조준장 개발자 생존기

문제 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 알고리즘 - dfs 탐색을 통해 첫 번째 노드에서 제일 먼 노드를 찾는다. - 첫 번째 노드에서 제일 먼 노드의 번호를 찾는다. - 제일 먼 노드의 번호부터 다시 dfs 탐색을 통해 제일 먼 노드를 찾고 그때의 간선의 길이를 출력한다. 코드 import sys sys.setrecursionlimit(10 ** 9) # dfs 탐색 def dfs(x, y): # 각 노드와 연결된 노드를 확인 for a, b in graph[x]: # 탐색하지..

문제 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 알고리즘 - dfs 탐색을 통해 첫 번째 노드와 연결된 모드 노드의 가중치를 확인한다. - 첫 번째 노드에서 제일 먼 노드를 찾았다면 그 노드에서도 다시 가장 먼 노드의 가중치를 찾는다. - 그때의 가중치가 트리의 지름이 된다. 코드 import sys sys.setrecursionlimit(10 ** 9) # dfs 탐색 def dfs(x, y): # 시작 노드 번호, 현재 노드 가중치 # 반복문을 통해 현재 노드와 연결된 노드, 연결..

문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 알고리즘 - 반복문을 통해 트리를 생성한다. - 전위 순회, 중위 순회, 후위 순회를 하는 함수를 생성한다. - 함수를 생성할 때 각 순회에 특징에 따라 루트 노드 출력, 재귀적으로 왼쪽과 오른쪽 탐색을 할 수 있게 한다. 코드 import sys n = int(sys.stdin.readline()) tree = dict() # 반복문을 통해 트리 생성 for i in range(n): root, left, right = map(str, sys...

문제 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 예산 상한액을 정하고 반복문을 통해 예산을 배정한다. - 예산 상한액보다 요청된 예산이 크다면 예산 상한액을 배정하고 그게 아니라면 요청된 예산을 배정한다. - 배정한 예산액이 총 예산보다 크다면 상한 예산액을 줄여준다. - 반대로 총 예산이 배정한 예산액보다 크거나 같다면 상한 예산액을 늘려준다. 코드 import sys n = int(sys.stdin.readline()) budget = list..

문제 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 공유기를 설치할 간격을 정하고 그 간격으로 공유기를 설치했을 때 모든 공유기를 설치할 수 있는지 확인한다. - 모든 공유기를 설치하고도 더 설치할 수 있다면 설치 간격을 늘려준다. - 반대로 모든 공유기를 설치할 수 있거나 공유기를 설치할 수 없다면 간격을 줄여준다. - 가장 인접한 두 공유기 사이의 최대 거리를 출력한다. 코드 import sys n, ..

문제 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 알고리즘 - 반복문을 통해 숫자 카드를 확인한다. - 이분 탐색을 통해 상근이의 카드 중에 현재 카드가 있는지 확인한다. - 상근이가 뽑은 카드가 현재 숫자 카드라면 1을 출력하고 반복을 멈춘다. - 상근이가 뽑은 카드가 현재 숫자 카드보다 크다면 더 작은 카드를 뽑기 위해 카드의 범위를 내린다. - 반대로 현재 숫자 카드가 크다면 더 큰 카드를 뽑기 위해 카드의 범위를 올린다. - 이분 탐색 후에도 상근이의 카드 중에서 현재 ..

문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 반복문을 통해 랜선을 잘랐을 때 남은 랜선의 개수를 구한다. - 자르고 남은 랜선의 개수가 필요한 랜선의 개수보다 크다면 더 이상 랜선을 자를 필요 없기에 반복을 멈춘다. - 필요한 랜선보다 현재 자른 랜선의 개수가 크거나 같다면 랜선을 자를 길이를 늘려준다. - 반대로 필요한 랜선보다 현재 자른 랜선의 개수가 작다면 랜선의 길이를 줄여준다. - 필요한 랜선의 개수를 만들 수 ..

문제 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 반복문을 통해 절단기로 나무를 자른 후 가져갈 수 있는 나무의 높이를 구한다. - 가져갈 수 있는 나무의 높이가 가져가려 하는 나무의 높이보다 크면 더 이상 가져갈 수 있는 나무의 높이를 구하지 않아도 되므로 반복을 멈춰준다. - 가져갈 수 있는 나무의 높이가 가져가야 하는 나무의 높이보다 크거나 같으면 절단기의 높이를 올려준다. - 반대로 가져가야 하는 나무의 높이..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 기본적인 이분 탐색 문제로 가운데 수와 찾아야 하는 수가 똑같은지 확인한다. - 이분 탐색이 끝나고도 똑같은 수가 없다면 찾아야 하는 수가 없는 것이다. 코드 import sys n = int(sys.stdin.readline()) n_list = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 아기 상어가 먹을 수 있는 물고기가 없을 때까지 반복한다. - 아기 상어가 현재 이동할 수 있는 모든 곳을 탐색하고 이동한 곳에 아기 상어보다 크기가 작은 물고기가 있다면 힙에 추가한다. - 문제를 보면 위, 왼쪽 물고기부터 먹어야 하는 우선순위가 있다. 따라서 heapq 우선순위 큐를 통해 물고기를 먹는다. - 아기 상어의 크기와 먹은 물고기의 양이 같다면 아기 상어의 크기를 1 키운다. - 위 ..