탐색 문제의 최적성과 점화식
2019.10.16
탐색 문제의 최적성 입력으로 주어진 수들 중 어떤 값을 찾는 탐색 문제는 항상 정렬만이 최적의 답은 아니다 문제 1. 정렬되지 않은 배열 A = {1,2,...,n} 중에서, 특정한 수 하나만 빼고, 무작위의 순서로 총 n-1개의 숫자가 한번에 하나씩 입력된다. 배열 A에서 빠진 하나의 수를 찾아라 이러한 문제를 봤을 때 가장 먼저 떠오르는 풀이법은 입력된 숫자들을 boolean배열에 저장하면서 숫자가 나왔을 때 그 배열을 true값으로 바꾸고, n-1개의 숫자가 모두 들어오면 배열을 처음부터 뒤져서 false인 값을 찾는다. 이런식으로 하면 boolean배열이 하나 필요하고, for문을 이용해 배열을 돌면서 boolean을 찾기 때문에 최소 1번, 최대 n번의 비교가 필요한 방법이다. 이 방법의 시간 ..