[프로그래머스 인공지능 스쿨]Day04:파이썬을 무기로, 코딩테스트 광탈을 면하자! (2)
Step 5-1: 힙(Heap) 대표 문제 풀이: 더 맵게
문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
- scoville의 길이는 1 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
문제의 해결 - 예제
1 2 3 9 10 12 k=7
만약 오름차순으로 정렬되어 있지 않다면 정렬해야 한다.
3 9 10 12 k=7
1+(2*2)=5
->
3 5 9 10 12
9 10 12
3+(5*2)=13
->
9 10 12 13
9는 k=7보다 크기 때문에 여기까지 하고 끝낸다.
알고리즘의 복잡도
- 최악의 경우 :
- 수가 하나 남을 때까지 섞어야 하는 경우(n-1회)
- 각 단계(“섞는 일”)에서 요구되는 계산량:
- 정렬된 리스트에 순서 맞추어 원소 삽입
- O(n)
- 전체 문제 풀이의 복잡도:
- n번의 단계를 거치는데 각 단계에서 n에 비례하는 계산을 하기 때문에
- O(n^2)
- 지나치게 높다.
보다 나은 방법
- 최소/최대 원소를 빠르게 꺼낼 수 있으면 좋겠는데!
- 힙(heap)
- max heap
- min heap
힙(Heaps)
- 성질 : 최대/최소 원소를 빠르게 찾을 수 있음. 상수 시간에 원소들 중 가장 큰 것, 가장 작은 것을 찾을 수 있음!
- 연산
- 힙 구성(heapify) : O(NlogN), 빈 힙에 n개의 원소를 차례로 삽입하기 때문에. 하나의 원소를 삽입하는데 logN만큼 걸리므로 N개의 원소를 다 삽입하면 NlogN
- 삽입(insert) : O(logN)
- 삭제(remove) : O(logN)
힙의 구현
- 완전 이진 트리(complete binary tree)
- 배열을 이용해서 구현 가능!
힙의 응용
- 정렬(heapsort)
- 우선 순위 큐(priority queue) : 큐에 들어갈 때에는 순서 상관 없이 들어가고, 빠져나올 때 우선순위(여기선 스코빌 지수)에 따라 빠져나온다.
Step 5-2: Python 풀이 예제 보기
import heapq # 파이썬에서 힙을 이용하기 위한 라이브러리. q가 붙은 이유는 우선순위 큐를 이용하기 위해!
heap.heapify(L) # 리스트 L로부터 min heap 구성
m = heapq.heappop(L) # min heap L에서 최소값 삭제(반환)그리고 다시 힙의 구조를 유지한다.
heapq.heappush(L, x) # min heap L에 원소 x 삽입 그리고 다시 힙의 구조를 유지한다.
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while True:# 한번 도는데 최대 O(N)
min1 = heapq.heappop(scoville) # 힙에서 가장 작은 수 팝. 가장 안매운 음식, O(logN)
if min1 >= K:
break
elif len(scoville) == 0: # 다 섞어도 스코빌 지수를 넘지 못하면
answer = -1
min2 = heapq.heappop(scoville)# 두번째로 가장 안매운 음식, O(logN)
new_scoville = min1+(min2*2)
heapq.heappush(scoville, new_scoville) # 섞은 음식을 힙에 추가, O(logN)
answer += 1
return answer
복잡도는 O(NlogN)이다.
리스트나 배열을 정렬해서 쓰게 되면 O(N^2)이 된다.
Step 5-3: 풀어서 내걸로 만들자! “더 맵게”
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)# 힙을 만든다.
while scoville[0] < K:# 배열의 모든 요소가 스코빌 기준치 이상일때까지 돌린다
if len(scoville)==2:# 음식이 두개 남아있을때
if heapq.heappop(scoville)+(heapq.heappop(scoville)*2) < K:
return -1# 남은거 섞었는데도 스코빌 기준치 못넘으면 -1
else:#남은거 섞어서 스코빌 기준치 넘으면 +1
return answer+1
elif len(scoville)<=1 and scoville[0]<K:#1개 이하로 남았는데 스코빌 기준치 못넘으면 -1
return -1
heapq.heappush(scoville, heapq.heappop(scoville)+(heapq.heappop(scoville)*2)) # 힙에 스코빌 지수가 가장 낮은 음식, 그다음으로 낮은 음식을 팝해서 연산해준 후 결과를 푸시해준다.
answer += 1 # 연산 횟수를 증가시켜준다.
# print(scoville)
return answer
Step 6-1: 동적계획법(Dynamic Programming)대표 문제 풀이 : N으로 표현
문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
제한사항
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.
동적계획법(Dynamic Programming)
- 주어진 최적화 문제를
- 재귀적인 방식으로 보다 작은 부분 문제로 나누어
- 부분 문제를 풀어, 이 해를 조합하여
- 전체 문제의 해답에 이르는 방식
- 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있음
동적계획법(Dynamic Programming)의 적용 예
- 피보나치 수열 -> 재귀함수로 구현한다면?
f(4) = f(3)+f(2) = f(2)+f(1)+f(1)+f(0) = f(1)+f(0)+f(1)+f(1)+f(0)복잡도 : 지수함수의 형태
수가 커질수록 복잡도가 기하급수적으로 커져 지수함수의 형태가 된다. - 피보나치 수열 -> 동적계획법을 적용한다면?
f(0)=0, f(1)=1 -> 문제의 정의에 따라 이미 알고 있는 값들. 이제 문제를 잘게 나눠 부분해를 구하기 시작한다. f(2)=f(1)+f(0)=1 f(3)=f(2)+f(1)=2 f(4)=f(3)+f(2)=3복잡도 : 선형함수의 형태
이렇게 부분문제들의 합으로 답을 구해나가는 방식이다.
동적계획법의 적용 예
- Knapsack Problem 가장 높은 값을 가지도록 물건들을 골라 배낭에 담으시오.
문제의 해결 - 동적계획법으로 설계
N을 한 번 사용해서 만들 수 있는 수(들) : 1
N을 두 번 사용해서 만들 수 있는 수(들) : 2
N을 세 번 사용해서 만들 수 있는 수(들) : 3
…
문제의 해결 - 예제
N = 5일 때,
N을 한 번 사용해서 만들 수 있는 수(들)
- 5
N을 두 번 사용해서 만들 수 있는 수(들)
- 55
- 한번 사용해서 만들 수 있는 수 + - * / 한번 사용해서 만들 수 있는 수 = 10, 0, 25, 1
N을 세 번 사용해서 만들 수 있는 수(들)
- 555
- 한번 사용해서 만들 수 있는 수 + - * / 두번 사용해서 만들 수 있는 수
- 두번 사용해서 만들 수 있는 수 + - * / 한번 사용해서 만들 수 있는 수
- 따라서 60, 15, 5, 30, 6, -50, -5, -20, 4, 275, 50, 0, 125, 11, 2, 20, -4, 555(set, 즉 집합을 이용해 중복 제거했다고 가정)
N을 네 번 사용해서 만들 수 있는 수(들)
- 5555
- 한번 사용해서 만들 수 있는 수 + - * / 세번 사용해서 만들 수 있는 수
- 두번 사용해서 만들 수 있는 수 + - * / 두번 사용해서 만들 수 있는 수
- 세번 사용해서 만들 수 있는 수 + - * / 한번 사용해서 만들 수 있는 수
N을 다섯 번 사용해서 만들 수 있는 수(들)
- 55555
- 한번 사용해서 만들 수 있는 수 + - * / 네번 사용해서 만들 수 있는 수
- 두번 사용해서 만들 수 있는 수 + - * / 세번 사용해서 만들 수 있는 수
- 세번 사용해서 만들 수 있는 수 + - * / 두번 사용해서 만들 수 있는 수
- 네번 사용해서 만들 수 있는 수 + - * / 한번 사용해서 만들 수 있는 수
이런식으로 계속 진행된다…
문제의 해결 - 일반화
N = x 일 때,
N을 x 번 사용해서 만들 수 있는 수(들)
- x *n
- 한번 사용해서 만들 수 있는 수 + - * / n-1번 사용해서 만들 수 있는 수
- 두번 사용해서 만들 수 있는 수 + - * / n-2번 사용해서 만들 수 있는 수 …
- n-1번 사용해서 만들 수 있는 수 + - * / 한번 사용해서 만들 수 있는 수
괄호 사용 문제 처리는 문제가 있을까? 문제가 없다! 왜냐하면 몇번 사용해서 만든 수들을 갖고 있을때, 수식이 아니라 계산 결과 “수”를 갖고 있으므로 괄호를 쳐서 수식을 계산한 것과 동일하기 때문이다.
요약
문제의 성질에 따라, 동적계획법으로 풀어냄으로써 탐색해야 하는 범위를 효과적으로 줄일 수 있음
Step 6-2: Python 풀이 예제 보기
def solution(N, number):
s = [set() for x in range(8)]# 몇번을 사용했을 때 만들어지는 수들을 다 담기 위한 리스트. 중복을 허용하지 않고 수를 모은다. [set()]*8하면 안된다!!
for i, x in enumerate(s, start=1):
# s에 들어있는 원소들을 x에 담고, i는 1부터 시작하는 연달은 정수를 가지게 한다.
x.add(int(str(N)*i)) #한번사용:5, 두번사용:55,...
for i in range(len(s)):
for j in range(i):
for op1 in s[j]:#연산자의 앞에 놓일 수
for op2 in s[i-j-1]:#연산자의 뒤에 놓일 수
s[i].add(op1 + op2)
s[i].add(op1 - op2)
s[i].add(op1 * op2)
if op2 != 0:
s[i].add(op1 // op2) # 나머지는 버려야 하므로 /이 아니라 //
if number in s[i]:#넘버가 집합 안에 포함되어있으면
answer = i + 1
break
else:
answer = -1
return answer
Step 7-1: 깊이/너비 우선 탐색(DFS/BFS) 대표 문제 풀이: 여행경로
배경지식
- 그래프(graphs)
- 정점(vertex, node)과 간선(edge, link)
- 유향(directed) 그래프와 무향(undirected) 그래프
- 스택(stack)
- 큐(queue)
깊이 우선 탐색(DFS; Depth-First Search)
한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
스택을 이용해서 어떤 정점에서 DFS를 하고 있는지를 기억하고 되돌아감
너비 우선 탐색(BFS; Breadth-First Search)
한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로(방문한 순서에 따라)또다시 너비 우선 탐색을 행함
큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행함
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
문제의 해결 - 깊이 우선 탐색(DFS)을 응용
- 한 붓 그리기!
- 이것이 가능함은 문제에서 보장되어 있음
- 시작 정점은 언제나 “ICN”
- 모든 정점 방문이 아니고, 모든 간선을 거쳐야
- 언젠가는 한 번 가야 하는데, 그 순서를 결정해라
- 한 정점에서 택할 수 있는 간선이 두 개 이상인 경우?
알고리즘의 설계
스택을 이용하여 재귀적인 “한 붓 그리기” 문제를 해결 -> DFS 알고리즘의 응용
스택에 한붓그리기로 넣으면(역순으로 쌓임)
요약
재귀적인 성질을 가진 “한 붓 그리기” 문제
-> 재귀적인 성질을 가진 “그래프의 깊이 우선 탐색”을 응용하여 해결
Step 7-2: Python 풀이 예제 보기
그래프의 표현
사전을 이용하여 각 공항에서 출발하는 항공권의 리스트를 표현
ICN -> [ATL, SFO] # ICN이 키, [ATL,SFO]이 값
ATL -> [SFO, ICN]
SFO -> [ATL]
알파벳 역순으로 정렬!
def solution(tickets):
routes = {} # 경로를 저장할 사전
for t in tickets: # 티켓들을 하나씩 꺼내서(앞이 출발공항, 뒤가 도착공항)
routes[t[0]] = routes.get(t[0], []) + [t[1]] # 출발공항에 도착공항 추가. 만약 처음 등장하는 것이면 빈 리스트를 리턴하도록 get메소드 호출. 여기에 t[1], 도착공항의 이름을 붙여준다.
# 라우트에 출발공항이 키가 되고, 값으로 그 공항에서 갈 수 있는 공항들의 이름이 들어있는 사전이 된다.
for r in routes: # 알고리즘의 복잡도가 여기에서 지배됨! O(NlogN)
routes[r].sort(reverse=True)#알파벳 역순으로 정렬
# 이제 스택을 이용해 어떤 순서로 공항을 방문할지 알고리즘 전개!
stack = ["ICN"] # 항상 인천공항에서 출발!
path = []
while len(stack) > 0 : # 모든 표를 하나씩 꺼내기 때문에 O(N)
top = stack[-1] # 스택을 하나씩 뺌
if top not in routes or len(routes[top]) == 0: # 만약 라우트에 안들어있거나(공항에서 출발하는 표가 하나도 없음), 표가 있었는데 다 썼으면
path.append(stack.pop()) # 경로에다가 스택에서 팝한걸 넣어준다.
else: # 갈 수 있는 공항이 있으면
stack.append(routes[top][-1]) # 갈 수 있는 공항 중 마지막 번째 공항(알파벳 역순으로 정렬했기 때문에 탑에 있는 것이 알파벳 순서상 가장 앞선 것!)
routes[top] = routes[top][:-1] # 맨 끝의 원소 꺼냄. pop써도 됨!
return path[::-1] # 경로 역순으로 출력!
전체 알고리즘의 복잡도는 routes[r].sort(reverse=True)에 의해 O(NlogN)!