[그리디] 섬 연결하기 (Lv.3)
걸린 시간
45분
접근 방식
처음에는 2차원 배열로 관계를 저장하고 플로이드 워셜로 최단 거리를 다 구하면 될줄 알았지만 문제는 모든 Node를 방문하도록 연결하는 연결값의 최솟값을 구하는 것이었다.
그래서 비용 기준으로 오름차순 정렬한 뒤 사이클이 만들어지는지 유무를 판단해서 그리디로 풀려고 했으나
사이클 유무를 다른 노드와 연결여부만으로 판단할 수는 없었다.
그래서 해설을 찾아본 결과 크루스칼 알고리즘을 써야하는 문제였다.
크루스칼 알고리즘은 이 문제가 요구하는 가중치의 합이 최소가 되는 신장 트리
즉, 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘이다.
비용 기준 오름차순으로 정렬한 뒤, 각 노드마다 연결됐을 때 임의의 기준으로 각 노드에 부모노드를 심어두고 이후 사이클 유무 판단은 각 노드가 서로 부모노드가 같은지 여부에 따라 결정하는 방식으로 최소 신장 트리를 구한다.
정답 코드
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
rootA = find(parent, a)
rootB = find(parent, b)
if rootA < rootB:
parent[rootB] = rootA
else:
parent[rootA] = rootB
def solution(n, costs):
answer = 0
costs.sort(key=lambda x: x[2])
parent = [i for i in range(n)]
for cost in costs:
if find(parent, cost[0]) == find(parent, cost[1]):
continue
union(parent, cost[0], cost[1])
answer += cost[2]
return answer배운점
최소 신장 트리라는 것과 Union-find 라는 자료구조를 배울 수 있었다.
[DP] 사칙연산 (Lv.4)
걸린 시간
60분
접근 방식
이것도 각 구간을 나눠서 천천히 범위를 넓혀보는 DP스러운 방식으로 풀어보려고 했으나 +연산과 -연산을 각각 따로 생각해서 계산해야했기에 생각하는 과정이 꽤나 복잡했다.
결국 해설을 보고 확인한 결과 부호가 -일 때는 (최댓값)-(최솟값)이 최댓값이므로 DP를 할 때 최솟값을 저장하는 DP 배열 또한 존재해야 했던 게 관건이었다.
정답 코드
def solution(arr):
answer = -1
nums = []
operators = []
for a in arr:
if a.isdigit():
nums.append(int(a))
else:
operators.append(a)
M = [[-1000000000 for _ in range(len(nums))] for _ in range(len(nums))]
m = [[1000000000 for _ in range(len(nums))] for _ in range(len(nums))]
for step in range(len(nums)):
for i in range(len(nums)-step):
j = i + step
if step == 0:
M[i][j] = nums[i]
m[i][j] = nums[i]
else:
for k in range(i, j):
if operators[k] == '+':
M[i][j] = max(M[i][j], M[i][k]+M[k+1][j])
m[i][j] = min(m[i][j], m[i][k]+m[k+1][j])
else:
M[i][j] = max(M[i][j], M[i][k]-m[k+1][j])
m[i][j] = min(m[i][j], m[i][k]-M[k+1][j])
return M[0][len(nums)-1]배운점
DP를 최근에 풀었기 때문에 접근법 자체는 맞았지만 생각하는 과정에서 좀 더 지혜가 필요했던 것 같다.
