[BaekJoon] LCA - 11437 (Gold III, Python3)
문제 링크 성능 요약 메모리: 273764 KB, 시간: 1044 ms 분류 그래프 이론, 최소 공통 조상, 트리 제출 일자 2024년 3월 29일 16:40:19 문제 설명 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은 두 정점..
2024. 4. 22.
[BaekJoon] 거의 소수 - 1456 (Python3, Gold V)
문제 링크 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 성능 요약 메모리: 111368 KB, 시간: 2920 ms 분류 수학, 정수론, 소수 판정, 에라토스테네스의 체 제출 일자 2024년 4월 15일 17:09:48 문제 설명 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총..
2024. 4. 22.
[이취코] 미래도시 (Python3)
Problem: 최단 경로 알고리즘 - 플로이드워셜 (FLoyd-Warshall) 플로이드 워셜을 적용한 코드 INF = int(1e9) n, m = map(int, input().split()) graph = [[INF] * (n+1) for i in range(n+1)] # 자기 자신인 경우, 0으로 초기화 for a in range(1, n+1): for b in range(1, n+1): if a == b: graph[a][b] = 0 # 간선에 대한 정보, 거리는 다 1로 초기화 for _ in range(m): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 x, k = map(int, input().split()) # 플로이..
2024. 3. 6.
