문제 명세하기: 입력, 출력, 단계
코드를 쓰기 전에 문제를 정확히 설명해요. 이것을 명세라고 해요.
- 입력: 어떤 데이터가 들어오는지, 그 종류와 범위 (예: "정수 n개, 1 ≤ n ≤ 1000").
- 출력: 무엇을 돌려줘야 하는지 (예: "그중 가장 큰 수").
- 조건: 시작 전에 참인 것(사전 조건)과 끝난 뒤에 참인 것(사후 조건).
단계 적기
알고리즘은 올바른 입력이면 무엇이든 맞는 출력으로 바꿔 주는, 끝이 있는 분명한 단계의 목록이에요. 이렇게 적을 수 있어요.
- 일상의 말: "숫자를 하나씩 보고, 지금까지 가장 큰 수보다 크면 그 수를 기억한다."
- 번호 붙인 단계 목록: 1. best ← 첫 번째 수. 2. 다음 수 x마다: x > best이면 best ← x. 3. best를 출력한다.
- 더 정확하게는 의사코드나 순서도.
작은 입력으로 손으로 직접 해 봐요. 까다로운 경우도 꼭 넣어요(모두 같은 수, 음수, 수가 하나뿐일 때).
탑다운 설계와 바텀업 설계
탑다운(단계적 세분화): 전체 일에서 시작해 큰 단계 몇 개로 나누고, 각 단계를 다시 나눠요. 쉽게 코드로 옮길 수 있을 때까지요. 예: "성적표 만들기" → 점수 읽기 → 평균 구하기 → 등급 매기기 → 출력하기.
바텀업: 먼저 작고 다시 쓸 수 있는 조각(최댓값을 찾는 함수, 정렬하는 함수)을 만들어 시험하고, 그다음 이어 붙여 전체 프로그램을 만들어요.
실제 프로젝트는 둘을 섞어요. 계획은 탑다운으로, 만들고 시험하기는 바텀업으로 해요.
분할 정복과 반씩 줄이기
분할 정복은 세 동작이에요. 같은 종류의 더 작은 조각으로 문제를 나누고, 각 조각을 (보통 재귀로) 풀고, 답을 합쳐요.
- 이진 탐색(반씩 줄이기): 정렬된 목록에서 가운데와 비교하고 절반을 버려요. n개면 약 log₂ n번 확인해요. 16 → 4, 1 000 000 → 20.
- 병합 정렬: 목록을 둘로 나누고, 각각 정렬하고, 합쳐요. O(n log n).
- 빠른 거듭제곱: a⁸ = ((a²)²)². 곱셈 7번 대신 3번.
- 이분법으로 근 찾기: 함수의 부호가 바뀌는 구간을 계속 반으로 줄여요.
그리디 알고리즘
그리디 알고리즘은 지금 가장 좋아 보이는 선택을 하고 절대 바꾸지 않아요.
- 50, 20, 10, 5, 2, 1 동전으로 거스름돈 주기: 큰 동전부터. 이런 동전 체계에서는 최적이에요.
- 하루에 가장 많은 활동 고르기: 늘 가장 일찍 끝나는 활동을 골라요. 최적이에요.
- 쪼갤 수 있는 배낭 문제: 1kg당 가치가 가장 큰 물건부터 담아요. 최적이에요.
하지만 그리디가 항상 맞는 것은 아니에요. 동전 1, 3, 4로 6을 그리디로 내면 4 + 1 + 1(3개)인데, 3 + 3은 2개예요. 그리디를 믿으려면 증명하거나, 확실한 방법과 비교해 시험해야 해요.
동적 계획법과 백트래킹
동적 계획법(DP)
같은 작은 문제가 되풀이되면 각각을 한 번만 풀어 답을 표에 저장해요. 금액 a의 최소 동전 수: best[a] = 1 + min(best[a - c]) (c ≤ a인 동전 c마다), 시작은 best[0] = 0. 동전 1, 3, 4이면 best = 0, 1, 2, 1, 1, 2, 2. 표를 작은 값에서 큰 값으로 채우면 바텀업이고, 기억을 쓰는 재귀는 탑다운(메모이제이션)이에요. 더 자세한 내용은 따로 있는 동적 계획법 수업에서 봐요.
백트래킹
선택을 하나씩 쌓으며 답을 만들어요. 선택이 규칙을 어기거나 막다른 길이면 되돌리고 다음 선택지를 시도해요. 미로, 스도쿠, N-퀸 퍼즐, 모든 부분집합 나열에 써요. 안 될 가지를 통째로 건너뛰는, 똑똑한 완전 탐색이에요.
완전 탐색
가능한 답을 전부 해 봐요. 항상 맞지만 너무 느린 경우가 많아요(부분집합 2ⁿ개, 순서 n!가지).
기법 고르기: 정확성, 효율, 자료구조
| 기법 | 쓰는 때 | 예 | 보통 시간 |
|---|---|---|---|
| 완전 탐색 | 입력이 아주 작을 때 | 세 자리 비밀번호 전부 해 보기 | 자주 2ⁿ 또는 n! |
| 분할 정복 | 조각이 서로 독립일 때 | 이진 탐색, 병합 정렬 | O(log n), O(n log n) |
| 그리디 | 지금의 최선이 안전하다고 증명됐을 때 | 활동 선택, 거스름돈 | O(n log n) |
| 동적 계획법 | 작은 문제가 되풀이될 때 | 동전 문제, 최단 경로 | 표의 크기 |
| 백트래킹 | 규칙이 있는 탐색 | 미로, 스도쿠 | 지수 시간, 하지만 가지치기 |
근거를 대요
정확성: 알고리즘이 항상 끝나고 맞는 출력을 준다는 것을 보여요(루프 불변식, 증명, 극단적인 경우의 시험). 효율: n이 커질 때 단계 수를 세고(빅오) 다른 방법과 비교해요.
자료구조가 도와줘요
배열은 표(DP)에, 스택은 백트래킹(어디로 돌아갈지 기억)에, 큐는 층별 탐색에 써요. 이진 트리는 각 노드가 자식을 최대 둘 갖도록 데이터를 저장해요. 이진 탐색 트리에서는 작은 키는 왼쪽, 큰 키는 오른쪽에 두어서, 한 층 내려갈 때마다 일이 반으로 줄어요. 이진 탐색과 똑같아요.
직접 해 보기: 동전과 숫자 맞히기
- 친구와 1~100 숫자 맞히기를 해 봐요. 늘 가운데를 물어봐요. 7번 안에 항상 이길 수 있을까요? (2⁷ = 128.)
- 동전 1, 3, 4로 금액 0부터 10까지 DP 표를 종이에 써 봐요. 그리디는 어디서 틀릴까요?
- 마지막 3D 단계를 열어요. 동전 1, 7, 10과 금액 14를 해 봐요. 그리디는 10 + 1 + 1 + 1 + 1, DP는 7 + 7이에요.
- "목록에서 가장 작은 수 찾기"의 단계 목록을 쓰고, 5, 5, 5와 수가 하나뿐인 경우로 시험해 봐요.
핵심 공식과 정의
- 명세 = 입력 + 출력 + 조건
- 반씩 줄이기: 약 log₂ n 단계 (16 → 4, 1024 → 10)
- 동전 DP: best[0] = 0; best[a] = 1 + min best[a - c]
- 분할 정복 = 나누기 + 풀기 + 합치기
- 그리디는 빠르지만 최적임을 증명해야 함
풀이 예제
1. n개의 수 중 가장 큰 수를 찾는 명세와 단계 목록을 써 보세요.
입력: n ≥ 1개의 수. 출력: 가장 큰 수. 단계: 1. best ← 첫 번째 수. 2. 나머지 수 x마다: x > best이면 best ← x. 3. best를 출력. 4, 9, 2, 7, 12, 5, 10, 3이면 비교 7번 뒤에 출력은 12예요.
2. 1부터 1000 중 수를 찾으려면 반씩 줄이기로 질문이 몇 번 필요할까요?
질문마다 범위가 반이 돼요: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. 질문은 10번이에요 (2¹⁰ = 1024 ≥ 1000).
3. 동전 50, 20, 10, 5, 2, 1로 87을 그리디로 내 보세요.
50 (37 남음), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 동전 5개.
4. 동전 1, 3, 4로 금액 7까지 DP 표를 채워 보세요.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. 활동(시작-끝): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. 겹치지 않게 가장 많은 활동을 고르세요.
끝나는 시각이 가장 이른 것부터 그리디로: A (11에 끝남), 그다음 C (11에 시작, 13에 끝남), 그다음 E (13에 시작). 활동 3개: A, C, E.
6. 탑다운으로 계획해 보세요: 반의 평균 점수와 1등 학생을 알려 주는 프로그램.
1단계: 데이터 읽기 → 계산 → 출력. 2단계: 이름과 점수를 목록에 읽기. 합계와 평균 구하기. 최고 점수와 그 이름 찾기. 둘 다 출력. 그다음 각 조각을 바텀업으로 코딩하고 시험해요.
자주 하는 실수
- 입력과 출력을 정하기 전에 코딩부터 시작하는 것. 많은 '버그'는 사실 불분명한 명세 때문이에요.
- 그리디가 항상 최적이라고 생각하는 것. 증명할 수 있을 때만 통해요(동전 1, 3, 4가 반례예요).
- 정렬되지 않은 목록에 이진 탐색을 쓰는 것. 반씩 줄이기는 정렬된 데이터가 필요해요.
- DP와 분할 정복을 헷갈리는 것. DP는 겹치는 부분 문제를 저장하고, 분할 정복은 서로 독립인 조각으로 나눠요.