국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 30분 + a 1. 문제 설명 - 상, 하, 좌, 우로 탐색할 수 있는 화성 로봇이 있는데 (0, 0)지점부터 (n-1, n-1)까지 갈 때의 최단 경로를 구하기 2. 접근 방식 - 처음에는 플로이드 워셜 알고리즘을 활용하려고 했는데, 생각해보니 시간이 너무 오래걸릴 거 같았다. 그래서 다익스트라 알고리즘을 활용하기로 했다. - 다익스트라 알고리즘의 경우 그래프에서 입력을 받아 이를 하나씩 꺼내면서 진행된다. 해당 문제의 경우 특정 노드를 기준으로 그래프에서 상, 하, 좌, 우에 해당하는 부분에 방문해서 비용을 계산하는 방식으로 코드가 알고리즘이..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 30분 1. 문제 설명 - 학생들의 성적을 누구보다 높다, 낮다로만 나눌 때, 정확한 위치를 알 수 있는 학생의 수를 출력하는 문제 2. 접근 방식 - 플로이드 워셜 알고리즘을 사용한다. - 단, 각 학생들별 연결을 확인할 때, graph[i][j]와 graph[j][i] 방향 모두를 확인해야 한다. (i -> j 방향, j -> i 방향) 3. 코드 n, m = map(int, input().split()) INF = 1e9 graph = [[INF]*(n+1) for _ in range(n+1)] for a in range(1, n+1): g..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 플로이드 워셜 알고리즘 구현 문제 2. 접근 방식 - 플로이드 워셜 알고리즘을 사용 - 단, 입력을 받을 때도, 동일한 위치에 cost값이 변형 될 수 있기에 조건을 넣어줘야 한다. (처음에 이 부분을 안 넣어서 오류가 났었음) 3. 코드 import sys n = int(input()) m = int(input()) INF = 1e9 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: gra..

오늘은 '이코테' 최단경로 부분 진도를 나갔다. 비슷한 문제가 반복되는 것 같아서 하루만에 4문제 다 풀 수 있을 것 같기도 했는데 괜히 머리가 띵한 것 같고, 생각도 잘 안돼서 오늘은 2문제만 풀었다. 2문제 전부 Floyd알고리즘을 사용하는 문제였는데, 뭔가 자잘한 실수가 계속해서 나와서 시간이 조금씩 더 걸렸었던 것 같다. 그리고 알고리즘을 적용하는 것뿐만이 아니라 알고리즘을 거쳐서 나온 값을 어떻게 활용할 것인지에 대해서도 생각해야 할 필요가 있다는 것을 느꼈다. 내일은 일이 있어서 문제를 풀 수 있을지 모르겠지만, 한 문제라도 꾸준하게 풀 수 있도록 해야겠다. 오늘 한 일 - 이코테 최단경로 문제 2개 내일 할 일 - 이코테 최단경로 문제 2개

1. 문제 설명 도시와 도시가 연결되어 있을 때 전보를 보내는 경우 얼마나 많은 도시에 보낼 수 있으며, 가장 먼 거리는 얼마인지 구하는 문제이다. - 다익스트라 알고리즘을 활용한 문제로 heapq를 활용한다. 2. 코드 import heapq # 입력 INF = int(1e9) a, b, start = map(int, input().split()) graph = [[] for _ in range(a+1)] distance = [INF]*(a+1) for _ in range(b): x, y, z = map(int, input().split()) graph[x].append((y, z)) # 노드, 거리 # 다익스트라 알고리즘 def dijkstra(start): q = [] heapq.heappush(q..

1. 문제 설명 미래도시 쿠팡맨이 N개의 도시들을 돌아다니면서 배달을 하는데, 특정 노드 (K) 를 지나서 노드 (X)에 도착하려고 할 때 몇 개의 도시를 지나가야 하는지를 묻는 문제이다. 각 도시와 도시가 연결된 간선의 비용은 1로 동일하다. - 전형적인 플로이드 워셜 알고리즘의 문제이다. - 플로이드 알고리즘의 경우 대칭행렬이 아니기 때문에 그냥 계산해도 양방향을 고려한 그래프가 된다. 2. 코드 # INF = int(1e9) n, m = map(int, input().split()) graph = [[INF]*(n+1) for _ in range(n+1)] for a in range(n+1): for b in range(n+1): if a==b: graph[a][b]=0 for _ in range(..