국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 40분 1. 문제 설명 - 숨바꼭질을 하는데 술래는 1에서 출발한다. 이때 계산 결과 1번에서 다른 노드의 최단거리 중 술래와 가장 먼 거리에 숨으면 가장 괜찮다는 것을 알아넀다. 그래서 숨는 위치, 가장 먼 최단거리, 이와 같은 값을 가지는 노드의 개수를 출력하는 문제 2. 접근 방식 - 다익스트라 알고리즘을 활용한다. - 단, 단방향이 아닌 양방향이기 때문에 input을 받을 때 그래프를 양방향에서 받는 느낌으로 넣어줘야 한다. a, b가 (input)으로 들어온다면, graph[a].append(b), graph[b].append(a) 둘 ..

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