국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 + a 1. 문제 설명 - 여행계획을 짜려고 하는데 나라들이 연결되어만 있으면 여행을 갈 수 있다. 나라들이 연결되어 있는 정보와 여행 일정에 대한 입력이 들어오면 해당 여행 일정이 가능한지 출력을 하는 문제 2. 접근 방식 - 그래프 알고리즘을 이용해서, 여행일정에 해당하는 노드들이 서로 연결되어 있는지 확인하면 된다. - 여행일정에 해당하는 노드들이 서로 연결되어 있다는 것은 하나의 집합(부모)에 묶여있다는 뜻이라고 생각할 수 있다. 3. 코드 n, m = map(int, input().split()) ls = [] for _ in r..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 비행기는 도킹할 수 있는 탑승구가 정해져 있다. 하지만 탑승구에 도킹해있는 비행기가 있으면 다른 비행기는 도킹할 수 없다. 탑승구에 더 이상 도킹이 불가능할 때까지 비행기를 받고자 할 때, 최대로 받을 수 있는 비행기는 몇 대인가? 2. 접근 방식 - 서로소 집합 알고리즘을 활용해서 문제를 풀 수 있다. - 0번째 집합(parent[0])까지 만든다. 집합을 주어진 순서대로 앞선 원소와 묶어가다가 0번째 집합에 묶이면 반복을 종료한다. 3. 코드 def find_parent(parent, a): if parent[a] ..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 마을에 설치되어 있는 가로수를 줄여서 비용을 줄이려고 한다. 가로수를 줄였을 때 절약할 수 있는 금액의 최대를 출력하는 문제 2. 접근 방식 - 최소비용으로 모든 노드를 연결하는 문제(크루스칼 알고리즘) - 추후 간선의 길이가 길어질 것을 대비해 heapq를 활용해서 구해봤다. 3. 코드 def find_parent(parent, a): if parent[a] != a: parent[a] = find_parent(parent, parent[a]) return parent[a] def union_parent(parent,..

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

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 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..