그리디 알고리즘
현재 상황에서 지금 당장 좋은것만 고르는 방법
현재 상황에서 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할수 있다는 것은 아님
최적의 해를 보장할 수 없을 때가 많지만 최적해에 가까운 값을 구할때 사용
ex) 거스름돈 문제
거스름돈으로 500원, 100원, 50원, 10원 동전이 무수히 많이 존재할때 손님에게 거슬러 줄 돈 N원을 최소 개수의 동전으로 주는 방법. 단, 거슬러 줘야 할 돈은 항상 10의 배수.
최적해를 빠르게 구하기 위해서 가장 큰 화폐 단위부터 거슬러줌
가장 큰 화폐부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 정당성이 필요함
⇒ 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이기 때문. 그렇지 않다면 정당한 방법이 아님.
n = 1260
count = 0
array = [500, 100, 50, 10]
for coin in array:
count+= n //coin
n%=coin
print(count)
Python
복사
시간복잡도: 화폐 개수가 K일때 O(K)
ex) 1이 될때까지
어떤 수 N이 1이 될때까지 다음의 두 과정중 하나를 반복적으로 수행한다.
두번째 연산은 N이 K로 나누어질때만 선택할 수 있다.
1.
N에서 1을 뺀다
2.
N을 K로 나눈다.
N과 K가 주어질 때 N이 1이 될때까지 수행해야하는 최소 횟수를 구해라.
1 ≤ N ≤ 100000, 2 ≤ K ≤ 100000 인 자연수
n,k = map(int, input().split())
count = 0
while(n != 1):
if(n % k == 0):
n = n//k
count+=1
else:
n-=1
count+=1
print(count)
Python
복사
최대한 많이 나누기를 수행해아함. 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 더 많이 줄일 수 있기 때문.
ex) 곱하기 혹은 더하기
각 자리가 숫자로만 이루어진 문자열 S가 주어졌을때 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 곱하기 혹은 더하기 연산자를 넣어 만들수 있는 가장 큰 수를 구해라.
모든 연산은 왼쪽부터 오른쪽으로 이루어진다.
data =input()
result = int(data[0])
for i in range(1, len(data)):
num = int(data[i])
if num <= 1 or result <= 1:
result+=num
else:
result*=num
print(result)
Python
복사
일반적으로 곱하기 연산이 더하기 연산보다 더 값을 크게 만든다
하지만 두 수중에서 하나라도 0혹은 1인 경우 곱하기보다는 더하기를 수행하는것이 효율적이다
따라서 두 수에 대해서 연산을 수행할 때 두 수중 하나라도 1이하인 경우에는 더하고 나머지는 곱하도록 하면 된다.
Greedy Algorithm#2
1. 허프만코드 (Huffman Code)
1.1 정의 및 목표
•
데이터의 평균 비트 수를 최소화하는 최적 압축 이진코드.
•
빈도가 높은 데이터는 짧은 코드, 드문 데이터는 긴 코드 부여.
•
모든 코드는 prefix code여야 하며, 한 코드워드가 다른 코드워드의 접두사가 될 수 없음.
1.2 예시 및 비교
•
고정길이 코드: 모든 문자에 동일한 비트 할당(a:00, b:01, c:10).
•
가변길이 코드: 문자별로 다른 비트수 할당(a:10, b:0, c:11)로 전체 비트수 감소.
•
Prefix code는 이진트리로 표현 가능, 트리의 리프노드가 코드워드.
1.3 최적 이진코드 문제
•
각 문자의 빈도수에 따라, 전체 파일을 이진코드로 표현하는 데 필요한 비트 총합을 최소화해야 함.
•
허프만 알고리즘은 최적 이진코드 트리를 생성하는 탐욕적 방법.
1.4 허프만코드 구축 절차
1.
각 문자의 빈도로 노드 생성, 우선순위 큐(PQ)에 삽입.
2.
PQ에서 가장 빈도가 작은 두 노드 병합, 새 노드로 PQ에 삽입.
3.
노드가 하나 남을 때까지 반복, 최종 트리의 각 리프에 0/1 할당하여 코드 생성.
1.5 복잡도
•
PQ는 min-heap으로 구현, 각 연산 O(log n).
•
총 n–1회 병합이 필요, 전체 복잡도 O(n log n).
2. 0–1 배낭문제 (0–1 Knapsack Problem)
2.1 정의
•
n개 아이템, 각 아이템의 무게 wi, 가치 pi.
•
배낭 용량 W.
•
각 아이템을 1번만 선택, 가치 합이 최대이면서 무게 합 ≤ W.
2.2 수학적 표현
max∑i∈Apisubject to∑i∈Awi≤W\max \sum_{i \in A} p_i \quad \text{subject to} \quad \sum_{i \in A} w_i \leq W
maxi∈A∑pisubject toi∈A∑wi≤W
A는 선택된 부분집합.
2.3 무작정 알고리즘
•
가능한 모든 부분집합(2^n) 탐색, 각 경우에 대해 무게합 ≤ W, 가치 최대화.
•
시간복잡도 O(2^n).
2.4 탐욕 알고리즘 한계
•
가장 비싼 것, 가장 가벼운 것, 무게당 가치가 큰 것 순서로 담아도 항상 최적해가 아님.
•
탐욕법으로는 0–1 배낭문제의 최적해를 보장할 수 없음(반례 존재).
2.5 Fractional Knapsack Problem
•
아이템을 쪼개어 일부만 선택 가능.
•
단위무게당 가치가 높은 순으로 선택하면 최적해.
•
탐욕 알고리즘으로 항상 최적해가 가능.
3. 동적계획법을 이용한 0–1 배낭문제 해법
3.1 점화식
P[i,w]={P[i−1,w](wi>w)max(P[i−1,w], pi+P[i−1,w−wi])(wi≤w)P[i, w] = \begin{cases}
P[i-1, w] & (w_i > w) \\
\max(P[i-1, w],\ p_i + P[i-1, w-w_i]) & (w_i \leq w)
\end{cases}
P[i,w]={P[i−1,w]max(P[i−1,w], pi+P[i−1,w−wi])(wi>w)(wi≤w)
경계조건: P[0,w]=0P[0, w]=0P[0,w]=0, P[i,0]=0P[i, 0]=0P[i,0]=0.
3.2 표 기반(bottom-up) DP
•
2차원 배열 P[0..n][0..W] 채움.
•
각 셀은 위 점화식으로 계산.
•
시간복잡도: O(nW).
3.3 DP의 개선(top-down, memoization)
•
필요한 부분만 재귀적으로 계산, 메모이제이션 적용.
•
최악의 경우 O(min(2^n, nW)).
4. 탐욕 알고리즘 vs 동적계획법
탐욕 알고리즘 | 동적계획법(DP) | |
효율 | 탐욕 속성 충족 시 매우 효율 | 일반적으로 느림 |
최적성 | 조건부(보장 안 됨) | 항상 보장 |
적용 예 | 다익스트라, Fractional Knapsack | 플로이드, 0–1 Knapsack |
5. 결론
•
허프만 알고리즘은 이진트리를 통한 탐욕적 병합으로 정보이론적으로 최적 압축코드 생성.
•
0–1 배낭문제는 탐욕해법으로는 최적을 보장할 수 없으며, DP로 최적화 가능(점화식, 표 기반).
•
Fractional Knapsack은 탐욕적 선택 속성을 충족, 0–1 Knapsack은 동적계획법으로 해결.
•
DP 복잡도는 O(nW), 메모이제이션을 통한 개선은 최악의 경우에도 O(min(2^n, nW)).
