목록검색알고리즘 (1)

글쓰는공대생의 IT블로그

[acmicpc] upper bound (feat. 이진 검색 알고리즘) / C++

출처 => [알고리즘 해결을 위한 창의적 알고리즘 해결 (중급)] 문제 문제 분석 문제의 의도 : k를 초과하는 가장 첫 번째 원소의 위치를 구하는 것 ① 먼저 구간을 설정한다. ([s, e]) ② 이 구간의 중간위치의 값을 m이라고 하면, A[m-1]k 인 최소 m을 찾아야 한다. 풀이 => 예시로 주어진 배열 A는 1,2,7,7,7,7,11,15이다. k의 값은 7이다. 따라서 출력값은 7이 나와야 한다. => 주어진 배열은 [0,8]이고 이에 따라 중간값의 위치인 m은 4이다. 우리가 원하는 것은 찾으려는 값의 위치가 아니라 k값보다 큰 수가 처음으로 등장하는 위치이다. A[4]=7이므로 우리의 위치와 일치하지 않다. => A[6]>7 이므로 그보다 아래로 범위를 설정하여 재탐색 =>A[5]=7이므..
🖥️ 컴퓨터공학 🖥️/알고리즘 2020. 6. 8. 02:00
이전 Prev 1 Next 다음