hws2006   3년 전

안녕하세요. 

1806 문제를 두 포인터를 이용하여 풀었습니다.

궁금한 점은 알고리즘 분류에 이분탐색으로 적혀있던데, 해당 문제가 왜 이분탐색으로 분류되는지 궁금합니다.

처음엔 두 포인터(head, tail)를 이용해서 mid = int((head + tail) / 2) 이런식으로 진행하거나, 아니면 수열을 절반으로 나눠서 진행 등등.. 이런 풀이를 생각했는데, 의외로 그런 트릭이 없이 풀려서 당황했습니다..

감사합니다.

djm03178   3년 전

투 포인터로 해결되는 문제 중에는 이분 탐색으로도 되는 것이 많습니다. 이 문제의 경우 각각의 시작 인덱스에 대해 거기부터 시작하는 부분합이 S 이상이 되는 최소 인덱스를 이분 탐색으로 찾을 수 있을 것 같습니다. 사실 투 포인터보다 별로 좋을 건 없는 풀이입니다.

댓글을 작성하려면 로그인해야 합니다.