[DEV] 2주차. 자료구조/알고리즘(5)
1. Heap 대표 문제 - 더 맵게
Heaps
- 최대/최소 원소를 상수 시간으로 빠르게 찾을 수 있음
- 연산
- 힙 구성 (heapify)
- $O(nlogn)$
- 삽입 (insert)
- $O(logn)$
- 삭제 (remove)
- 최대/최소 원소를 하나 꺼내서 없애는 것
- $O(logn)$
- 힙 구성 (heapify)
- 완전 이진 트리
- 배열을 이용해서 구현 가능!
- 공간 효율성이 높음
- 응용
- 정렬 (heap sort)
- $O(nlogn)$
- 우선 순위 큐 (prioirty queue)
- 우선 순위에 따라 빠져나오는 큐
- 정렬 (heap sort)
문제 설명
매운 것을 좋아하는 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
scoville배열 정렬- 앞에서부터 공식에 따라 계산
- (가장 작은 수) + (두번째로 작은 수 * 2)
- 계산된 결과를 배열에 삽입
- 순서에 맞게!
- 모든 원소가 7보다 클 때까지 위 과정 반복
알고리즘 복잡도
- 최악의 경우
- 수가 하나 남을 때까지 섞어야 하는 경우 (n-1 회)
- 각 단계 (섞는 일) 에서 요구되는 계산량
- 정렬된 리스트에 순서를 맞추어 원소 삽입
- $O(n)$
- 전체 : $O(n^2)$
- 지나치게 높음
- Heap 이용
보다 나은 방법
- 최소/최대 원소를 빠르게 꺼내는 방법!
- 힙 (Heap)
- max heap
- min heap
python에서 힙 적용
import heapq
heapq.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:
min1 = heapq.heappop(scoville)
if min1 >= K:
break
elif len(scoville) == 0:
answer = -1
break
min2 = heapq.heappop(scoville)
new_scoville = min1 + (min2 * 2)
heapq.heappush(scoville, new_scoville)
answer += 1
return answer
- $O(nlogn)$
2. Dynamic Programming 대표 문제 - N으로 표현
동적계획법 (Dynamic Programming)
- 문제의 답인지 확인하기 위해서 탐색해야 하는 범위(solution space)를 진전하면서 동적으로 결정
- 처음에 정해놓고 시작하는 것이 아님
- 탐색 범위를 한정할 수 있음
- 주어진 최적화 문제를 (보통 최적화 문제를 다룸)
- 재귀적인 방식으로 보다 작은 부분 문제로 나누어
- 부분 문제를 풀어, 이 해를 조합하여
- 전체 문제의 해답에 이르는 방식
적용 예시 - 피보나치 수열
- 피보나치 수열을 재귀함수로 구현한다면?
- 같은 수를 여러 번 구해야 함
- 복잡도 : 지수 함수의 형태
- 동적 계획법을 적용한다면?
- 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
- 가장 높은 값을 가지도록 물건을 골라 배낭에 담기
문제 설명
아래와 같이 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 합니다.
입출력 예
문제 해결 방법
- N을 한 번 사용해서 만들 수 있는 수(들) ->
1 - N을 두 번 사용해서 만들 수 있는 수(들) ->
2 - N을 세 번 사용해서 만들 수 있는 수(들) ->
3
…
위 과정을 반복하다가 정답이 나오면 출력
예제
- N = 3
1 : 5
2 : 55 or 1 + - x / 1
3 : 555 or 1 + - x / 2
555 or 2 + - x / 1
- N = x
코드
def solution(N, number):
s = [set() for x in range(8)]
for i, x in enumerate(s, start=1):
x.add(int(str(N) * i)) # 초기화
for i in range(1, 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
3. 깊이/너비 우선 탐색 (DFS/BFS) 대표 문제 - 여행경로
깊이 우선 탐색 DFS
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
- root에서 가장 왼쪽부터 아래로 쭉 진행 (세로로)
- 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감
너비 우선 탐색 BFS
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또다시 너비 우선 탐색 진행
- root부터 가로로 한 줄씩 탐색
- 큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행함
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 “ICN” 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return하도록 solution 함수를 작성해주세요.
제한 조건
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
문제 해결 방법 - DFS 응용
- 한 붓 그리기!
- 이것이 가능함은 문제에서 보장되어 있음
- 시작 정점은 언제나 “ICN”
- 모든 정점 방문이 아니고, 모든 간선을 거쳐야 함
- 언젠가는 한 번 가야하는데, 그 순서를 결정하는 것!
- 한 정점에서 택할 수 있는 간선이 두 개 이상인 경우
- 공항 이름의 알파벳 순서를 따름
알고리즘 설계
- 입출력 두번째 예제
- 스택을 이용하여 재귀적인 한 붓 그리기 문제 해결
- DFS 알고리즘의 응용
코드
그래프의 표현
- 사전을 이용하여 각 공항에서 출발하는 항공권의 리스트을 표현
- 경로가 여러 개 일 경우 알파벳 순으로 방문해야 함 -> 리스트 이용
- 리스트: 뒤에서 제거하는 것이 편함
- 알파벳의 역순으로 정렬
ICN -> [SFO, ATL]
ATL -> [SFO, ICN]
SFO -> [ATL]
def solution(tickets):
routes = {}
for t in tickets:
routes[t[0]] = routes.get(t[0], []) + [t[1]]
for r in routes:
routes[r].sort(reverse = True)
stack = ["ICN"] # 출발은 항상 ICN
path = []
while len(stack) > 0:
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] # 리스트 역순으로 출력
알고리즘 복잡도
- 스택에 들어가고 나오는 횟수 : 한번씩 들어가고 꺼내짐
- ticket의 개수에 비례
- 표에 해당하는 공항에 대해 조사할 때 : list의 맨 끝을 꺼냄
- 정렬을 수행했음 -> $O(nlogn)$
- while문 반복 횟수 : ticket 개수
- 각 단계는 상수 시간
- $O(n)$
- 전체 알고리즘 복잡도는 정렬 시간에 지배됨!
- **$O(nlogn)$