반응형 Algorithm/Binary search4 [이분 탐색] 징검다리 건너기 - 2019 카카오 개발자 겨울 인턴십 코딩테스트 문제가 이분 탐색 문제인지를 확인할 수 있는 꼼수가 있다. 그것은 주어진 값의 범위를 확인하는 것이다. 이 문제는 주어진 범위를 아무리 잘 조합해봐도 복잡도가 터무니없는 수(억 단위)가 나온다. 보통 코딩테스트에서 효율성을 따질 때 최대 복잡도가 억 단위 이상이 나오면 거의 실패한다. 이분 탐색은 값을 미리 가정하고 푸는 알고리즘이다. 처음으로 가정하고 싶은 값은 어떠한 값을 골라도 상관이 없지만 보통 중간값을 선택한다. 해결 방법 중간값을 m으로 지정했다면 m명이 모두 징검다리를 건널 수 있는지를 체크해야 한다. m명이 모두 건널 수 없다면 m명 이상인 경우는 전부 건널 수 없다는 뜻이므로 범위의 최댓값을 m-1명으로 지정하고, m명이 모두 건널 수 있다면 범위는 m명~2억명 사이에 있다는 .. 2022. 3. 29. 이분탐색 고득점 kit 풀이 완료, 후기 이분탐색 알고리즘은 두 가지 선택지(true/false) 중에서 하나를 판단하고 범위를 좁혀 나가서 효율적으로 정답을 찾는 알고리즘이다. 이 알고리즘의 응용으로 1부터 10억까지 숫자중 상대방이 고른 숫자를 yes or no 문답 식으로 약 30번의 질문안으로 맞힐 수도 있을 정도로 매우 효율적인 알고리즘이다. 이분탐색 알고리즘을 프로그래머즈에서 처음 접해봐서 그런지 2개의 문제들은 모두 쉽지 않았다. 접근법을 떠올리는건 동적계획법, 그리디 알고리즘보다 다소 어려웠지만 매우 재미있는 알고리즘인 것 같다. 이 문제들을 풀면서 이분탐색 기법으로 어떻게 접근하는지 충분히 감을 익힐 수 있었다. 제일 먼저 할 일은 정답이라고 가정할 적당한 값을 세우는 것인데, 보통 정답이 될 수 있는 범위의 중간값으로 세우게 .. 2020. 11. 5. [이분 탐색, 난이도 상] 프로그래머즈, 징검다리 출발지점부터 도착지점 사이에 놓여져 있는 돌들 중에서 n개를 뺀 상태의 모든 경우에서, 각 지점 사이의 거리들의 최솟값들중 가장 큰 값을 구하면 되는 문제이다. rocks의 순서는 뒤죽박죽 하기 때문에 오름차순으로 정렬해주고 시작해야 한다. 우리가 구해야 하는 답(바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값) 을 미리 적당한 값으로 세워두고, 실제 정답이 미리 세워둔 값보다 큰지 작은지 판단하고 범위를 좁혀 나가면 된다. 바위를 몇개 제거해야 미리 세워둔 답이 실제 정답이 될 수 있는지 계산하는 것이 핵심이다. 그 바위 수는 n개가 나와야 하는 것이다. 입출력 예를 예로 들어보자. 정렬된 바위의 배치 -> [2,11,14,17,21] 각 지점 사이의 거리 (시작점, 도착점도 지점.. 2020. 11. 5. [이분 탐색, 난이도 중] 프로그래머즈, 입국심사 이 문제는 시간 복잡도 O(n)도 통하지 않는다. 인구 수, 심사 시간 데이터 범위가 10억이기 때문에 이분 탐색을 적용해야 하는 변수는 이 둘중 하나임을 알 수 있다. 이분 탐색 알고리즘은 IT계열의 대학교에서 대부분 1학년때 배울 것이다. "1000개의 수중 하나를 선택했을 때 10번 이내의 yes or no 질문으로 선택한 수를 찾을 수 있다" 이런 기초적인 예시로 많이 배웠을거라 생각이 든다. 여기서 핵심은 탐색 조건은 yes or no라는 것이다. 이분 탐색은 중간값을 기준으로 찾으려는 값이 큰가 or 작은가로 판단하여 탐색이 이루어진다. 찾으려는 값이 크다면 첫 번째 값~ 중간 값 까지는 찾으려는 수가 없다는 의미이고, 찾으려는 값이 작다면 중간 값~ 마지막 값 까지는 찾으려는 수가 없다는 의.. 2020. 10. 8. 이전 1 다음
