조준장 개발자 생존기

문제 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net 알고리즘 - 문제를 해석하면 결국 두 노드의 가장 가까운 부모 노드를 찾는 것이다. - 부모 노드는 자식 노드에서 2로 나눈 값을 가진다. - 두 노드의 부모 노드가 같을 때까지 반복하여 두 노드의 가장 가까운 부모 노드를 찾는다. 코드 import sys n = int(sys.stdin.readline()) # 테스트 케이스만큼 반복 for _ in range(n): a, b = map(int, sys.stdin.readlin..

문제 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 알고리즘 - 산술 평균은 round() 함수를 통해 수행한다. - 중앙값은 오름차순으로 정렬 후 중간에 있는 정수를 출력한다. - 최빈값은 collection 모듈의 Counter 클래스를 사용한다.(Counter 클래스에서도 most_common() 함수를 사용해도 됨) - 범위는 최댓값에서 최솟값을 빼준 값을 출력한다. 코드 import sys from collections import Counter n = int(sys.stdin.readline()) m = [in..

문제 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 알고리즘 - 각 노드의 부모 노드를 저장한다. - 공통 조상을 구하려는 두 노드는 따로 저장하여 두 노드의 부모 노드들을 찾는다. - 두 노드의 부모 노드를 레벨별로 비교하여 제일 마지막에 같았던 부모 노드를 구한다. - 제일 마지막에 같았던 부모 노드가 가장 가까운 공통 조상 노드가 된다. 코드 import sys t = int(sys.stdin.readline()) # 테스트 케이스만큼 반복 for _..

문제 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 알고리즘 - 후위 순회에서 끝점이 루트 노드인 것을 이용한다. - 중위 순회에서 루트 노드 기준으로 서브 트리 노드가 좌, 우로 나뉘는 것을 이용한다. - 위 두 가지 성질을 이용하여 분할 정복을 재귀적으로 수행한다. - 분할 정복을 수행할 때 각 트리의 루트 노드를 출력한다. 코드 import sys sys.setrecursionlimit(10**9) # 분할 정복 def divide(in_start, in_end, post_start, post_end): # 중위 순회 시작점과 ..

문제 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 알고리즘 - 분할 정복을 통해 문제를 수행한다. - 문제를 보면 중위 순환을 통해 빌딩을 방문한 것을 확인할 수 있다. - 중위 순환이고 완전 이진 트리이기 때문에 중간에 있는 노드가 루트 노드가 된다. - 루트 노드를 찾고 왼쪽 서브 노드와 오른쪽 서브 노드를 나눠 각 트리를 재귀적으로 탐색한다. 코드 import sys sys.setrecursionlimit(10 ** 9) # 분할 정복 def divide(start, end,..

문제 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, ..