1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 분석 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나 그래프를 인접 리스트로 저장 BFS를 수행하고 탐색할 때 각 노드의 거리를 리스트에 저장 2에서 저장한 리스트에서 임의의 노드와 가장 먼 노드를 찾고, 그 노드부터 BFS 다시 수행 3에서 저장한 거리 리스트 값 중 가장 큰 값을 이 트리의 지름으로 출력 풀이 """ 트리를 구성하는 노드 중 두 노드 사이의 거리가 가장 긴 것 정점개수V V개의 줄에..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 """ 두 정수 N, M(2 ≤ N, M ≤ 100) M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. """ import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] visited= [[False for j in range(m)] for i in r..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 분석 [1260번] DFS, BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. karla.tistory.com 풀이 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) n,m=map(int,input().split()) # 사람수, 친구관계수 list = [[] for _ in range(n+1)] for _ in..

2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 분석 자리수가 한 개인 소수 2,3,5,7부터 탐색 시작 자릿수가 두개인 현재수*10+a를 계산하여 소수인지 판단, 소수라면 재귀 함수로 자릿수를 하나 늘림 a가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우 제외 자릿수를 n까지 확장했을 때 그 값이 소수라면 해당 값 출력 풀이 """ 소수 7331 : 733, 73, 7 소수 (왼쪽부터 1,2,3,4 자리 모두 소수) n(1~8)자리 숫자 중 신기한 소수 찾기 """ impo..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 분석 트리 순회(전위 순회, 중위 순회, 후위 순회), DFS 1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 karla.tistory.com 풀이 import sy..

10829번: 이진수 변환 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000) www.acmicpc.net 풀이 n=int(input()) def DFS(x): if x == 0: return else: DFS(x//2) print(x%2, end='') DFS(n)