. 티모는 더 많은 책을 접할 생각에 기뻐했지만, 막상 1,000권이 도착하니 문제를 실감했습니다. 이제 티모는 책 1,000권을 도서관 코드번호 순으로 정렬해야 합니다. - P276
버블 정렬
인접한 두 값 중 더 작은 값이 뒤에 있을 때, 이 둘을 바꾸어 나가며 정렬하는 알고리즘 - P277
5권의 책을 정렬하기 위해서는 총 4+3+2+1 = 10회의 비교가 필요합니다. 그렇다면 1,000권의 책을 정렬하기 위해서는 총999 + 998 +....+ 2 + 1 = 499,500회의 비교가 필요합니다. 티모가 책을 한 번 비교하는 데 1초가 걸린다고 하면 정렬을 끝내는 데 5.78일이나 필요하네요. - P278
이건 어떤가요? 먼저 첫 번째 책과 두 번째 책 중 더 큰 책을 뒤에 놓습니다. 그 후세번째 책과 두 번째 책을 비교해 만약 세 번째 책이 두 번째 책보다 작다면 두 책의 자리를 바꿉니다. 만 - P279
삽입 정렬
두 번째 자료부터 시작해. 정렬하려고 하는 값을 그 앞의 값들과 비교해 가며 알맞은 위치로 옮겨질 때까지 앞으로 옮기는 알고리즘 - P279
도 하지만 삽입 정렬을 사용해도 1,000권의 도서를 정렬하는 데는 3일 가까이 걸립니다. 버블 정렬 및 삽입 정렬과 더불어 또다른 유명한 정렬 알고리즘으로 선택 정렬¹이 있지만 선택 정렬은 삽입 정렬보다 더 느립니다. - P280
여러분 혹시 업 앤 다운 게임을 아시나요? 이 게임은 상대방이 종이에 적어둔 1부터 100 사이의 숫자가 무엇인지 맞히는 게임입니다. 단, 상대방은 내가 부른 숫자가 자신이 생각하고 있는 숫자보다더 큰지(업), 작은지 (다운)를 알려줘야 합니다. 적은 횟수 안에 숫자를 맞출수록 더 높은 점수를 얻을 수 있습니다. - P280
가장 단순한 방법은 그냥 1부터 100까지 불러보는 것입니다. 이 알고리즘은 선형 탐색이라고 합니다. - P280
대부분은 1부터 100의 중앙값인 50을 부를 것입니다. 그래야 가장 효과적으로 범위를 좁힐 수 있으니까요. - P281
. 이와 같이 남은 구간의 중앙값을 불러서 구간을 반씩 줄여나가면 매우 효과적으로 숫자의 범위를 좁혀나갈 수 있습니다. 이 알고리즘을 이진 탐색이라고 합니다. - P281
선형 탐색은 최악의 경우 회의 시도가 필요하므로 시간복잡도를 O(n) 이라고 표기하며, 이진 탐색은 최악의 경우 log_2(n)의 시도가 필요하므로 O(logn)이라고 표기합니다. - P281
좋은 알고리즘은 연산에 필요한 시간을 어마어마하게 줄여줄 수 있기 때문에 이러한 알고리즘을 찾는 것은 컴퓨터 공학에서 매우 중요한 주제입니다. - P282
(전략) 따라서 버블 정렬과 삽입 정렬의 시간복잡도는 O(n²) 이라고 쓰는 것이 가장 일반적입니다. - P283
이진 탐색의 경우 중앙값을 기준으로 해 문제의 크기를 반으로 줄였습니다. 이 아이디어를 책을 정렬하는 데 적용해 볼게요. - P283
11권의 책을 예시로 들어보겠습니다.
(중략)
7을 기준으로 책을 두 부류로 나눔으로써, 우리는 11권의 책을 정렬하는 문제를 6권의 책과 4권의 책을 각각 정렬하는 문제로 나눴습니다. - P284
위와 같이 정렬하는 알고리즘을 퀵 정렬(Quick Sort)이라고 합니다.
예시에서도 알 수 있다시피 퀵 정렬은 버블 정렬이나 삽입 정렬보다 매우 빠른 알고리즘입니다. - P285
하지만 퀵 정렬의 경우, 처음에는 책이 1권만 정렬되지만 그다음에는 2권의 책이, 그다음에는 4권의 책이 한꺼번에 정렬됩니다. 이렇게 정렬되는 책의 개수가 지수적으로 증가하기 때문에 매우 빠르게 책을 정렬할 수 있습니다. - P285
(중략), 모든 책의 정렬이 완료될 때까지 거쳐야 하는 총 단계의 개수는 logn정도로 잡을 수 있습니다. 따라서 퀵 정렬의 시간복잡도는O(nlogn) 입니다. O(n²) 에 비해서 무지하게 빠르네요! - P286
퀵 정렬 이외에도 O(nlogn)의 시간복잡도를 가지는 알고리즘은병합 정렬, 힙 정렬 등이 있습니다. 하지만 O(nlogn)보다 더 빠른 정렬 알고리즘은 존재하지 않습니다. 이건 수학적으로 증명이 된 사실입니다.³
3) 엄밀히 말하자면 값을 비교하는 정렬 알고리즘 중 O(n log (n))보다 빠른 걱은 없습니다. 값을 비교하지 않는 정렬 알고리즘으로는 계수 정렬이 있으며 이 알고리즘의 시간복잡도는 O(n)입니다. - P286
정렬보다 더 어려운 문제의 대표적인 예로는 세일즈맨 문제가 있습니다. 세일즈맨 문제는 비용 k 이하로 n개의 지점을 모두 방문하는 게 가능한지를 묻는 것입니다. - P287
세일즈맨의 차에는 지금 35 만큼 운전할 수 있는 기름만이 남아 있습니다. 과연 세일즈맨은 4개의 집을 모두 방문할 수 있을까요? - P287
4개의 집을 방문하는 순서의 경우의 수는 총 4!로스물네 가지입니다.⁴ 이 경로를 전부 계산하다 보면, 비용이 35보다 작은 경로가 있는지 없는지 확실히 알 수 있겠죠.
4) 느낌표 기호는 팩토리얼이라고 읽습니다. n은 1부터 n까지 곱한 값을 의미합니다. - P287
O(nl)은 정말 비효율적인 시간복잡도입니다. n이 조금만 커져도 n!은 어마어마하게 증가합니다. 예를 들어서 n이 20일 때, (중략). 하지만 n!회의 연산을 완료하기 위해서는 우주 나이의 5.5배에 육박하는 시간이 필요합니다. - P288
하지만 누군가 세일즈맨 문제의 해답을 가지고 오면, 그 답이 올바른지 확인하는 일은 매우 간단합니다. 예를 들어 아래의 경로는비용 35 이하의 경로가 맞을까요? - P288
이처럼 답을 확인하는 것이 쉬운 문제를 수학자들과 컴퓨터 과학자들은 NP 문제라고 합니다.
NP 문제 (Nondeterministic Polynomial)
주어진 답이 올바른지 확인하는 것이 쉬운 문제.
세일즈맨 문제, 스도쿠, 소인수분해 등이 있다. - P289
한편 답을 구하는 것이 쉬운 문제는 P문제라고 합니다.
P 문제 (Deterministic Polynomial)
답을 구하는 것이 쉬운 문제.
곱셈, 정렬, 업앤다운 게임 등이 있다. - P289
O(logn)은 다항식은 아니지만, O(n)보다 빠르기 때문에 쉬운 문제로 간주합니다. 다항식이 기준이 되는 이유는 다항 시간 알고리즘은 현대의 컴퓨터가 충분히 계산할 수 있을 정도이며, 설령 그렇지 않다고 하더라도 기술의 발전을 조금만 기다리면 충분히 계산할 수 있을 정도여서입니다. - P289
모든 P 문제는 NP 문제입니다. 답을 구하는 것도 답을 확인하는 것이라고 볼 수 있으니까요. - P290
주어진 수가 소수인지 아닌지 판별하는 문제는 오랜기간 NP라고 생각되어 왔습니다.⁵ 하지만 아그라왈, 카얄, 그리고삭세나라는 컴퓨터 과학자들이 다항 시간 안에 이 문제를 푸는 알고리즘을 발견했습니다.
5) ‘소수 판정 문제는 주어진 수 n을 2부터 -1까지의 수로 나누어 보면 되니 O(n) 아닌가요?"라는의문이 들었다면 훌륭합니다! 사실 시간복잡도는 책에서 설명한 것보다 더 복잡한 개념입니다. 어떤 수를 컴퓨터 프로그램에 입력하기 위해서는 이진수로 변환해야 합니다. 이 과정에서 필요한 비트(bit)의 개수가 n의 정확한 의미입니다. 이 의미대로 계산하면 시간복잡도는 0(2^(n/2))입니다. - P290
P-NP 문제
모든 NP 문제들은 P에 속하는가? 즉, P = NP인가? - P291
대부분의 전문가들(약 83퍼센트)은 PNP라고 생각합니다. 하지만 인류의 믿음이 깨진 적은 정말 많았죠? 아직까지는 P≠NP라고확실히 단정지을 근거가 없습니다. - P291
|