알고리즘과 복잡도: 해설이 있는 연습 문제

1복잡도가 재는 것

알고리즘은 문제를 푸는 유한한 정확한 단계의 목록입니다. 예를 들어 목록을 정렬하거나 전화번호부에서 이름을 찾는 것입니다.

두 알고리즘이 같은 문제를 풀어도 걸리는 시간은 크게 다를 수 있습니다. 복잡도는 입력이 커질 때 작업량이 어떻게 늘어나는지를 나타냅니다.

입력의 크기를 n이라고 합니다. 정렬할 항목의 수, 목록의 길이, 그래프의 노드 수 등입니다.

1000쪽짜리 전화번호부에서 이름을 찾는다고 생각해 보세요. 모든 쪽을 읽으면 최대 1000단계가 걸립니다. 가운데를 펴서 매번 절반으로 줄이면 약 10단계가 걸립니다.

시간 복잡도는 단계 수를 셉니다. 공간 복잡도는 추가 메모리를 셉니다. 둘 다 n의 함수로 씁니다.

보통은 최악의 경우를 봅니다. 크기 n인 모든 입력 중 작업량이 가장 많은 경우입니다. 때로는 평균의 경우나 최선의 경우를 묻기도 합니다.

2빅오와 증가율의 부류

빅오 표기는 n이 클 때 중요한 것만 남깁니다. 상수 인수를 버리고 가장 빨리 커지는 항만 남깁니다.

n = 1000이면 n² 항은 3 000 000이고 5n은 5000에 불과합니다. 작은 항은 전체를 거의 바꾸지 못합니다.

이 부류들은 느린 증가에서 빠른 증가 순으로 계속 나타납니다.

• O(1), 상수: 인덱스로 배열 원소 읽기.
• O(log n), 로그: 이진 탐색. 단계마다 문제를 절반으로 줄입니다.
• O(n), 선형: 모든 항목을 한 번 훑기. 예를 들어 최댓값 찾기.
• O(n log n): 병합 정렬 같은 좋은 정렬 알고리즘.
• O(n²), 이차: 항목에 대한 이중 반복문. 예를 들어 버블 정렬.
• O(2ⁿ), 지수: 모든 부분집합을 시도. 금방 쓸 수 없게 됩니다.

빅오는 상한입니다. 작업량이 기껏해야 이만큼 빨리 늘어납니다. Ω(빅 오메가)는 하한이고, Θ(세타)는 상한이면서 하한인 정확한 경계입니다.

로그의 밑은 빅오에서 중요하지 않습니다. 밑이 다른 로그는 상수배만큼만 다르기 때문입니다.

3탐색, 정렬, 재귀

몇몇 알고리즘은 거의 모든 강의에 나옵니다. 그 복잡도를 사실로 외워 두세요.

• 선형 탐색은 항목을 하나씩 확인합니다: O(n). 이진 탐색은 정렬된 배열이 필요하며 단계마다 범위를 절반으로 줄입니다: O(log n).
• 버블, 삽입, 선택 정렬은 이중 반복문에서 항목을 비교하고 교환합니다: O(n²). 삽입 정렬은 이미 정렬된 배열에서 O(n)입니다.
• 병합 정렬은 배열을 절반으로 나누어 각각 정렬한 뒤 합칩니다: 모든 경우에 O(n log n)이며 추가 메모리는 O(n)입니다.
• 퀵 정렬은 피벗을 기준으로 나눕니다: 평균 O(n log n)이지만 최악의 경우에는 O(n²)입니다. 예를 들어 정렬된 배열에서 첫 원소를 피벗으로 쓸 때입니다.
• 항목을 비교하기만 하는 정렬은 최악의 경우 Ω(n log n)을 넘어설 수 없습니다. 계수 정렬은 비교하지 않으므로 더 빠릅니다.

재귀 함수는 더 작은 입력으로 자기 자신을 호출하다가, 직접 답할 수 있는 기저 사례에 이릅니다. 실행 시간은 점화식으로 씁니다.

• T(n) = T(n/2) + O(1)은 이진 탐색처럼 O(log n)을 줍니다.
• T(n) = 2T(n/2) + O(n)은 병합 정렬처럼 O(n log n)을 줍니다.
• T(n) = T(n − 1) + O(n)은 O(n²)을 줍니다.
• T(n) = 2T(n − 1) + O(1)은 O(2ⁿ)을 줍니다.

알아 둘 만한 설계 아이디어가 셋 있습니다. 분할 정복은 나누고, 풀고, 합칩니다. 탐욕은 단계마다 지역적으로 가장 좋은 선택을 합니다. 동적 계획법은 겹치는 부분 문제의 답을 저장해 한 번만 계산합니다.

4단계별 방법

코드 조각의 시간 복잡도를 구하려면:

1. n이 무엇인지 정하세요: 입력의 크기.
2. 각 반복문이 몇 번 도는지 세세요. 매번 1씩 더하는 반복문은 약 n번 돕니다. 두 배로 하거나 절반으로 하는 반복문은 약 log₂ n번 돕니다.
3. 안에 들어 있는 반복문은 곱합니다. 차례로 이어지는 반복문은 더합니다.
4. 재귀 함수는 점화식을 쓰세요. 몇 번 호출하는지, 어떤 크기인지, 호출당 작업량은 얼마인지.
5. 가장 빨리 커지는 항만 남기고 상수는 버리세요.
6. 작은 수로 확인하세요. 예를 들어 n = 8 또는 n = 1024.

이론 문제에서는 먼저 그것이 설명하는 알고리즘이나 아이디어의 이름을 말하고, 그다음 복잡도와 조건(정렬된 입력, 음이 아닌 가중치, 겹치는 부분 문제)을 떠올리세요.

5풀이 예제

모든 단계를 따라가 보세요. 다음 단계를 열기 전에 미리 예측해 보세요.

6흔한 실수

• 차례로 이어지는 반복문을 곱하는 것. n + n = 2n도 여전히 O(n)입니다.
• O(2n)이나 O(n/2)처럼 상수를 남기는 것. 둘 다 O(n)입니다.
• 두 배로 늘리는 반복문을 n번 도는 것으로 세는 것. 약 log₂ n번 돕니다.
• 정렬되지 않은 데이터나 가운데에 한 번에 접근할 수 없는 연결 리스트에 이진 탐색을 쓰는 것.
• 최악의 경우를 물었는데 퀵 정렬의 평균 경우를 답하는 것.
• 빅오가 “정확히”를 뜻한다고 생각하는 것. O(n²)은 상한이고, Θ(n²)이 정확한 증가율입니다.

7시험 문제의 유형

• 쉬움: 핵심 용어와 사실. 이진 탐색, 병합 정렬, 배열 접근의 복잡도, O, Ω, Θ의 뜻, 재귀란 무엇인가.
• 보통: 개념 적용. 코드 조각의 복잡도, 풀어야 할 점화식, n이 두 배가 될 때 시간이 어떻게 변하는지, 과제에 맞는 알고리즘.
• 어려움: 사례와 분석. 마스터 정리, 퀵 정렬의 최악의 경우, 탐욕과 동적 계획법의 비교, P, NP, NP-완전 부류.

P는 다항 시간에 풀 수 있는 문제를 포함합니다. NP는 해를 다항 시간에 확인할 수 있는 문제를 포함합니다. P의 모든 문제는 NP에 속하며, P = NP인지는 아직 알려지지 않았습니다.