등차수열에서 중간에 빠진 수 구하기 : binary search 기법으로 풀면 된다.
오늘 새벽에 들어온 문제 하나 보겠습니다. 당연하게도, brr은 오름차순으로 sort가 된 상태입니다. 쉬운 문제는 아닙니다. 다만, 아이디어를 얻을 수 있는 것 중 하나는 이진 검색이라는 것이 있어요. 링크 들어가셔도 좋을 듯 싶어요. 이것을 아신다는 전제하에 설명을 드리도록 하겠습니다. 먼저, 등차 수열 {a(1), a(2), ... , a(n)}이 있다면 임의의 1= 0일 때, a = 0이고 b = 1이거나, 혹은 a = 1이고 b = 0이여야 합니다. 그러면, 좌측에서 수가 빠지지 않았다면, 우측에서 탐색을 해야 하고, 반대로, 좌측에서 수가 빠졌다면, 왼쪽 구간을 탐색해야 할 거에요. 데이터를 볼까요? 문제를 보면, arr[mid] - arr[le]의 값은 8입니다. ..
자료알고/알고리즘
2019. 12. 10. 03:43
최근댓글