1주차 마지막 학습 내용 정리 ✈️
✅ Heap
- 최소 or 최대 원소를 빠르게 찾을 수 있음
- Heapify (최소힙 구성) // insert (삽입) - O(logN)의 복잡도를 가짐
- 완전 이진 트리로 구성되며 heap sort, 우선순위 큐로 응용 가능
🎈 더 맵게
주어진 모든 음식을 스코빌 지수 k 이상으로 만들 때 혼합 과정은 아래를 거친다.
섞은 음식 : 가장 안매운 음식의 스코빌 지수 + 두번째로 맵지않은 음식의 스코빌지수*2
위 과정을 거쳐 모든 음식이 스코빌 지수 k를 넘을 경우, 과정을 거친 최소 횟수를 리턴하는 문제
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while scoville[0] < K:
mixing = heapq.heappop(scoville) + heapq.heappop(scoville)*2
heapq.heappush(scoville, mixing)
answer += 1
if scoville[0] < K and len(scoville) == 1:
return -1
return answer< 풀이 과정 >
heapify로 주어진 scoville리스트를 최소 힙으로 만들어준다.
scoville의 최소 값을 가진 원소가 K보다 작은 조건으로 while루프를 돌며
주어진 과정을 거쳐 mixing을 만들고, 모든 음식을 혼합해도 K보다 작다면 -1을 리턴한다.
✅ DFS/BFS
- DFS : 깊이 우선 탐색으로 스택을 이용해 재귀적인 방식으로 탐색 (한 붓 그리기)
- BFS : 너비 우선 탐색으로 큐를 이용해 탐색
🎈 여행 경로
주어진 항공권으로 ICN 공항에서 시작하는 여행 경로를 짜려고 한다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때 항공권을 모두 사용해 방문하는 공항 경로를 리턴하는 문제.
경로가 여러 개인 경우 알파벳 순으로 정렬하기
# BFS - 나의 풀이
from collections import deque
def solution(tickets):
answer = []
# 주어진 tickets에 도착지를 오름차순 정렬
tickets.sort(key = lambda x: x[1])
# 큐에 현재 공항, 경로, ticket 사용 여부를 큐에 삽입
queue = deque()
queue.append(('ICN', ['ICN'], []))
while queue:
# 큐에서 매번 빼내면서
airport, route, visited = queue.popleft()
# 티켓 모두 사용한 경우, answer에 추가
if len(visited) == len(tickets):
answer.append(route)
# tickets를 enumerate로 탐색해, 티켓 인덱스, (출발, 도착) for문으로 순회
for idx, ticket in enumerate(tickets):
# 출발지가 현재 공항위치고 아직 사용하지 않은 티켓인 경우
if ticket[0] == airport and not idx in visited:
# 큐에 도착지, 경로 + 도착지, 티켓 사용한 인덱스를 다시 삽입한다.
queue.append((ticket[1], route + [ticket[1]], visited + [idx]))
# 모든 경로에 대해 주어졌으므로, 제일 첫번째 리스트만 출력
return answer[0]
# DFS
def solution(tickets):
answer = []
routes = {}
for t in tickets:
# 출발지 : 도착지로 routes dic형 만들기 (처음 도착 시 빈 리스트 만들고 + 도착지)
routes[t[0]] = routes.get(t[0], []) + [t[1]]
for i in routes:
# 도착지 내림차순 정렬
routes[i].sort(reverse = True)
# 결과 path 와 stack에 ICN 입력
stack = ['ICN']
path = []
# 스택이 빌때까지 반복
while stack:
# 스택 값 빼서 확인
top = stack[-1]
# 출발 공항이 없거나, 도착지가 없다면(이미 티켓 사용으로)
if top not in routes or len(routes[top]) == 0:
# path에 입력
path.append(stack.pop())
# 티켓이 있는 경우 스택에 도착지 집어 넣고 도착지 갱신
else:
stack.append(routes[top][-1])
routes[top] = routes[top][:-1]
return path[::-1]< 풀이 과정 >
BFS를 만들어 풀이를 진행했는데, deque을 만들고 리스트를 3개나 만들어 큐가 비는 작업을 진행했기에 시간복잡도와 공간복잡도가 더 오래걸린 것 같다.
✅ Dynamic Programming
- 주어진 최적화 문제를 재귀적인 방식으로 작은 부분 문제로 만들어 이를 해결하고 전체 문제를 해결하고자 하는 알고리즘
- 탐색 범위를 동적으로 결정함으로써 탐색 범위를 한정하며 알고리즘 진행 가능
-> 탐색 범위를 효과적으로 줄여줄 수 있음- ex) knapsack 알고리즘
🎈 N으로 표현
숫자 n과 number가 주어질 때 N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N을 최소로 사용한 횟수를 구하는 문제 (최소값이 8보다 크면 -1을 리턴)
def solution(N, number):
# 주어진 숫자 N과 만들어야 하는 number가 동일하면 1을 리턴
if N == number:
return 1
# 숫자 개수 별 만들 수 있는 숫자 조합 0~8까지 만들기
possible = [set() for _ in range(9)]
# 숫자 1개로 number를 만드는 경우는 N 1개
possible[1].add(N)
# 동적 계획법을 이용하여 숫자 2개 ~ 8개로 가능한 조합 구하기
for i in range(2, 9):
# 한 숫자로 쭉 나열한 경우 추가
possible[i].add(int(str(N) * i))
# 절반까지만 확인하여 복잡도 낮추기 (4인 경우 (1,3) ~ (3,1) 경우 확인)
for j in range(1, i//2 + 1):
for op1 in possible[j]:
for op2 in possible[i - j]:
possible[i].add(op1 + op2)
possible[i].add(op1 - op2)
possible[i].add(op2 - op1)
possible[i].add(op1 * op2)
if op2 != 0:
possible[i].add(op1 // op2)
if op1 != 0:
possible[i].add(op2 // op1)
if number in possible[i]:
return i
# 최솟값이 8보다 크면 -1 반환
if i == 8:
return -1
return -1✨ Code 형식
코드 짤 때 참고해야 할 사항들
위 링크를 참고하여 코드를 작성하도록 하자! (암묵적인 rule 느낌)
To be a DataScientist