코딩고치

1. 문제 주소: https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 문제 유형: 트리 2. 소스코드 import sys class Node: def __init__(self, data, left, right): self.data = data self.left = left self.right = right def preorder(node): print(node.data, end='') if node.left != '.': preorder(tr..

1. 문제 주소: https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제 유형: BFS, 이진 탐색 중량 제한이 1,000,000,000이므로 일반적인 탐색으로 풀 수 없음 log나 $\sqrt{}$를 이용하는 방식으로 풀여야 함 (약 3,000,000개로 연산이 줄어듦) 각 노드와 간선을 입력받은 후 중량의 최댓값과 최솟값을 찾음 BFS로 간선을 확인하면서 현재 중량으로 다리를 건널 수 있는지 확..

1. 문제 주소: https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 문제 유형: 2진 탐색 집의 좌표가 1,000,000,000이므로 이진 탐색을 이용해야 함 시간 복잡도: O(NlogX) 공유기 사이의 거리의 최솟값과 최댓값을 계산 최솟값과 최댓값을 이용하여 중간값을 계산 중간값을 이용하여 c개만큼의 공유기를 설치할 수 있는지 확인 설치할 수 있으면 최솟값 = 중간값 + 1, 설치할 수 없..

1. 문제 주소: https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 문제 유형: 탐색 경비원의 수를 받기 위한 행과 열 리스트 선언 경비원의 위치를 입력받고 경비가 있는 곳을 파악한 후 리스트에 저장 행의 부족인원이 열의 부족인원보다 많으면 행의 부족인원수를 출력 열의 부족인원이 더 많으면 열의 부족인원 출력 2. 소스코드 import sys def guard(n, m): col = [0 for i in range(n)] row = [..