📖 학습주제
자료구조/알고리즘 풀기(5)
힙(Heap)
문제풀이
더 맵게
1) 문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.2) 제한 사항
- scoville의 길이는 1 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
3) 입출력 예
4) 풀이
가장 맵지 않은 음식과 두번째로 맵지 않은 음식을 섞는 것을 조건을 만족할 때까지 반복하면 된다. 그러나 그냥 진행하면 복잡도가 높아질 수 있으니 최대/최소를 빠르게 꺼낼 수 있는 힙을 이용한다.
코드
import heapq # 힙 구현을 위해 호출
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # 리스트를 힙으로
while True:
min1 = heapq.heappop(scoville) # 스코빌 지수가 가장 낮은 음식
if min1 >= K: # 가장 낮은 스코빌 지수가 K 이상이면 중지
break
elif len(scoville) == 0: # 스코빌 지수를 K 이상으로 만드는 게불가능하면 -1 리턴
answer = -1
break
min2 = heapq.heappop(scoville) # 스코빌 지수가 두번째로 낮은 음식
new = min1 + 2 * min2
heapq.heappush(scoville, new)
answer += 1 # 주어진 연산에 따라 처리하고 섞은 회수 +1
return answer결과
동적계획법(Dynamic Programming)
주어진 최적화 문제를 재귀적인 방법으로 보다 작은 부분 문제로 나누어 풀어, 이 해들을 조합해 전체 문제의 해를 구하는 방법
문제풀이
N으로 표현
1) 문제 설명
매아래와 같이 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 함수를 작성하세요.2) 제한 사항
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
3) 입출력 예
4) 풀이
예시의 문제에 경우(N=5) 5를 하나만 썼을 때 만들 수 있는 경우는 5 하나이다. 5를 2개 썼을 때 만들 수 있는 경우는 55와 5를 하나만 썼을 때와 다시 5를 하나만 썼을 때의 경우 각각에 사칙연산을 적용한 것과 같다. 다시 5를 3개 썼을 때는 555와 5를 하나만 썼을 때와 5를 2개 썼을 때의 경우, 5를 2개 썼을 때와 5를 하나만 썼을 때의 경우 각각에 사칙연산을 적용한 것과 같다. 이런식으로 1부터 n-1까지 나누어서 풀면 답을 구할 수 있다.
코드
def solution(N, number):
s = [set() for x in range(8)] # N이 1이상 9이하 (최대 N-1 = 8)
if N == number: # N == number 일 때 자기 자신 밖에 없으므로
answer = 1
else:
for i,x in enumerate(s, start=1):
x.add(int(str(N)*i)) # N을 여러번 반복한 수( e.g.) 5, 55, 555, ...)
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]: # number가 위의 연산으로 만든 수들의 집합에 있을 때
answer = i+1
break
else:
answer = -1
return answer결과
깊이/너비 우선 탐색(DFS/BFS)
- 깊이 우선 탐색 : 한 노드에서 인접한 모든 (아직 방문하지 않은) 노드에 방문하되 각 인접 노드들을 기준으로 깊이 우선 탐색을 끝낸 후 다음 노드로 진행
- 너비 우선 탐색 : 한 노드에서 인접한 모든 (아직 방문하지 않은) 노드에 방문하고 방문한 각 인접 노드를 기준으로 (방문한 순서에 따라) 또다시 너비 우선 탐색 진행
문제풀이
여행경로
1) 문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.2) 제한 사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
3) 입출력 예
4) 풀이
딕셔너리로 그래프를 표현하고, 스택을 사용해 재귀적인 성질을 가진 한 붓 그리기 문제를 풀듯이 깊이 우선 탐색을 응용한 답을 구한다.
코드
def solution(tickets):
routes = {} # 빈 딕셔너리
for t in tickets: # 출발 공항를 key로 도착 공항을 value로 한다
routes[t[0]] = routes.get(t[0], []) + [t[1]]
for r in routes: # 도착 공항을 알파벳 역순으로 정렬한다(뒤에서 pop하는 것이 더 효율적)
routes[r].sort(reverse = True)
stack = ['ICN'] # ICN에서 출발
path = [] # 방문한 공항
while len(stack) > 0:
top = stack[-1]
# 어떤 공항에서 출발하는 표가 없거나 써버렸을 때 path에 추가
if top not in routes or len(routes[top]) == 0:
path.append(stack.pop())
# 갈 수 있다면 stack에 넣고 사용한 표는 없앤다
else:
stack.append(routes[top][-1])
routes[top] = routes[top][:-1]
answer = path[::-1] # 방문한 순서 반대로 저장되어 있으므로 역순으로 한다.
return answer 결과
