이 글에서는 아래 두 가지 주제를 요약하고, 파이썬으로 테스트한 시간 복잡도 그래프와 표준오차를 이용한 해석도 함께 추가로 정리했습니다.
[주제 1] 정렬 알고리즘(sorting algorithms, sorts) 6종
- 기본 개념, 장단점, 시간/공간 복잡도
- 6종 예제 구현: 버블, 선택, 삽입, 병합, 퀵, 힙
[주제 2] 동적 프로그래밍(Dynamic Programming, DP)
- 기본 개념, 분할 정복과의 차이, 메모이제이션/탑다운-바텀업 방식
- DP 예제 구현: Fibonacci, 계단 오르기, 0/1 배낭 문제
[글 전체 개요]
│
├─ 1. 복잡도와 알고리즘 큰 그림
│ ├─ 1-1. 시간 복잡도
│ └─ 1-2. 공간 복잡도
├─ 2. 통계적 해석: 표준편차 vs 표준오차
├─ 3. 정렬 알고리즘 6종 개념
│ ├─ O(n²) 계열: 버블(Bubble), 선택(Selection), 삽입(Insertion)
│ └─ O(n log n) 계열: 병합(Merge), 퀵(Quick), 힙(Heap)
├─ 4. 복잡도 해석
│ ├─ Big-O 이론
│ ├─ 정렬 시간 Mean ± SE
│ └─ SE vs repeats
├─ 5. 동적 프로그래밍(DP)
│ ├─ Fibonacci
│ ├─ Climb Stairs
│ └─ 0/1 Knapsack
├─ 6. 정렬 vs DP 비교 (장단점, 특징)
├─ 7. 요약: 알고리즘, 복잡도, 프로그램 효율성
└─ ※ 코드
1. 복잡도와 알고리즘 큰 그림
1-1. 시간 복잡도
시간 복잡도는 입력 크기 n에 따라 연산 횟수가 어떻게 증가하는지를 나타내는 것입니다.
실제 연산 횟수 T(n)은 보통 다음처럼 "다항식 + 상수" 형태가 됩니다.
- 예1: T(n) = 5n + 3
- 예2: T(n) = 2n² + 10n + 7
n이 충분히 커지면, 위 식에서 연산 횟수의 성장을 지배하는 항은 각각 이렇게 됩니다.
- 5n + 3 → n에 비례 ⇒ O(n)
- 2n² + 10n + 7 → n²에 비례 ⇒ O(n²)
이때 사용하는 표기가 Big-O 표기법입니다.
- 상수배·상수항은 버리고, 성장률만 남기는 것이 핵심입니다.
"O"는 상한(upper bound) 을 뜻합니다. 예를 들어, 어떤 알고리즘의 연산 횟수가 항상 C·n² 이하라면(충분히 큰 n에서) 그 알고리즘은 O(n²)이 됩니다. ☞ [참고] 4. 복잡도 해석
1-2. 공간 복잡도
공간 복잡도는 알고리즘이 사용해야 하는 추가 메모리의 크기가 n에 따라 어떻게 증가하는지를 나타낸 것입다.
- 정렬 알고리즘 중
- 버블, 선택, 삽입, 힙 정렬은 배열 내부에서 원소를 교환 → O(1) 추가 메모리.
- 병합 정렬은 병합을 위해 임시 배열이 필요 → O(n) 추가 메모리. - DP 알고리즘은 보통 dp 테이블(리스트, 2차원 배열 등)을 사용하기 때문에 문제에 따라 O(n), O(nW), O(n²) 등 다양한 공간 복잡도를 갖습니다.
시간과 공간은 서로 바꿔 쓸 수 있는 경우가 많습니다. 예를 들어 Fibonacci 재귀는 메모리를 거의 쓰지 않지만 O(2ⁿ) 시간, DP를 쓰면 메모리를 추가로 쓰는 대신 O(n) 시간으로 줄일 수 있습니다.
2. 통계적 해석: 표준편차 vs 표준오차
정렬 알고리즘의 성능을 단순히 "한 번 실행 시간"으로 비교하면 우연에 따른 차이가 너무 큽니다.
그래서 다음과 같이 반복 테스트을 수행했습니다.
- 입력 크기 n을 여러 값(10 ~ 10000)으로 설정: logscale으로 비교할 목적.
- 각 n마다 무작위 배열을 repeats회 생성: SIZES = n
- Mean ± SE 그래프 출력에 적용한 파라메터:
- SIZES = [10, 20, 30, 40, 50, 60, 80, 100, 120, 150, 200, 250, 300, 400, 500, 600, 800, 1000, 1500, 2000, 3000, 4000, 5000, 7000, 10000]
- REPEATS = 5 - SE vs repeats 그래프 출력에 적용한 파라메터:
- REPEATS_LIST = [5, 10, 20, 50, 100, 200, 500, 1000, 2000]
- SIZE = 100
- Mean ± SE 그래프 출력에 적용한 파라메터:
- 각 배열에 대해 정렬 알고리즘 6종을 모두 실행.
- 실행 시간에 대한 다음을 계산.
- 평균(mean_time)
- 표준편차(SD)
- 표준오차(SE)
2-1. 표준편차(Standard Deviation, SD)
- 측정값: x₁, x₂, …, x_k
- 평균:
- 표준편차: s가 클수록 각 측정값이 평균에서 많이 흩어져 있다는 뜻입니다.
2-2. 표준오차(Standard Error, SE)
알고 싶은 것은 "진짜 평균 실행 시간(모평균)"입니다. 테스트을 통해 얻은 평균은 표본이기 때문에 오차를 갖습니다. 표준오차(SE)는 이 평균값 자체의 불확실성을 나타냅니다.
- 표준오차(SE):반복 횟기 k를 늘리면 SE는 1/√k 비율로 감소합니다.
정렬 알고리즘의 평균 실행 시간 차이를 비교할 때는 각 측정값의 흩어짐(SD) 보다, "평균이 얼마나 정확한가(SE)"가 더 중요합니다. 그래서 이 글에서는 그래프의 에러바로 SE를 사용했습니다.
3. 정렬 알고리즘 6종 개념
정렬 알고리즘은 크게 두 계열로 나눌 수 있습니다.
- O(n²) 계열: 버블(Bubble), 선택(Selection), 삽입(Insertion)
- O(n log n) 계열: 병합(Merge), 퀵(Quick), 힙(Heap)
아래는 이에 대한 비교 표입니다.
| 알고리즘 | 평균 시간복잡도 | 최악 시간복잡도 | 공간복잡도 | 주요 특징, 적합한 상황 |
| Bubble | O(n²) | O(n²) | O(1) | 인접 원소를 계속 교환. (교육용, n이 매우 작을 때) |
| Selection | O(n²) | O(n²) | O(1) | 매번 최솟값을 찾아 앞으로. (교환 횟수 적음) |
| Insertion | O(n²) | O(n²) | O(1) | 이미 정렬된 부분에 새 원소를 끼워 넣음. (거의 정렬된 데이터에 유리) |
| Merge | O(n log n) | O(n log n) | O(n) | 반으로 나누고 병합. (안정 정렬, 큰 데이터에 적합) |
| Quick | O(n log n) | O(n²) | O(log n) | 피벗 기준 분할 정복. (평균적으로 매우 빠름) |
| Heap | O(n log n) | O(n log n) | O(1) | 힙 구조 사용. 최악에도 O(n log n). (우선순위 큐와 자연스럽게 연결) |
3-1. O(n²) 계열 – 버블(Bubble), 선택(Selection), 삽입(Insertion)
Bubble Sort (버블 정렬) : O(n²)
def bubble_sort(a):
a = a[:] # 원본 보호
n = len(a)
for i in range(n):
swapped = False
for j in range(0, n-1-i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
swapped = True
if not swapped: # 더 이상 교환이 없으면 종료
break
return a- 인접한 두 원소를 비교·교환하면서 큰 값을 뒤로 "떠오르게" 하는 방식
- 시간 복잡도: 평균·최악 O(n²)
- 장점: 구현이 매우 단순, 교육용 예제로 좋음
- 단점: 실제 사용에서는 거의 항상 비효율적이다.
Selection Sort (선택 정렬) : O(n²)
- 매 단계마다 남아 있는 구간에서 최솟값의 위치를 찾고, 맨 앞과 교환
- 비교 횟수는 항상 n(n-1)/2 → O(n²)
- 교환 횟수는 최대 n-1로 작다는 점이 특징
- 데이터 이동이 비싼 환경(플래시 메모리 등)에서 이점이 있을 수 있다.
Insertion Sort (삽입 정렬) : O(n²)
def insertion_sort(a):
a = a[:]
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j -= 1
a[j+1] = key
return a- 이미 정렬된 왼쪽 부분에 새 원소를 적당한 위치에 끼워 넣는 방식
- 평균·최악 시간 복잡도: O(n²)
- 데이터가 거의 정렬돼 있을 때 평균 복잡도가 크게 줄어드는 장점
- 실제 라이브러리 정렬(Timsort 등)에서도 작은 구간에는 삽입 정렬을 섞어 사용한다.
3-2. O(n log n) 계열 – Merge / Quick / Heap
Merge Sort (병합 정렬) : O(n log n)
- 배열을 절반으로 나누어 재귀적으로 정렬한 뒤, 두 정렬된 배열을 선형 시간에 병합
- 분할 깊이: log₂ n, 각 깊이에서 병합 비용: O(n) → 전체 O(n log n)
- 항상 같은 복잡도를 보장하고, 안정 정렬(stable) 이라는 장점
- 단점은 병합용 배열 때문에 O(n) 추가 메모리가 필요하다는 점
Quick Sort (퀵 정렬) : O(n log n)
- 피벗을 하나 선택하고, 피벗보다 작은 원소/큰 원소로 분할
- 분할된 두 부분에 대해 재귀 호출
- 평균적으로는 O(n log n) 이며, 실제로 가장 빠른 편
- 피벗을 잘못 선택하면(이미 정렬된 경우 등) 최악 O(n²) 까지 나빠질 수 있음
- 현대 라이브러리는 피벗 선택을 무작위/median-of-three 등으로 개선
Heap Sort (힙 정렬) : O(n log n)
- 배열을 최대 힙(max-heap)으로 만든 뒤, 루트(최댓값)를 끝으로 보내고 힙을 재정비
- 힙 구성 O(n) + 원소 n개를 꺼내는 데 각 O(log n) → 전체 O(n log n)
- 추가 메모리가 거의 필요 없고(제자리 정렬), 최악 경우도 O(n log n) 보장
- 다만 병합/퀵에 비해 실제 상수 배가 조금 더 큰 편
[참고] 각 정렬 알고리즘 6종에 대한 코드는 글 마지막 하단을 참고해주세요.
4. 복잡도 해석
이제 이론적인 Big-O와 실제 파이썬 테스트 결과를 비교하였습니다.
4-1. Big-O 이론
[그래프 1] Big-O Complexity Comparison
- O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!) 성장 비교)
- n이 커질수록 O(n²) 곡선이 O(n log n)보다 훨씬 빠르게 상승합니다.
- O(2ⁿ), O(n!)은 다른 것들에 비해 y축 상단으로 가파르게 상승합니다. (기울기가 큽니다.)
☞ n이 커질수록 O(n²), O(2ⁿ), O(n!)이 O(n log n)이나 O(n)보다 훨씬 빠르게 커진다는 것을 시각적으로 확인할 수 있습니다. 즉, 이 그래프는 "왜 n이 큰 상황에서는 O(n log n) 정렬을 택해야 하는가"에 대한 직관적인 해석을 도와줍니다.
4-2. 정렬 시간 Mean ± SE
[그래프 2] All Sorting Algorithms – Mean ± SE
- x축 (log scale) : 입력 크기 n
- y축 (log scale) : 평균 실행 시간(초),
- 에러바(Error bar): 표준오차(SE)
☞ 해석:
- 버블/선택/삽입(O(n²) 계열)이 병합/퀵/힙(O(n log n) 계열)에 비해 n이 커질수록 빠르게 위쪽으로 벌어집니다.
- 평균 실행 시간 그래프의 기울기가 이론상의 n² vs n log n 패턴과 잘 부합합니다. 즉, 이론적인 Big-O 그래프와 실제 테스트 결과가 유사한 경향성을 보여줍니다.
4-3. SE vs repeats
[그래프 3] SE vs repeats (at n = 100)
- x축 (log scale) : 반복 횟수(repeats)
- y축 (log scale) : 표준오차(SE)
반복 횟수를 5 → 10 → 20 → … → 2000으로 늘려 가면, SE가 대체로 1/√k 형태로 줄어드는 경향이 있음을 확인할 수 있습니다.
- 반복을 4배 늘리면 SE는 절반 정도로 감소함.
- 충분히 큰 repeats를 사용하면 "평균 실행 시간"이 안정적인 값으로 수렴함.
반복 횟수가 늘어나면 각 측정값의 산포(표준편차)는 비슷하더라도, 평균값의 표준오차(SE)가 1/√k 비율로 감소합니다. 즉 같은 알고리즘을 여러 번, 가능하면 충분히 큰 횟수로 반복 측정하여 평균과 SE를 함께 보면, 한 번 또는 적은 횟수로 측정했을 때보다 평균 실행 시간의 정확도(accuracy)가 높아지고, 값의 재현성·일관성이라는 정밀도(precision)도 함께 확보할 수 있습니다.
이런 방식으로 동일한 조건에서 코드를 여러 번 실행해 실행 시간, 메모리 사용량 등을 수치로 비교, 평가하는 실험을 흔히 '벤치마크(benchmark)'라고 부릅니다. 벤치마크를 통해 이론적인 복잡도 분석만으로는 알기 어려운 실제 성능 차이를 확인할 수 있고, 여러 알고리즘 후보 중에서 어떤 구현을 선택할지 보다 근거 있는 결정을 내릴 수 있습니다.
5. 동적 프로그래밍(DP)
5-1. DP의 정의와 분할 정복과의 차이
분할 정복(Divide & Conquer)
- 하나의 큰 문제를 서로 겹치지 않는(subproblems disjoint) 여러 개의 작은 문제로 나눈 뒤(쪼갠 뒤), 각 작은 문제를 같은 방법(같은 알고리즘)으로 해결하고, 마지막에 이 부분 결과들을 합쳐서 전체 해답을 만드는 방식입니다.
- 핵심 키워드 : 기억하며 풀기, 중복 계산 제거, 부분 문제 결과 재사용.
- 예: 병합 정렬, 퀵 정렬 - 재귀적(recursive)의 개념 : '함수가 자기 자신을 다시 호출하면서, 입력 크기를 점점 줄여 가는 방식' 같은 방법으로 계속 풀어내는 것을 말합니다.
- 예를 들어 병합 정렬에서는 배열을 절반씩 나누어(큰 문제 → 작은 배열 정렬 문제), 그 작은 배열도 다시 같은 병합 정렬 함수로 정렬하고, 더 이상 나눌 수 없는 크기(원소 1개 등)에 도달하면 그 값을 그대로 되돌린 뒤, 이 작은 결과들을 차례대로 합치는 과정(merge) 을 통해 전체 배열을 정렬합니다.
동적 프로그래밍(Dynamic Programming)
- 큰 문제를 작은 문제로 쪼갠다는 점은 비슷하지만, 부분 문제가 서로 겹친다는 것이 핵심입니다.
- 같은 부분 문제가 여러 번 등장하면, 한 번 계산한 결과를 테이블에 저장해 재사용합니다.
☞ 시간 절약, 대신 메모리 사용 - DP가 잘 맞는 문제의 특징 두 가지:
1. 중복 부분 문제(Overlapping Subproblems) : 같은 계산을 반복하는 재귀 구조가 보임.
2. 최적 부분 구조(Optimal Substructure) : 전체 문제의 최적해가, 부분 문제들의 최적해로부터 구성됨.
☞ 분할 정복과 동적 프로그래밍의 차이점
| 항목 | 분할 정복(D&C) | 동적 프로그래밍(DP) |
| 부분 문제 | 중복 없음 | 겹침(중복) 발생 |
| 결과 저장 | 저장 안 함 | 저장함 (재사용) |
| 방식 | 정렬, 탐색 등 일반 문제 | 최적화 문제에 유리 |
| 대표 예 | 퀵소트, 합병정렬 | 피보나치, 배낭 문제 등 |
5-2. 메모이제이션과 바텀업
- 메모이제이션(Memoization)
- 함수 호출 결과를 캐시에 저장해 두고, 같은 입력이 다시 오면 저장된 결과를 가져다 쓰는 방식 - Top-Down 방식
- 큰 문제에서 작은 문제 순서로 재귀 호출하며 내려가는 방식으로 메모이제이션과 함께 사용됨.
- 재귀 함수 + 캐시(딕셔너리/리스트)를 사용하고 필요한 부분 문제만 계산한다. - 바텀업 (Bottom-Up) 방식
- 작은 문제부터 차례대로 값을 채워 올라가는 방식으로 재귀 방식이 없고 보통 반복문(for)으로 구현.
- 재귀 호출 스택이 없어 안정적이다.
- 이번 글에서 구현한 Fibonacci, 계단 오르기, Knapsack은 모두 바텀업 DP 방식.
5-3. Fibonacci DP
점화식: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2)
단순 재귀는 같은 값을 반복 계산하므로 O(2ⁿ) 시간입니다.
바텀업 DP는 다음처럼 작성할 수 있습니다.
def fib_dp(n):
dp = [0] * (n+1)
if n >= 1:
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]- 시간 복잡도: O(n)
- 공간 복잡도: O(n) (필요하면 두 칸만 남기고 O(1)로 줄일 수 있음)
5-4. 계단 오르기(Climb Stairs)
한 번에 1계단 또는 2계단씩 올라갈 수 있을 때, n계단을 올라가는 서로 다른 방법의 수를 구하는 문제입니다.
점화식: ways[1] = 1, ways[2] = 2, ways[i] = ways[i−1] + ways[i−2]
Fibonacci와 동일한 형태입니다.
def climb_stairs(n):
if n <= 2:
return n
dp = [0]*(n+1)
dp[1], dp[2] = 1, 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]- 시간 복잡도: O(n)
- 공간 복잡도: O(n) 또는 O(1)
5-5. 0/1 Knapsack (배낭 문제)
무게 제한 W짜리 배낭과, 각각 무게 wᵢ와 가치 vᵢ를 가진 물건 n개가 있을 때, 일부 물건을 선택하여 총 무게 ≤ W 를 만족하면서
가치를 최대로 하는 문제입니다.
1차원 바텀업 DP:
def knapsack_01(weights, values, W):
dp = [0] * (W+1)
for wt, val in zip(weights, values):
for w in range(W, wt-1, -1):
dp[w] = max(dp[w], dp[w-wt] + val)
return dp[W]- 시간 복잡도: O(nW)
- 공간 복잡도: O(W)
재귀로 모든 경우를 탐색하면 O(2ⁿ) 시간이지만, DP를 사용하면 가능한 모든 무게 w에 대해 최적값을 저장하면서 O(nW)로 줄일 수 있습니다.
6. 정렬 vs DP 비교 (장단점, 특징)
마지막으로, 정렬 알고리즘과 동적 프로그래밍을 복잡도와 구조 관점에서 비교해 봅니다.
| 관점 | 정렬 알고리즘 | 동적 프로그래밍(DP) |
| 주 목적 | 데이터의 순서를 정렬 | 최댓값/최솟값, 경우의 수, 최소 비용 등 최적화 |
| 대표 복잡도 | O(n log n), O(n²) | O(n), O(nW), O(n²) 등 문제에 따라 다양 |
| 핵심 아이디어 | 비교/교환 패턴 최적화, 분할 정복, 힙 구조 | 중복 부분 문제 + 최적 부분 구조 + 테이블 |
| 공간 사용 | 보통 O(1)~O(n) | dp 테이블 크기에 따라 O(n), O(W), O(nW) |
| 전형적인 예제 | Bubble, Selection, Insertion, Merge, Quick, Heap | Fibonacci, 계단 오르기, 0/1 Knapsack 등 |
- 정렬은 순서 자체가 목적이며, 입력이 커질수록 O(n log n) 알고리즘이 실질적 표준입니다.
- DP는 최적화 문제에서 자주 등장하며, '시간을 줄이기 위해 메모리를 투자하는' 전형적인 패턴입니다.
7. 요약: 알고리즘, 복잡도, 프로그램 효율성
- 시간 복잡도와 공간 복잡도는 알고리즘을 수학적으로 비교할 수 있게 해 줍니다.
☞ O(n log n)과 O(n²)의 차이는 n이 커질수록 "몇 배"가 아니라 "몇 만 배"의 차이가 됩니다. - 정렬 알고리즘 6종을 서로 비교하면서, 각 알고리즘의 코드 구조가 시간 복잡도에 어떻게 연결되는지를 살펴보았고, 그 결과가 Big-O 이론 그래프와 실제 실행 시간 Mean ± SE 그래프에서 거의 같은 패턴으로 나타난다는 점도 함께 확인했습니다.
- 표준편차(SD) 와 표준오차(SE) 를 통해 알고리즘 성능 측정 결과의 신뢰도를 수치로 표현할 수 있었습니다.
☞ 평균 실행 시간을 비교할 때는 개별 값의 흩어짐(SD)보다 평균의 불확실성(SE)을 보는 것이 더 적절합니다. - 동적 프로그래밍(DP) 예제(Fibonacci, 계단 오르기, 0/1 배낭)를 통해, 같은 문제를 단순 재귀나 완전 탐색으로 풀 때보다 훨씬 적은 연산으로 해결할 수 있고, 특히 '한 번 계산한 부분 결과를 저장해 두었다가 재사용하면 전체 실행 시간이 크게 줄어든다' 는 점을 확인할 수 있습니다.
☞ 피보나치 수를 단순 재귀로 계산하면 같은 값을 계속 다시 계산해야 하지만, DP를 쓰면 각 n에 대한 값을 정확히 한 번씩만 계산하면 되어, 실행 시간이 눈에 띄게 감소합니다. - 실제 코딩에서는 문제 유형(정렬, 그래프, DP 등)을 먼저 분류한 다음, 복잡도가 낮은 알고리즘을 선택하고, 필요할 경우 여러 번 벤치마크를 수행해 평균 실행 시간과 SE를 함께 확인하는 습관이 중요합니다.
☞ 입력 규모가 커져도 성능과 안정성을 유지할 수 있는 코드를 설계·구현하려면, 시간·공간 복잡도와 알고리즘 선택, 전반적인 프로그래밍 효율성을 함께 고려하는 것이 매우 중요하다는 사실을 알게 되었습니다. 이번에 정렬 알고리즘과 동적 프로그래밍을 공부하면서, 새로운 문제를 만났을 때 어떤 알고리즘을 선택할지, 그리고 그 선택의 성능을 어떻게 검증할지를 늘 염두에 두고, 그 기준을 스스로 설명할 수 있어야 한다는 점을 깨닫게 된 유익한 학습 경험이었습니다.
즐거운 파이썬~ 즐 파이씽~
[주의] 내용에 오류가 있을 수 있습니다.
[코드] [그래프 1] Big-O Complexity Comparison
import os
import numpy as np
import math
import matplotlib.pyplot as plt
# Jupyter/Colab에서 그래프를 셀 아래에 바로 표시하기 위한 매직 명령
%matplotlib inline
#---------------------------------------------------------------
# 글꼴/마이너스 깨짐 방지 (기본 폰트 사용)
plt.rcParams["font.family"] = "DejaVu Sans" # 한글이 들어가도 깨지지 않는 기본 폰트 설정
plt.rcParams["axes.unicode_minus"] = False # 축에 음수 부호(-)가 깨지지 않도록 설정
# 1) x 범위 설정
# - Big-O 함수들을 그릴 독립 변수 n 역할
# - 0.5 ~ 10.5 사이를 2000개의 점으로 잘게 나누어 부드러운 곡선을 그리기 위함
x = np.linspace(0.5, 10.5, 2000)
# 2) Big-O 함수들 정의
# 각 Big-O 표기법에 해당하는 "성장 함수"를 직접 수식으로 만든 것
y_log = np.log(x) # O(log n)
y_n = x # O(n)
y_nlogn = x * np.log(x) # O(n log n)
y_n2 = x**2 # O(n^2)
y_2n = 2**x # O(2^n)
y_fact = np.array([math.factorial(int(v)) for v in x]) # O(n!)
# factorial은 정수에 대해서만 정의되므로, x의 값을 int로 변환해서 사용
# 예: x가 3.7이면 int(3.7) = 3 이고, math.factorial(3) = 6
# 3) 그래프 스타일 설정
# - figure(figsize=(가로, 세로)) : 그래프 전체의 크기(인치 단위)
plt.figure(figsize=(12, 8))
# 4) 각 함수 그리기
# - label 파라미터는 나중에 legend(범례)에 표시될 이름
plt.plot(x, y_log, label="O(log n)")
plt.plot(x, y_n, label="O(n)")
plt.plot(x, y_nlogn, label="O(n log n)")
plt.plot(x, y_n2, label="O(n^2)")
plt.plot(x, y_2n, label="O(2^n)")
plt.plot(x, y_fact, label="O(n!)")
# 5) 그래프 제목과 축 이름 설정
plt.title("Big-O Complexity Comparison", fontsize=15) # 그래프 전체 제목
plt.xlabel("n (Elements)", fontsize=14) # x축 이름: 입력 크기 n
plt.ylabel("Operations", fontsize=14) # y축 이름: 연산 횟수(상대적 크기)
# 6) 범례 + 로그 스케일 + 그리드
# - y축을 log 스케일로 바꾸면, 서로 크기 차이가 큰 함수들도 한 화면에서 비교하기 좋음
plt.yscale("log") # 세로축을 log scale로 설정 → 매우 큰 값들도 함께 표시 가능
plt.grid(True, which="both", ls="--", alpha=0.4) # 눈금을 보기 좋게 점선 그리드 추가
plt.legend(fontsize=12) # 위에서 지정한 label들을 이용해 범례 표시
# 7) 최종적으로 그래프 화면에 출력
plt.show()
[코드] [그래프 2] All Sorting Algorithms – Mean ± SE
[코드] [그래프 3] SE vs repeats at n = 100
# Reset matplotlib font settings to default
import matplotlib as mpl
mpl.rcdefaults() # 이전에 바꿔둔 matplotlib 설정을 기본값으로 초기화
#====================================================================
# STEP 1 ─ 기본 라이브러리 import
import random # 난수(무작위 배열 생성)
import time # 실행 시간 측정
import statistics # 평균, 표준편차 계산
import math # 수학 함수 (sqrt 등)
import os # 파일/디렉터리 경로 작업
import pandas as pd
import matplotlib.pyplot as plt
# 주피터/코랩에서 그래프를 셀 아래에 바로 표시
%matplotlib inline
#====================================================================
# STEP 2 ─ 정렬 알고리즘 구현 (core 버전만 사용: 벤치마크용)
class SortStepRecorder:
"""벤치마크용 정렬 알고리즘 핵심 구현 (단계 기록/애니메이션 없음)"""
#---------------------------------------------------------------
@staticmethod
def bubble_core(arr):
# 버블 정렬: 인접한 두 원소를 비교/교환
a = arr[:] # 원본 보존
n = len(a)
for i in range(n):
swapped = False
for j in range(0, n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 교환이 없으면 이미 정렬 → 조기 종료
break
return a
#---------------------------------------------------------------
@staticmethod
def selection_core(arr):
# 선택 정렬: 매 단계마다 최솟값을 찾아 앞으로 보냄
a = arr[:]
n = len(a)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
return a
#---------------------------------------------------------------
@staticmethod
def insertion_core(arr):
# 삽입 정렬: 정렬된 앞부분에 새 원소를 끼워 넣음
a = arr[:]
for i in range(1, len(a)):
key = a[i]
j = i - 1
# key보다 큰 원소들을 한 칸씩 뒤로 밀기
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
#---------------------------------------------------------------
@staticmethod
def merge_core(arr):
# 병합 정렬: 배열을 반으로 나누고 정렬 후 병합
if len(arr) <= 1:
return arr[:]
mid = len(arr) // 2
left = SortStepRecorder.merge_core(arr[:mid])
right = SortStepRecorder.merge_core(arr[mid:])
return SortStepRecorder._merge_lists(left, right)
#---------------------------------------------------------------
@staticmethod
def _merge_lists(left, right):
# 두 정렬된 리스트를 하나의 정렬된 리스트로 병합
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
# 남은 원소들 이어붙이기
result.extend(left[i:])
result.extend(right[j:])
return result
#---------------------------------------------------------------
@staticmethod
def quick_core(arr):
# 퀵 정렬: 피벗을 기준으로 작은/같은/큰 그룹으로 분할
if len(arr) <= 1:
return arr[:]
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return (SortStepRecorder.quick_core(left) +
equal +
SortStepRecorder.quick_core(right))
#---------------------------------------------------------------
@staticmethod
def heap_core(arr):
# 힙 정렬: 최대 힙을 구성한 뒤, 루트를 끝으로 보내며 정렬
a = arr[:]
n = len(a)
def heapify(n, i):
# 인덱스 i를 루트로 하는 부분 트리를 최대 힙으로 만들기
largest = i
l = 2*i + 1
r = 2*i + 2
if l < n and a[l] > a[largest]:
largest = l
if r < n and a[r] > a[largest]:
largest = r
if largest != i:
a[i], a[largest] = a[largest], a[i]
heapify(n, largest)
# 1단계: 배열을 최대 힙으로 변환
for i in range(n // 2 - 1, -1, -1):
heapify(n, i)
# 2단계: 루트(최댓값)를 끝으로 보내고 힙 크기 줄이기
for i in range(n - 1, 0, -1):
a[0], a[i] = a[i], a[0]
heapify(i, 0)
return a
#====================================================================
# STEP 2-1 ─ 벤치마크에서 사용할 알고리즘 딕셔너리
ALGORITHMS = {
"bubble": SortStepRecorder.bubble_core,
"selection": SortStepRecorder.selection_core,
"insertion": SortStepRecorder.insertion_core,
"merge": SortStepRecorder.merge_core,
"quick": SortStepRecorder.quick_core,
"heap": SortStepRecorder.heap_core,
}
#====================================================================
# STEP 3 ─ size 리스트와 repeats에 대해
# mean_time, se_time을 계산하는 벤치마크 함수
def benchmark_algorithms(sizes, repeats=5, seed=100):
rng = random.Random(seed) # 재현성을 위한 시드 고정
records = [] # 결과를 담을 리스트
for n in sizes:
# 동일한 난수 배열들을 미리 만들어 두고 모든 알고리즘이 공유
base_arrays = [
[rng.randint(0, n) for _ in range(n)]
for _ in range(repeats)
]
for algo_name, algo_func in ALGORITHMS.items():
times = []
for arr in base_arrays:
data = arr[:] # 원본 보존
t0 = time.perf_counter() # 시작 시간
algo_func(data) # 정렬 실행
t1 = time.perf_counter() # 종료 시간
times.append(t1 - t0)
# 평균, 표준편차, 표준오차 계산
mean_t = statistics.mean(times)
std_t = statistics.stdev(times) if repeats > 1 else 0.0
se_t = std_t / math.sqrt(repeats)
records.append({
"algorithm": algo_name,
"n": n,
"mean_time": mean_t,
"se_time": se_t,
"repeats": repeats,
})
# pandas DataFrame으로 반환 (그래프/분석용)
return pd.DataFrame(records)
#====================================================================
# STEP 4 ─ size 하나를 고정하고 repeats를 바꿔가며
# se_time(SE)가 어떻게 줄어드는지 측정
def benchmark_se_vs_repeats(size, repeats_list, seed=42):
rng = random.Random(seed)
records = []
for repeats in repeats_list:
# 각 repeats에 대해 새로운 난수 배열들 생성
base_arrays = [
[rng.randint(0, size) for _ in range(size)]
for _ in range(repeats)
]
for algo_name, algo_func in ALGORITHMS.items():
times = []
for arr in base_arrays:
data = arr[:]
t0 = time.perf_counter()
algo_func(data)
t1 = time.perf_counter()
times.append(t1 - t0)
mean_t = statistics.mean(times)
std_t = statistics.stdev(times) if repeats > 1 else 0.0
se_t = std_t / math.sqrt(repeats)
records.append({
"algorithm": algo_name,
"n": size,
"repeats": repeats,
"mean_time": mean_t,
"se_time": se_t,
})
return pd.DataFrame(records)
#====================================================================
# STEP 5 ─ 색상 매핑 및 figure 생성 함수들
color_map = {
"bubble": "red",
"selection": "orange",
"insertion": "hotpink",
"merge": "blue",
"quick": "green",
"heap": "purple",
}
algo_order = ["bubble", "selection", "insertion", "merge", "quick", "heap"]
def create_mean_se_figure(df, sizes, repeats):
"""정렬 알고리즘별 mean ± SE vs n (로그-로그) 그래프 생성"""
fig, ax = plt.subplots(figsize=(10, 6))
for algo in algo_order:
# 해당 알고리즘 행만 골라서 n 순서대로 정렬
sub = df[df["algorithm"] == algo].sort_values("n")
sub = sub[sub["n"].isin(sizes)]
if sub.empty:
continue
ax.errorbar(
sub["n"],
sub["mean_time"],
yerr=sub["se_time"], # 에러바에 SE 사용
marker="o",
capsize=3,
label=algo,
color=color_map.get(algo)
)
ax.set_xscale("log")
ax.set_yscale("log")
ax.set_xlabel("Input size n (log scale)")
ax.set_ylabel("Mean running time (seconds, log scale)")
ax.set_title(f"All Sorting Algorithms – Mean ± SE (repeats = {repeats})")
ax.grid(True, which="both", linestyle="--", alpha=0.4)
ax.legend()
fig.tight_layout()
return fig, ax
def create_se_vs_repeats_figure(df_se, size):
"""고정된 n에서 repeats에 따른 SE 변화를 그리는 그래프"""
fig, ax = plt.subplots(figsize=(10, 6))
for algo in algo_order:
sub = df_se[df_se["algorithm"] == algo].sort_values("repeats")
if sub.empty:
continue
ax.plot(
sub["repeats"],
sub["se_time"],
marker="o",
label=algo,
color=color_map.get(algo)
)
ax.set_xscale("log")
ax.set_yscale("log")
ax.set_xlabel("repeats (log scale)")
ax.set_ylabel("Standard Error of mean_time (log scale)")
ax.set_title(f"SE vs repeats at n = {size} (all algorithms)")
ax.grid(True, which="both", linestyle="--", alpha=0.4)
ax.legend()
fig.tight_layout()
return fig, ax
#====================================================================
# STEP 6 ─ Mean ± SE 그래프 출력 (그리기 전용)
SIZES = [10, 20, 30, 40, 50, 60, 80, 100,
120, 150, 200, 250, 300, 400, 500, 600,
800, 1000, 1500, 2000, 3000, 4000, 5000,
7000, 10000]
REPEATS = 5
df_mean_se = benchmark_algorithms(SIZES, repeats=REPEATS)
fig1, ax1 = create_mean_se_figure(df_mean_se, SIZES, REPEATS)
plt.show(fig1) # Mean ± SE vs n 그래프 화면에 출력
#====================================================================
# STEP 6-2 ─ SE vs repeats 그래프 출력 (그리기 전용)
REPEATS_LIST = [5, 10, 20, 50, 100, 200, 500, 1000, 2000]
SIZE = 100
df_se = benchmark_se_vs_repeats(SIZE, REPEATS_LIST)
fig2, ax2 = create_se_vs_repeats_figure(df_se, SIZE)
plt.show(fig2) # SE vs repeats 그래프 화면에 출력
[코드] 정렬 알고리즘 6가지 (+애니메이션 그래프)
[코드] 동적 프로그래밍 3가지 (+애니메이션 그래프)
#====================================================================
# STEP 1 ─ import하기
import os
import random
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import animation
from matplotlib.animation import PillowWriter
from IPython.display import HTML
# 그래프/애니메이션 바로 표시
%matplotlib inline
# 기본 폰트 설정 (한글/마이너스 깨짐 방지)
plt.rcParams["font.family"] = "DejaVu Sans"
plt.rcParams["axes.unicode_minus"] = False
#====================================================================
# STEP 2 ─ 정렬용 StepRecorder (버블/선택/삽입/병합/퀵/힙)
class SortStepRecorder:
"""
정렬 알고리즘 6종
- 각 단계에서 배열 상태 + '관심 인덱스(active)'를 step으로 기록
step: {"values": [...], "active": [i, j, ...]}
"""
@staticmethod
def _make_step(a, active=None):
"""현재 배열 상태와 강조할 인덱스를 하나의 step으로 포장"""
return {
"values": a[:],
"active": [] if active is None else list(active),
}
#----------------------------------------------------------------------
# 1) Bubble Sort
@classmethod
def bubble(cls, arr):
"""버블 정렬: 인접한 두 원소를 비교/교환하며 큰 값을 뒤로 보냄"""
a = arr[:]
n = len(a)
steps = [cls._make_step(a, active=[])]
for i in range(n):
swapped = False
for j in range(0, n - 1 - i):
# 비교하는 두 인덱스를 active로 표시
steps.append(cls._make_step(a, active=[j, j+1]))
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
swapped = True
# 교환 후 상태도 기록
steps.append(cls._make_step(a, active=[j, j+1]))
if not swapped: # 더 이상 교환이 없으면 조기 종료
break
return steps
#----------------------------------------------------------------------
# 2) Selection Sort
@classmethod
def selection(cls, arr):
"""선택 정렬: 구간마다 최솟값 위치를 찾아 앞으로 교환"""
a = arr[:]
n = len(a)
steps = [cls._make_step(a, active=[])]
for i in range(n):
min_idx = i
for j in range(i+1, n):
# 현재 i와 탐색 중인 j를 강조
steps.append(cls._make_step(a, active=[i, j]))
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
# 교환 직전/직후 상태 기록
steps.append(cls._make_step(a, active=[i, min_idx]))
a[i], a[min_idx] = a[min_idx], a[i]
steps.append(cls._make_step(a, active=[i, min_idx]))
return steps
#----------------------------------------------------------------------
# 3) Insertion Sort (key가 왼쪽으로 한 칸씩 이동하는 느낌)
@classmethod
def insertion(cls, arr):
"""삽입 정렬: 정렬된 구간에 key를 알맞은 위치로 삽입"""
a = arr[:]
steps = [cls._make_step(a, active=[])]
n = len(a)
for i in range(1, n):
j = i
# key 선택 단계
steps.append(cls._make_step(a, active=[j]))
while j > 0 and a[j-1] > a[j]:
# 비교하는 두 원소 표시
steps.append(cls._make_step(a, active=[j-1, j]))
# 인접 swap
a[j-1], a[j] = a[j], a[j-1]
steps.append(cls._make_step(a, active=[j-1, j]))
j -= 1
# key가 최종 자리로 들어간 상태
steps.append(cls._make_step(a, active=[j]))
return steps
#----------------------------------------------------------------------
# 4) Merge Sort
@classmethod
def merge(cls, arr):
"""병합 정렬: 반으로 나누어 재귀 정렬 후 병합"""
a = arr[:]
steps = [cls._make_step(a, active=[])]
def _merge_sort(lo, hi):
"""구간 [lo, hi) 를 병합 정렬"""
if hi - lo <= 1:
return
mid = (lo + hi) // 2
_merge_sort(lo, mid)
_merge_sort(mid, hi)
_merge_inplace(lo, mid, hi)
def _merge_inplace(lo, mid, hi):
"""두 정렬된 구간 [lo, mid), [mid, hi) 를 병합"""
temp = []
i, j = lo, mid
while i < mid and j < hi:
# 비교 중인 두 인덱스를 강조
steps.append(cls._make_step(a, active=[i, j]))
if a[i] <= a[j]:
temp.append(a[i]); i += 1
else:
temp.append(a[j]); j += 1
# 남은 부분 붙이기
while i < mid:
temp.append(a[i]); i += 1
while j < hi:
temp.append(a[j]); j += 1
# 병합 결과를 원배열에 덮어쓰면서 매 단계 기록
for k, val in enumerate(temp):
a[lo + k] = val
steps.append(cls._make_step(a, active=[lo + k]))
_merge_sort(0, len(a))
return steps
#----------------------------------------------------------------------
# 5) Quick Sort
@classmethod
def quick(cls, arr):
"""퀵 정렬: 피벗 기준으로 분할한 뒤 재귀 정렬"""
a = arr[:]
steps = [cls._make_step(a, active=[])]
def _quick(lo, hi):
"""구간 [lo, hi] 퀵 정렬"""
if lo >= hi:
return
p = _partition(lo, hi)
_quick(lo, p-1)
_quick(p+1, hi)
def _partition(lo, hi):
"""구간 [lo, hi] 를 피벗 기준으로 분할"""
pivot = a[hi]
i = lo
for j in range(lo, hi):
# 현재 비교 중인 j와 피벗 hi 강조
steps.append(cls._make_step(a, active=[j, hi]))
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
steps.append(cls._make_step(a, active=[i, j]))
i += 1
# 피벗을 최종 위치로 이동
a[i], a[hi] = a[hi], a[i]
steps.append(cls._make_step(a, active=[i, hi]))
return i
if len(a) > 1:
_quick(0, len(a)-1)
return steps
#----------------------------------------------------------------------
# 6) Heap Sort
@classmethod
def heap(cls, arr):
"""힙 정렬: 최대 힙을 만든 뒤 루트를 끝으로 보내며 정렬"""
a = arr[:]
n = len(a)
steps = [cls._make_step(a, active=[])]
def heapify(size, i):
"""인덱스 i를 루트로 하는 부분트리를 최대 힙으로 정리"""
largest = i
l = 2*i + 1
r = 2*i + 2
if l < size:
steps.append(cls._make_step(a, active=[i, l]))
if a[l] > a[largest]:
largest = l
if r < size:
steps.append(cls._make_step(a, active=[largest, r]))
if a[r] > a[largest]:
largest = r
if largest != i:
a[i], a[largest] = a[largest], a[i]
steps.append(cls._make_step(a, active=[i, largest]))
heapify(size, largest)
# 1단계: 배열을 최대 힙으로 만들기
for i in range(n//2 - 1, -1, -1):
heapify(n, i)
# 2단계: 루트(최댓값)를 끝으로 보내고 힙 크기를 줄여가며 정렬
for i in range(n-1, 0, -1):
a[0], a[i] = a[i], a[0]
steps.append(cls._make_step(a, active=[0, i]))
heapify(i, 0)
return steps
#====================================================================
# STEP 3 ─ SortAnimator: 스무스 좌우 이동 + 색상 강조
class SortAnimator:
"""
steps: 정렬 과정에서 기록된 스텝 리스트
- 각 원소는 {"values": [...], "active": [i, j, ...]} 형태
- values: 배열의 상태
- active: 현재 비교/교환에 참여하는 인덱스들
역할:
1) steps 사이의 변화(특히 두 원소 교환)를 분석해서
2) 막대가 좌우로 자연스럽게 이동하는 중간 프레임을 만들고
3) FuncAnimation으로 GIF/HTML 애니메이션 생성
"""
def __init__(self, steps, title="Sorting Animation", smooth_steps=5):
self.steps = steps # 원본 step 리스트
self.title = title # 그래프 제목
self.smooth_steps = smooth_steps # swap 사이에 넣을 중간 프레임 수
self.frames = self._build_frames() # 실제 애니메이션용 프레임들
def _build_frames(self):
"""step 리스트를 기반으로 중간 프레임까지 포함한 frames 생성"""
if not self.steps:
return []
frames = []
n = len(self.steps[0]["values"])
# 첫 프레임: 초기 상태
first = self.steps[0]
frames.append({
"x": list(range(n)),
"heights": first["values"][:],
"active": first.get("active", [])[:],
})
# 인접 step 쌍을 보면서 swap 여부 판단 + 중간 프레임 생성
for idx in range(len(self.steps) - 1):
s0 = self.steps[idx]
s1 = self.steps[idx + 1]
v0 = s0["values"]
v1 = s1["values"]
a0 = set(s0.get("active", []))
a1 = set(s1.get("active", []))
active_union = list(a0 | a1)
# 값이 달라진 인덱스 목록
diff = [i for i in range(n) if v0[i] != v1[i]]
is_swap = False
if len(diff) == 2:
i, j = diff
# 두 위치의 값이 서로 뒤바뀐 경우 swap으로 판단
if v0[i] == v1[j] and v0[j] == v1[i]:
is_swap = True
if is_swap:
# swap이면 두 막대의 x 좌표를 서서히 교환
i, j = sorted(diff)
h0 = v0[:]
for step in range(1, self.smooth_steps + 1):
t = step / (self.smooth_steps + 1)
x_positions = list(range(n))
x_positions[i] = (1 - t) * i + t * j
x_positions[j] = (1 - t) * j + t * i
frames.append({
"x": x_positions,
"heights": h0[:],
"active": active_union,
})
# 최종적으로 swap된 상태 추가
frames.append({
"x": list(range(n)),
"heights": v1[:],
"active": s1.get("active", [])[:],
})
else:
# swap이 아니라 단순 값 변경이면 그대로 한 프레임만 추가
frames.append({
"x": list(range(n)),
"heights": v1[:],
"active": s1.get("active", [])[:],
})
return frames
def animate(self, interval=120):
"""
frames를 기반으로 matplotlib 애니메이션 생성
- interval: 프레임 간 시간 간격(ms)
- 반환: (anim, fig)
"""
if not self.frames:
raise ValueError("frames 비어 있음")
fig, ax = plt.subplots(figsize=(7, 4))
fig.suptitle(self.title)
data0 = self.frames[0]
x0 = data0["x"]
h0 = data0["heights"]
# 초기 막대 그래프
bars = ax.bar(x0, h0, align="center")
# y축 범위 상한 설정 (최댓값의 약 1.1배)
max_val = max(max(f["heights"]) for f in self.frames)
ax.set_ylim(0, max_val * 1.1)
ax.set_xlabel("Frame")
ax.set_ylabel("Value")
base_color = "#cccccc"
active_colors = ["red", "orange", "purple"] # active 막대 색상들
def init():
"""애니메이션 초기 상태 설정"""
for rect, x, h in zip(bars, x0, h0):
rect.set_x(x - 0.4)
rect.set_width(0.8)
rect.set_height(h)
rect.set_color(base_color)
return bars
def update(frame_idx):
"""frame_idx 번째 프레임으로 막대 상태 업데이트"""
frame = self.frames[frame_idx]
xs = frame["x"]
hs = frame["heights"]
active = frame.get("active", [])
# 위치/높이 갱신
for i, rect in enumerate(bars):
rect.set_x(xs[i] - 0.4)
rect.set_height(hs[i])
# 색상 초기화
for rect in bars:
rect.set_color(base_color)
# active 인덱스에만 강조 색 적용
for k, idx in enumerate(active):
if 0 <= idx < len(bars):
color = active_colors[min(k, len(active_colors)-1)]
bars[idx].set_color(color)
ax.set_xlabel(f"Frame {frame_idx+1}/{len(self.frames)}")
return bars
anim = animation.FuncAnimation(
fig, update, init_func=init,
frames=len(self.frames),
interval=interval,
blit=True
)
return anim, fig
#====================================================================
# STEP 4 ─ 정렬 6종 애니메이션 생성 + 화면 출력 (저장은 아직 X)
# 데모용 난수 배열 생성
random.seed(0)
arr_demo = [random.randint(1, 50) for _ in range(10)]
print("원본 배열:", arr_demo)
#----------------------------------------------------------------------
# 1) Bubble
steps_bubble = SortStepRecorder.bubble(arr_demo)
anim_bubble, fig_bubble = SortAnimator(
steps_bubble, title="Bubble Sort", smooth_steps=10
).animate(interval=100)
HTML(anim_bubble.to_jshtml()) # 애니메이션 재생
#----------------------------------------------------------------------
# 2) Selection
steps_selection = SortStepRecorder.selection(arr_demo)
anim_selection, fig_selection = SortAnimator(
steps_selection, title="Selection Sort", smooth_steps=10
).animate(interval=200)
HTML(anim_selection.to_jshtml())
#----------------------------------------------------------------------
# 3) Insertion
steps_insertion = SortStepRecorder.insertion(arr_demo)
anim_insertion, fig_insertion = SortAnimator(
steps_insertion, title="Insertion Sort", smooth_steps=10
).animate(interval=100)
HTML(anim_insertion.to_jshtml())
#----------------------------------------------------------------------
# 4) Merge
steps_merge = SortStepRecorder.merge(arr_demo)
anim_merge, fig_merge = SortAnimator(
steps_merge, title="Merge Sort", smooth_steps=40 # 더 부드럽게(중간 프레임 많이)
).animate(interval=400) # 프레임 간 간격도 길게 → 천천히
HTML(anim_merge.to_jshtml())
#----------------------------------------------------------------------
# 5) Quick
steps_quick = SortStepRecorder.quick(arr_demo)
anim_quick, fig_quick = SortAnimator(
steps_quick, title="Quick Sort", smooth_steps=10
).animate(interval=150)
HTML(anim_quick.to_jshtml())
#----------------------------------------------------------------------
# 6) Heap
steps_heap = SortStepRecorder.heap(arr_demo)
anim_heap, fig_heap = SortAnimator(
steps_heap, title="Heap Sort", smooth_steps=10
).animate(interval=150)
HTML(anim_heap.to_jshtml())
#====================================================================
# STEP 5 ─ DP용 StepRecorder 3종 (Fibonacci / Climb Stairs / Knapsack)
class DPStepRecorder:
#----------------------------------------------------------------------
@staticmethod
def _make_step(a, active=None, info=""):
"""DP 배열 상태 + 강조할 인덱스 + 설명 문자열을 한 단계(step)로 묶어 반환"""
return {
"values": a[:], # 현재 dp 배열 값 복사
"active": [] if active is None else list(active), # 강조할 인덱스들
"info": str(info), # 현재 단계 설명 텍스트
}
#----------------------------------------------------------------------
@classmethod
def fibonacci_bottom_up(cls, n):
"""피보나치 수를 바텀업 DP로 계산하면서 각 단계 상태를 기록"""
dp = [0]*(n+1) # dp[i] = F(i)
dp[0] = 0
steps = [cls._make_step(dp, active=[0], info="F(0)=0")]
if n >= 1:
dp[1] = 1
steps.append(cls._make_step(dp, active=[1], info="F(1)=1"))
# F(i) = F(i-1) + F(i-2)를 앞에서부터 채워 나감
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
info = f"F({i}) = F({i-1}) + F({i-2}) = {dp[i-1]} + {dp[i-2]} = {dp[i]}"
steps.append(cls._make_step(dp, active=[i, i-1, i-2], info=info))
return steps
#----------------------------------------------------------------------
@classmethod
def climb_stairs_bottom_up(cls, n):
"""계단 오르기(한 번에 1 or 2칸) 경우의 수를 바텀업 DP로 계산"""
dp = [0]*(n+1) # dp[i] = i번째 계단까지 가는 방법 수
steps = [cls._make_step(dp, active=[0], info="init dp[0]=0")]
if n >= 1:
dp[1] = 1 # 1칸 계단: 경우의 수 1
steps.append(cls._make_step(dp, active=[1], info="dp[1]=1"))
if n >= 2:
dp[2] = 2 # 2칸 계단: (1+1), (2) → 2가지
steps.append(cls._make_step(dp, active=[2], info="dp[2]=2"))
# dp[i] = dp[i-1] + dp[i-2] 규칙으로 채움
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
info = f"dp[{i}] = dp[{i-1}] + dp[{i-2}] = {dp[i-1]} + {dp[i-2]} = {dp[i]}"
steps.append(cls._make_step(dp, active=[i, i-1, i-2], info=info))
return steps
#----------------------------------------------------------------------
@classmethod
def knapsack_01_bottom_up(cls, weights, values, capacity):
"""
0/1 배낭 문제(1차원 배열 사용) 바텀업 DP
- weights[i], values[i]: i번째 물건의 무게/가치
- capacity(W): 배낭이 버틸 수 있는 최대 무게
- dp[w]: 무게 한도 w일 때 얻을 수 있는 최대 가치
"""
n = len(weights)
W = capacity
dp = [0]*(W+1)
steps = [cls._make_step(dp, active=[], info="init dp[w]=0")]
# i번째 물건까지 고려하면서 dp 갱신
for i in range(1, n+1):
wt = weights[i-1] # 현재 물건의 무게
val = values[i-1] # 현재 물건의 가치
# 1차원 배열을 사용할 때는 w를 뒤에서 앞으로 내려와야 이전 상태가 덮어쓰이지 않음
for w in range(W, wt-1, -1):
not_take = dp[w] # 현재 물건을 안 담는 경우
take = dp[w-wt] + val # 현재 물건을 담는 경우
new_val = max(not_take, take)
info1 = f"item{i}(wt={wt}, val={val}), w={w}"
# 비교 중인 w 인덱스를 강조
steps.append(cls._make_step(dp, active=[w], info=info1))
dp[w] = new_val # 더 큰 가치로 갱신
info2 = f"dp[{w}] = {new_val}"
steps.append(cls._make_step(dp, active=[w], info=info2))
return steps
#====================================================================
# STEP 5-2 ─ DPAnimator: 값 변화 smooth하게 개선
class DPAnimator:
"""
DP 배열이 갱신되는 과정을 막대 그래프 애니메이션으로 시각화하는 클래스.
- steps: DPStepRecorder에서 만든 step 리스트
(각 step은 {"values": [...], "active": [...], "info": "..."} 형태)
"""
def __init__(self, steps, title="DP Animation", smooth_steps=3):
self.raw_steps = steps # 원본 DP 단계 기록
self.title = title # 그래프 제목
self.smooth_steps = smooth_steps # 두 step 사이 보간 프레임 수
self.frames = self._generate_smooth_frames() # 실제 애니메이션에 사용할 프레임 리스트
def _generate_smooth_frames(self):
"""이산적인 step 사이에 선형 보간 프레임을 생성하여 부드러운 변화 구현"""
frames = [self.raw_steps[0]]
for i in range(len(self.raw_steps) - 1):
s0 = self.raw_steps[i]
s1 = self.raw_steps[i+1]
v0 = np.array(s0["values"], float) # 이전 step 값
v1 = np.array(s1["values"], float) # 다음 step 값
a0 = set(s0.get("active", []))
a1 = set(s1.get("active", []))
active_union = list(a0 | a1) # 두 단계에서 강조된 인덱스 합집합
info1 = s1.get("info", "") # 다음 단계 설명 텍스트
# 0~1 사이 t에 대해 선형 보간: (1-t)*v0 + t*v1
for t in np.linspace(0, 1, self.smooth_steps, endpoint=False):
vals = (1-t)*v0 + t*v1
frames.append({
"values": vals.tolist(),
"active": active_union,
"info": info1,
})
# 마지막에는 실제 다음 step 추가
frames.append(s1)
return frames
def animate(self, interval=160):
"""frames를 이용해 matplotlib 애니메이션 객체(anim, fig)를 생성"""
frames = self.frames
fig, ax = plt.subplots(figsize=(8, 4))
fig.suptitle(self.title)
data0 = frames[0]["values"]
x = list(range(len(data0)))
bars = ax.bar(x, data0) # dp 배열을 막대 그래프로 표시
# y축 범위: 최대값의 약 1.2배로 설정
max_val = max(max(f["values"]) for f in frames)
ax.set_ylim(0, max_val*1.2 if max_val > 0 else 1)
base_color = "#cccccc" # 기본 막대 색
active_colors = ["red", "orange", "purple"] # 강조 색상들
def init():
"""애니메이션 초기 프레임 설정"""
for rect, h in zip(bars, data0):
rect.set_height(h)
rect.set_color(base_color)
ax.set_xlabel(frames[0].get("info", "")) # 아래쪽에 설명 표시
return bars
def update(frame_idx):
"""frame_idx번째 프레임에 맞춰 막대 높이/색상/설명 갱신"""
frame = frames[frame_idx]
values = frame["values"]
active = frame.get("active", [])
info = frame.get("info", "")
# 막대 높이 갱신
for rect, h in zip(bars, values):
rect.set_height(h)
# 모든 막대를 기본 색으로 초기화
for rect in bars:
rect.set_color(base_color)
# active 인덱스만 강조 색으로 칠하기
for k, idx in enumerate(active):
if 0 <= idx < len(bars):
color = active_colors[min(k, len(active_colors)-1)]
bars[idx].set_color(color)
ax.set_xlabel(info) # 현재 단계 설명을 x축 라벨로 표시
return bars
anim = animation.FuncAnimation(
fig, update, init_func=init,
frames=len(frames),
interval=interval, # 프레임 간 시간 간격(ms)
blit=True
)
return anim, fig
#====================================================================
# STEP 6 ─ DP 3종 애니메이션 생성 + 화면 출력 (저장은 아직 X)
#----------------------------------------------------------------------
# 1) Fibonacci
n_fib = 10
steps_fib = DPStepRecorder.fibonacci_bottom_up(n_fib) # DP 단계 기록 생성
anim_fib, fig_fib = DPAnimator(
steps_fib, title=f"Fibonacci Bottom-Up DP (n={n_fib})", smooth_steps=10
).animate(interval=150) # 애니메이션 생성
HTML(anim_fib.to_jshtml()) # 노트북에서 재생
#----------------------------------------------------------------------
# 2) Climb Stairs
n_stairs = 8
steps_stairs = DPStepRecorder.climb_stairs_bottom_up(n_stairs)
anim_stairs, fig_stairs = DPAnimator(
steps_stairs,
title=f"Climb Stairs Bottom-Up DP (n={n_stairs})",
smooth_steps=10,
).animate(interval=150)
HTML(anim_stairs.to_jshtml())
#----------------------------------------------------------------------
# 3) 0/1 Knapsack
weights = [1, 2, 3, 4, 5]
values = [2, 3, 4, 5, 6]
capacity = 9
steps_knap = DPStepRecorder.knapsack_01_bottom_up(weights, values, capacity)
anim_knap, fig_knap = DPAnimator(
steps_knap,
title=f"0/1 Knapsack Bottom-Up DP (W={capacity})",
smooth_steps=10,
).animate(interval=50)
HTML(anim_knap.to_jshtml())
'[Code] Study & Practice' 카테고리의 다른 글
| [Python] 알고리즘 상태 다이어그램 (Algorithm Phase Diagram) : 메모리 사용량, 실행 속도, 시간 복잡도로 비교하는 알고리즘 18종 (0) | 2025.11.29 |
|---|---|
| [Python] 탐색 알고리즘의 개념: 선형(Linear), 이진(Binary), 깊이 우선(DFS), 너비 우선(BFS) (0) | 2025.11.27 |
| [백준문제] 알람 시계(2884번), 좀 더 잘 풀어보기! - 45분 당기기? 부족하다! 알람 늦추기도 해보자. (0) | 2025.11.12 |
| [HTML,CSS] tistroy, 제목 글자 크기 수정하기 (0) | 2025.11.09 |
| [Python] MySQL & Jupyter 연동 - 객체지향 프로그래밍(OOP)을 활용한 DB 작업 프로그램 예제 (0) | 2025.11.05 |