알고리즘으로 생각하기 - 양성봉 참고
백준 문제를 풀다가 알고리즘 풀이가 잘 기억이 나지 않아서
교과서에 있는 알고리즘 코드를 외우기 위해 작성
태스크 스케줄링
1. 구간 스케줄링
설명
n개의 태스크와 1개의 프로세스가 있을 때, 수행 시간이 겹치지 않게
가장 많은 태스크들을 수행하는 방법
단, 각 태스크는 시작과 종료 시각을 가진다.
시간 복잡도
정렬 O(nlogn) + task검사 O(1) = O(nlogn)
알고리즘
[1] 종료시각으로 정렬한다.
[2] 가장 일찍 종료하는 동아리를 선택한다.
[3] 다음 동아리의 시작 시각이 직전에 선택된 동아리의 종료 시각 이전이면
다음 동아리를 포기하고, 이후이면 다음 동아리를 선택한다.
코드
a = [['지역봉사회', 8, 13], ['서예회', 9, 11], ['토론회', 10, 12], ['바둑회', 11, 14],
['문학회', 13, 16], ['독서회', 14, 15], ['사진회', 15, 17]]
a.sort(key=lambda t: t[2])
solution = [a[0]]
i = 0
for j in range(1, len(a)):
if a[j][1] >= a[i][2]: # 직전에 선택된 동아리의 종료시간 이후에 시작하면
solution.append(a[j])
i = j
print('선택된 동아리:', solution)
2. 구간 분할
설명
n개의 태스크가 있을 때, 최소의 프로세서를 사용하여 수행 시간이 겹치지 않게 모든 태스크를프로세서에 배정하는 문제
단, 각 태스크는 시작과 종료 시각을 가진다.
시간 복잡도
정렬 O(nlogn) + task배정 가능성 검사 O(d)*n = O(nlogn) + O(dn)
알고리즘
[1] 동아리들을 첫 시작 시각으로 정렬한다.
[2] 동아리를 미팅룸1에 배정한다.
[3] 다음 동아리를 기존의 미팅룸에 배정할 수 있으면 배정하고, 배정할 수 없으면 새 미팅룸에 배정한다.
코드
a = [['문학회', 9.0, 11.0], ['지역봉사회', 9.0, 12.5], ['서예회', 13.0, 14.5],
['바둑회', 14.0, 17.0], ['미술회', 11.0, 14.0], ['사진회', 9.0, 11.0],
['음악회', 15.0, 16.5], ['창조회', 15.0, 16.5], ['독서회', 11.0, 12.5],
['토론회', 13.0, 14.5]]
n = len(a)
a.sort(key=lambda x: x[1]) # 시작 시간으로 정렬
solution = [[a[0]]]
finish_time = [a[0][2]] # 직전 선택된 동아리 미팅 종료 시간
k = 0 # 미팅룸0
for i in range(1, n):
flag = False
for j in range(k+1):
if a[i][1] >= finish_time[j]: # 현재 동아리 a[i]를 미팅룸 j에
solution[j].append(a[i]) # 할당 가능하면 solution[j] 뒤에 추가
finish_time[j] = a[i][2] # 미팅룸[j]의 finish_time 갱신
flag = True # 다음 동아리를 위해 for-루프로
break
if not flag: # 새 미팅룸 만들기
k += 1
solution.append([a[i]])
finish_time.append(a[i][2])
for i in range(k+1):
print('미팅룸', i+1, ':', solution[i])
초 증가 순서
설명
부분 집합의 합
주어진 숫자들 가운데서 합하여 K가 되는 숫자들을 찾는 문제
초 증가 순서: 각 숫자가 자신보다 앞서있는 숫자들의 합보다 큰 순서
ex) 동전: 1원, 5원, 10원, 50원, 100원, 500원
시간 복잡도
이미 되어있지만, 사전 정렬한다면 O(nlogn)
test 시간 O(n)
시간복잡도 → O(n)
알고리즘
집합의 가장 큰 숫자부터 차례대로 다음과 같이 검사한다
while K > 0:
if 현재 검사하는 숫자 x > K:
x를 무시한다
else:
x를 선택한다
K = K - x
코드
S = [1, 4, 7, 16, 44, 100, 260, 550]
K = 200
solution = []
i = len(S) - 1
while K > 0:
if S[i] <= K: # S[i]가 K보다 크지 않으면
solution.append(S[i]) # S[i] 추가
K -= S[i]
i -= 1
print(solution)
최소 신장 트리: MST
설명
신장 트리: 그래프의 모든 점들을 연결하는 트리
사이클을 가지지 않음.
최소 신장 트리: 간선에 가중치가 부여된 그래프에서 최소 가중치의 합을 가진 신장 트리
그래프 - 점:n, 간선:m
MST - 점:n, 간선 n-1
MST - 크러스컬 알고리즘
설명
가장 짧은 간선을 욕심내어 가져다 신장 트리를 만든다.
이때 가져온 간선이 사이클을 만들면 그 간선은 버리고 그다음 짧은 간선을 가져옴.
시간 복잡도
O(mlogm), m은 간선의 수
m이 n^2일 때, 2mlogn, m이 n일 때는 nlogn
MST - 프림 알고리즘
설명
한 점에서 시작하여 욕심내어 가장 짧은 간선을 연결하여 신장 트리를 만든다.
시간 복잡도
트리에 넣기 O(n)
for 트리 밖의 점 중 가중치 최소 점 찾기 O(n)
for 주변정리 O(n)
→ O(n^2)
최소 힙을 사용하면 O(mlogn), m은 간선 수
→ 크러스컬 알고리즘과 프림 알고리즘의 시간 복잡도는 비슷하다.
알고리즘
[1] 임의의 점 하나를 선택하여 T에 넣는다.
[2] 다음을 n-1회 수행한다.
T 밖에 있는 점들 중에서 T에 있는 점과 가장 가중치가 작은 점을 T에 추가한다.
n-1회 수행하는 이유: MST에서 간선의 개수 n-1개만 찾으면 되니깐
ex)점 6개면 신장트리 간선 5개
T는 트리(해집합)
코드
n = 6 # 그래프 정점 수
g = [[]] * n
g[0] = [[1, 4], [3, 8], [4, 2]]
g[1] = [[0, 4], [2, 9], [4, 3]]
g[2] = [[1, 9], [3, 2], [5, 1]]
g[3] = [[0, 8], [2, 2], [4, 4], [5, 1]]
g[4] = [[0, 2], [1, 3], [2, 7], [3, 4]]
g[5] = [[2, 1], [3, 1]]
included = [False for _ in range(n)] # 트리에 포함 여부
D = [float('inf') for _ in range(n)] # 트리의 정점에서 각 정점까지의 거리
D[0] = 0
connected_to = [-1 for _ in range(n)] # 트리의 간선을 추출하기 위해
for k in range(n):
m = -1
min_value = float('inf')
for j in range(n): # 트리 밖의 정점들의 D 원소들 중에서 최솟값을 가진 정점 m 찾기
if not included[j] and D[j] < min_value:
min_value = D[j]
m = j
included[m] = True
for w, wt in g[m]: # m에 인접하면서 트리 밖에 있는 정점의 D의 원소 갱신
if not included[w] and wt < D[w]:
D[w] = wt # D 원소 갱신
connected_to[w] = m
print('MST: ', end='')
mst_cost = 0
for i in range(1, n):
print('(%d, %d)' % (i, connected_to[i]), end='')
mst_cost += D[i]
print('\nMST의 가중치: ', mst_cost)
최단 경로
설명
가중치 그래프의 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제
최단 경로 - 다익스트라(Dijkstra) 알고리즘
설명
프림 MST 알고리즘을 이용
프림 알고리즘도 시작점이 있지만, 프림 알고리즘은 시작점을 뭘 잡아도 값이 같이 나옴.
근데 최단 경로는 시작점이 중요함. 프림 알고리즘처럼 하지만 점의 거리 계산을 다르게 하면 된다.
거리 계산: 시작점으로부터의 거리 계산하면 됨 → 다익스트라 알고리즘
시간 복잡도
루프 O(n), 간선 완화 O(n)
알고리즘의 수행 시간: O(n^2)
최소 힙을 사용하면 O(mlogn)
알고리즘
[1] 경로가 미확정된 점 중에서 출발점에서 가장 가까운 점을 선택한다. 선택된 점을 m이라고 하자.
[2] 경로가 미확정된 점중에서 m에 인접한 점이 있으면, 출발점에서 m을 거쳐서 더 짧은 거리로
인접한 점에 도달할 수 있으면 그 거리를 기록해 둔다
코드
n = 8 # 그래프 정점 수
s = 0 # 시작점
g = [[]] * n
g[0] = [[1, 3], [3, 5], [4, 6]]
g[1] = [[2, 3], [3, 1], [5, 4]]
g[2] = [[3, 7]]
g[3] = [[4, 4], [5, 1]]
g[4] = [[5, 8], [6, 1]]
g[5] = [[2, 6], [7, 10]]
g[6] = [[5, 9], [7, 1]]
g[7] = []
included = [False for _ in range(n)] # 초기화
distance = [float('inf') for _ in range(n)] # distance[i]를 최댓값으로 초기화
distance[s] = 0
previous = [-1 for _ in range(n)] # 최단 경로를 추출하기 위해
previous[s] = 0
for k in range(n):
m = -1
min_value = float('inf')
for j in range(n): # 방문 안된 정점들의 distance 원소들 중에서 최솟값을 가진 정점 m 찾기
if not included[j] and distance[j] < min_value:
min_value = distance[j]
m = j
included[m] = True
for w, wt in g[m]: # m에 인접한 방문 안된 각 정점의 D의 원소 갱신
if not included[w] and distance[m] + wt < distance[w]:
distance[w] = distance[m] + wt # 간선 완화
previous[w] = m
print('정점 ', s, '(으)로부터 최단 거리:')
for i in range(n):
if distance[i] == float('inf'):
print(s, '와(과) ', i, ' 사이에 경로 없음.')
else:
print('[%d, %d]' % (s, i), '=', distance[i])
print('\n정점 ', s, '(으)로부터의 최단 경로')
for i in range(n):
back = i
print(back, end='')
while back != s:
print(' <-', previous[back], end='')
back = previous[back]
print()
허프만 코딩
설명
파일 압축: 파일의 크기를 줄이는 방법
코드가 이진수이니 코드와 이진 트리를 연관지어 왼쪽 자식 0, 오른쪽 자식 1 부여
그냥 하면 275*8bit = 825지만 허프만 코딩 사용하면 3bit*125+2bit*150 = 475로 압축
위 그림은 숫자가 깔끔해서 이쁜 트리가 그려졌지만,
예를 들어 초 증가 순서로 된 숫자들이라면 편향 이진 트리가 그려진다.
시간 복잡도
최소 힙 O(n)
While 루프 n-1회
루프 내에서 O(logn)
수행시간 = O(n) + (n-1)*O(logn) = O(nlogn)
알고리즘
[1] 압축할 파일을 스캔하여 각 문자의 빈도수를 계산한다.
[2] 문자마다 문자와 빈도수를 가진 이파리 노드를 만든다.
[3] 빈도수가 가장 적은 두 노드의 부모를 만들어 빈도수의 합을 저장한다.
[4] if 노드가 하나만 남으면:
[5] 남은 노드를 허프만 트리의 루트로 반환
[6] else:
[7] 자식이 된 노드들을 제외하고 goto[3]
코드
from heapq import heappush, heappop, heapify
def huffman_tree(a):
h = [[freq, [char, ""]] for char, freq in a] # ""에 코드 담는다.
heapify(h) # 최소 힙 만들기
while len(h) > 1:
left = heappop(h) # 루트 제거(최소의 빈도수 가진 항목 제거)
right = heappop(h) # 한번 더 루트 제거
for code in left[1:]: # 왼쪽 자식이면 0 추가
code[1] = '0' + code[1]
for code in right[1:]: # 오른쪽 자식이면 1 추가
code[1] = '1' + code[1]
t = [left[0] + right[0]] + left[1:] + right[1:] # 합쳐진 새 항목
print(t)
heappush(h, t) # 힙에 새 항목 t 삽입
return h # 힙 h는 1개의 항목만 가진채 리턴
input_freq = [['b', 20], ['c', 30], ['d', 35], ['e', 40], ['a', 60], ['f', 90]]
h_code = huffman_tree(input_freq)
result = sorted(heappop(h_code)[1:], key=lambda x: x)
for ch, code in result:
print(ch, ':', code)