알고리즘이란?

알고리즘은 한 마디로 말해 결과물을 위한 레시피이다.

문제와 알고리즘 (Problems and Algorithms)

알고리즘을 설계하기 전에 문제를 명확히 정의해야 한다.
- "풀어야 하는 문제는 무엇인가?"
- "무엇을 해야 하는가?"
- "이 코드는 무엇을 하는 코드인가?"
문제 (Problem): 가능한 입력들의 집합과 각 입력에 대한 출력의 쌍
알고리즘 (Algorithm): 주어진 문제를 해결하기 위한 기본 연산들의 시퀀스 (How?)

알고리즘 기술 방법

자연어 (이해 쉬움, 코딩 어려움)
슈도 코드 (알고리즘의 핵심을 표현)
프로그램 코드 (코딩 쉬움, 이해 어려움)

알고리즘 분석

Correctness Proof (정확성 증명)
Running Time Analysis (시간 복잡도 분석)

재귀 (Recursion)

모든 것은 재귀로 해결될 수 있다!

재귀와 알고리즘 설계 기법

분할 정복 (Divide & Conquer)
백트래킹 (Backtracking)
동적 계획법 (Dynamic Programming, DP)
탐욕법 (Greedy Algorithm)
트리 및 그래프 탐색 (Tree & Graph Traversal)

재귀의 예

팩토리얼 계산
자연수의 정의
점화식 및 수열
자료구조 (연결 리스트, 이진 트리)
재귀적 알고리즘 & 재귀 함수

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

문제 축소 (Reduction)

알고리즘 설계에서 가장 중요한 기법 중 하나는 문제를 더 작은 문제로 축소하는 것이다.

문제 X를 문제 Y로 변환 (Reduction)
Y의 알고리즘을 호출하여 X를 해결
예시:
- 최소값 찾기: sorted(A)[0]
- k번째 최소값 찾기: sorted(A)[k-1]

재귀와 Reduction

재귀는 특별한 종류의 Reduction
문제의 크기를 점점 줄여서 해결
Recursion = Subproblem으로 Reduction
내부 동작을 신경 쓰지 말 것!

하노이의 탑 (Hanoi Tower)

문제 정의

n개의 디스크를 기둥1에서 기둥3으로 옮기는 방법은?

해결 방법 (재귀)

n-1개의 디스크를 기둥1 → 기둥2로 이동
n번째 디스크를 기둥1 → 기둥3으로 이동
n-1개의 디스크를 기둥2 → 기둥3으로 이동

하노이의 탑 알고리즘

HANOI(n, src, dst, tmp):
    if n > 0:
        HANOI(n-1, src, tmp, dst)
        move disc n from src to dst
        HANOI(n-1, tmp, dst, src)

시간 복잡도 분석

T(n) = 2T(n-1) + 1
T(n) = O(2^n)

정렬 알고리즘 (Sorting Algorithms)

병합 정렬 (Merge Sort)

과정

배열을 절반으로 나눔
두 개의 부분 배열을 각각 정렬 (재귀)
두 부분 배열을 합쳐 정렬된 배열 생성

MERGE(A[1..n], m):
    i ← 1; j ← m+1
    for k ← 1 to n
        if j > n:
            B[k] ← A[i]; i ← i+1
        else if i > m:
            B[k] ← A[j]; j ← j+1

시간 복잡도

O(n log n)
점화식: T(n) = 2T(n/2) + O(n)

퀵 정렬 (Quick Sort)

과정

Pivot 선택
Partition: pivot을 기준으로 작은 값은 앞으로, 큰 값은 뒤로 정렬
두 개의 부분 배열을 재귀적으로 정렬

시간 복잡도

최악: O(n²) (pivot이 한쪽 끝에 치우친 경우)
최선: O(n log n)
점화식: T(n) = T(r-1) + T(n-r) + O(n)

Recursion 정리

Simplify and delegate!
- Simplify : 더 작은 instance(subproblem)를 만들고
- Delegate : 던져버리고 잊어버려라. Recursion의 요정이 다 해준다(?)
자신으로 문제를 줄여나가는 전략
정확성 증명은 수학적 귀납법 (Induction)으로 가능
시간 복잡도 분석: 점화식을 통해 분석