힙(Heap) 대표 문제 풀이 - 더 맵게
- 손으로 풀어보기
- 알고리즘 복잡도 생각하기
1) 리스트 이용
- 각 단계("섞는 일")에서 요구되는 계산량 : 정렬된 리스트에 순서 맞춰 원소 삽입
- 최악의 경우 O(N^2)
2) 힙 이용
- 힙은 완전 이진 트리 형태로 배열을 이용해서 구현 가능
- 최소 혹은 최대 원소를 꺼내는 문제에선 힙을 이용하면 효율이 좋음
- 힙의 연산을 다시 생각해보면, heapify (NlogN) / push (logN) / pop (logN)
- 최악의 경우 O(NlogN)
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # 최소 힙
while scoville[0] < K:
if len(scoville) >= 2:
s1 = heapq.heappop(scoville)
s2 = heapq.heappop(scoville)
heapq.heappush(scoville,s1+s2*2)
answer += 1
else:
return -1
return answer
힙의 응용
- 정렬(heapsort)
- 우선 순위 큐(priority queue)
동적 계획법(Dynamic Programming)
- 주어진 최적화 문제를 재귀적인 방식으로 작은 문제로 쪼갬
- 그리고 이 작은 문제를 풀어, 이 해의 조합으로 전체 문제의 해답에 이르는 방식
- 알고리즘 진행에 따라 탐색 범위를 동적으로 결정함
- 피보나치 수열
1) 재귀함수로 구현한다면
- 복잡도 : 지수 함수의 형태
2) 동적 계획법으로 구현한다면
- 복잡도 : 선형 함수의 형태 - 이점
- 문제의 성질에 따라, 동적계획법으로 풀어냄으로써 탐색 범위를 효과적으로 풀어낼 수 있음 - 예시 - N으로 표현
def solution(N, number):
s = [set() for _ in range(8)]
for i,x in enumerate(s, start=1):
x.add(int(str(N) * i))
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
깊이/너비 우선 탐색(DFS/BFS) 대표 문제 풀이 - 여행 경로
-
from collections import defaultdict
def solution(tickets):
answer = []
airport = defaultdict(list)
vis = defaultdict(list)
for dep,arr in tickets:
airport[dep].append(arr)
for i in airport.keys():
airport[i].sort(reverse=True)
def dfs():
stack = ["ICN"]
while stack:
now = stack[-1]
if not airport[now]:
answer.append(stack.pop())
else:
stack.append(airport[now].pop())
dfs()
return answer[::-1]
'dev course - DE > TIL' 카테고리의 다른 글
[데브코스] TIL 7일차 (0) | 2024.04.02 |
---|---|
[데브코스] TIL 6일차 (0) | 2024.04.01 |
[데브코스] TIL 4일차 (0) | 2024.03.28 |
[데브코스] TIL 3일차 (1) | 2024.03.27 |
[데브코스] TIL 2일차 (0) | 2024.03.26 |