탐욕적 선택 속성 : 매 순간 가장 최적의 선택을 하는 것이 최종 해답의 최적성을 보장하는 속성
최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해들로 구성될 수 있는 구조
장점
빠른 시간 복잡도 : 보통 정렬 O(n log n) + 선형 스캔 O(n) 등으로 매우 효율적이다.
메모리 적음 : 상태 저장(테이블) 필요성이 적다.(대부분 상수 또는 선형)
구현 쉬움 : 코드가 짧고 디버깅이 쉽다.
단점
항상 최적이 아니다 : 잘못된 그리디 규칙은 전혀 최적해를 주지 못한다.
증명 필요 : 그리디 방법이 최적임을 보이려면 교환 주장(exchange argument) 등으로 증명해야 한다.
문제 인식 필요 : 문제의 구조를 잘 파악하지 못하면 그리디를 적용하면 틀린 경우도 있다.
문제 유형
● 활동 선택 문제
활동 번호
시작 시간
종료 시간
A1
1
2
A2
3
4
A3
0
6
A4
5
7
A5
8
9
activities = [(1,2), (3,4), (0,6), (5,7), (8,9)]
activities.sort(key=lambda x: x[1]) # end time 순 정렬
result = []
current_end = 0
for start, end in activities:
if start >= current_end:
result.append((start, end))
current_end = end
print(result) # [(1,2), (3,4), (5,7), (8,9)]
● 거스름돈 계산
목표: 최소 개수의 동전으로 특정 금액을 만들기
전략: 큰 동전부터 최대한 사용
단계
사용 동전
남은 금액
동전 개수
500원 사용
1260 → 1260 // 500 = 2개
1260 - 1000 = 260
2개
100원 사용
260 → 260 // 100 = 2개
260 - 200 = 60
4개
50원 사용
60 → 60 // 50 = 1개
60 - 50 = 10
5개
10원 사용
10 → 10 // 10 = 1개
10 - 10 = 0
✅ 6개
coins = [500, 100, 50, 10]
target = 1260
count = 0
for coin in coins:
count += target // coin # 해당 동전을 최대 몇 개 쓸 수 있는가
target %= coin # 남은 잔돈 갱신
print(count) # 출력: 6
서로소 집합(Disjoint Set) 자료구조라고도 불리며, 주로 그래프에서 사이클을 판별하거나, 자료들의 연결 정보를 알고 싶을 때 사용
핵심
연산
설명
Find(x)
원소 x가 속한 집합의 대표(root)를 찾는다.
Union(a, b)
원소 a가 속한 집합과 b가 속한 집합을 합친다.
작동원리
1. 초기화 : 각 노드가 자기 자신을 부모로 갖는다.
↓
2. Find 함수 : 루트 노드(대표)를 찾는다
↓
3. Union 함수 : 두 집합을 하나로 합친다
# 유니온 파인드 기본 구조 예제
# 1. 초기화: 각 노드가 자기 자신을 부모로 갖는다.
parent = [0, 1, 2, 3, 4, 5] # 1~5번 노드 예시
# 2. Find 함수 — 루트 노드(대표)를 찾는다.
def find_parent(parent, x):
if parent[x] != x: # 부모가 자기 자신이 아니면
parent[x] = find_parent(parent, parent[x]) # 재귀로 루트를 찾고 경로 압축
return parent[x]
# 3. Union 함수 — 두 집합을 하나로 합친다.
def union_parent(parent, a, b):
a = find_parent(parent, a) # a의 루트 찾기
b = find_parent(parent, b) # b의 루트 찾기
if a < b:
parent[b] = a # 작은 번호를 부모로
else:
parent[a] = b
# 4. 사용 예시
union_parent(parent, 1, 2) # 1과 2 합치기
union_parent(parent, 2, 3) # 2와 3 합치기
# 5. 결과 확인
print(find_parent(parent, 3)) # → 1 (3의 대표)
print(parent) # 전체 부모 배열 출력 [0, 1, 1, 1, 4, 5]
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1): # 마지막은 이미 정렬됨
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([5, 3, 8, 4, 2]))
1-(2) 선택 정렬 (Selection Sort)
매 단계마다 최솟값(또는 최댓값)을 선택해서 앞(또는 뒤)으로 보내는 방식
특징: 교환 횟수가 적다. [시간 복잡도 : O(n²)]
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([5, 3, 8, 4, 2]))
1-(3) 삽입 정렬 (Insertion Sort)
앞에서부터 차례로, 적절한 위치에 삽입하면서 정렬.
특징: 거의 정렬된 배열에 매우 빠름. [시간 복잡도 : 평균 O(n²), 최선 O(n) ]
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key: # key보다 큰 원소들을 뒤로 민다
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(insertion_sort([5, 3, 8, 4, 2]))
2. 심화 정렬
2-(1) 퀵 정렬 (Quick Sort)
*피벗(Pivot)을 기준으로 작은 값과 큰 값으로 분할하여 재귀적으로 정렬 ( *피벗 : 배열을 두 그룹으로 나누는 기준 값 )
특징: 평균적으로 가장 빠른 정렬 중 하나. [시간 복잡도 : 평균 O(n log n), 최악 O(n²) ]
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # 가운데 원소를 피벗으로
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([5, 3, 8, 4, 2]))
