2020 kakao blind recruitment
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60057
내가 생각한 문제 풀이
[시도1]
최단거리 문제니까 단순하게 다익스트라로 풀자고 결정
다익스트라 알고리즘 파이썬 코드를 찾아보니까 이중 리스트 구조가 많아서 그걸 사용
어설프게 알고 이유 없이 코드 구현 방식 선택 : 시간 날림
[시도2]
모든 지점에서 다른 모든 지점까지를 구해야 중간에 합승을 그만두는 시점에서 최단 거리를 구할 수 있으리라 생각해 플로이드 워셜 알고리즘으로 변경
플로이드 워셜 알고리즘으로 2차원 배열을 만들어서 각 출발점에서 도착점까지의 최단 거리를 구함. 그 후 합승에서 내리는 지점을 1~n까지 돌며 최솟값 찾음
시간 / 결과 / 패착
소요 시간 : 약 60분?
결과(정확도) : 85/100
패착 :
생각 안함
어떤 알고리즘을 쓸지 생각을 안했고, 플로이드워셜/다익스트라는 진짜 많이 했는데도 알고리즘 자체를 까먹음 ;;
이유는 알 수 없지만 최댓값을 적용할 때 바로 다음 수가 아니라 아예 큰 수를 하는 게 낫다
요금 최대값이 100000원이어서 max를 100001로 두고 문제를 풀었는데 계속 85점이 나왔다. max를 inf로 바꾸니까 해결되었음
문제 해설
플로이드 워셜 알고리즘을 사용 할 수도 있고, 다익스트라로 문제를 풀 수도 있다.
n의 수가 충분히 작기 때문에 플로이드 워셜로 풀어도 시간초과가 나지 않는다.
일반적으로 다익스트라 알고리즘이 플로이드 워셜보다 빠르다고 알려져 있다.
플로이드 워셜 알고리즘의 경우 나의 풀이가 해답이다.
[다익스트라 알고리즘]
다익스트라 알고리즘은 시작점이 정해져있고 거기서부터 모든 노드로의 거리를 구할 수 있다.
그냥 시작점을 for문으로 다 구하는 거다.. 별반 다를 건 없다
코드
def solution(n, s, a, b, fares):
answer = 0
graph = [[inf]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
if i == j:
graph[i][j] = 0
for start, end, fare in fares:
graph[start][end] = fare
graph[end][start] = fare
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
answer = graph[s][a] + graph[s][b]
for i in range(1, n+1):
temp = graph[s][i] + graph[i][a] + graph[i][b]
if temp < answer:
answer = temp
return answer
추가 공부
두 알고리즘의 차이점 :
다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 문제'
플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 문제'
두 알고리즘은 greedy 및 dp의 한 유형으로 볼 수 있다
그리디 알고리즘 : 각 단계에서 가장 최선의 선택
다이나믹 프로그래밍 : 전체 문제를 여러 개의 작은 문제로 풀고 그것을 결합해서 최종 목적
플로이드 워셜 알고리즘
1) 이차원 배열을 생성하고 모든 값을 무한으로 초기화한다
2) 자기 자신에서 자기 자신으로 가는 비용을 0으로
3) 출발/도착/비용값을 그래프에 반영
4) k라는 지점을 통해서 i에서 j로 이동하는 비용 vs i에서 j로 이동하는 기존 비용 비교해서 최소값 반영
INF = int(1e9)
# 2차원 배열 생성, 모든 값 무한 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자기 자신에서 자기 자신으로 가는 비용 0으로 초기화
for i in range(1, n+1):
graph[i][i] = 0
# temp = [start, end, money]
# 유향 그래프 가정
for t in temp:
graph[start][end] = money
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
다익스트라 알고리즘
다익스트라 알고리즘은 visited라는 배열을 두고 구현하는 방법이 있고,
heapq를 사용하여 최단 거리 여부로 visited 배열을 판단하는 방법이 있다.
후자가 더 빠르기 때문에 후자만 사용한다.
음의 간선이 없을 때 정상적으로 동작
음의 간선이 없어야 하는 이유 : 다익스트라 알고리즘은 근시안적 관점을 유지하기 때문에 가중치가 감소하는 것을 고려하지 않는다.(그리디 알고리즘이기 때문에 당시 가장 나은 해답을 찾기 때문에 한 수 뒤에 마이너스가 있어 비용이 줄어드는 것을 고려하지 못한다)
음의 간선이 있는 경우 : bellman-ford 알고리즘 사용
이 알고리즘은 모든 경우의 수를 검사하기 때문에 음수 가능
준비물 : visited 리스트(방문 여부 확인) distance 리스트(현재까지 최단 거리) graph(어떤 모양이든 거리 나타내는 리스트)
1) 출발 노드를 설정한다
2) 최단 거리 테이블을 초기화한다
3) 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다
4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다
맨 처음에 start 디폴트로 해준 다음에 반복문(첫번째 빼고 n-1번) 안에서 now(not visited 중 최단 거리)와 연결된 노드 점검(now를 통하는 게 더 비용이 작은지
각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하며 계속 갱신
현재 처리하고 있는 노드 기준으로 주변 간선 확인
1) visited 배열을 두고 구현
O(V^2) 노드 개수 10000개 이상이면 시간초과
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)
# temp = [start, end, money]
# 유향 그래프 가정
for t in temp:
graph[start].append((end, money))
def get_smallest_node():
index = 0
answer = INF
for i in range(1, n+1):
if distance[i] < answer and not visited[i]:
index = i
answer = distance[i]
return index
def dijkstra(start):
visited[start] = True
distance[start] = 0
for node, edge in graph[start]:
distance[node] = edge
for i in range(n-1):
now = get_smallest_node()
visited[now] = True
for node, edge in graph[now]:
distance[node] = min(distance[node], distance[now]+edge)2) 힙 사용
O(ElogV)
최단 거리가 가장 짧은 노드 찾는 시간을 단축
최단 거리를 힙에 담아서 처리 : 개선
visited list -> heap
heap에서 튀어나온 거리가 distance에 저장된 거리보다 크다면 이미 처리된 것이다
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
def dijkstra_heap(start):
heap = []
heapq.heappush(heap, (0, start))
distance[start] = 0
while heap:
dist, now = heapq.heappop(heap)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(heap, (cost, i[0])출처 : 이것이 취업을 위한 코딩 테스트다
그 외의 경로, 그래프 관련 알고리즘
벨만 포드 알고리즘 : 모든 edge에 대해 계산 수행
D(s, v) = D(s, u) + D(u, v)
크루스칼 알고리즘 : 최소 비용 신장 트리(acyclic하면서 최소 비용인 트리)
간선 정렬 후에 사이클 발생 여부 확인하여 최소 신장 트리에 포함
tip for me
만약 중요한 코테가 있다면 이런 알고리즘 복습하자
나는 .. 그래프를 잘 못다룬다 ㅜ
