복습

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 아이디어: 플로이드-와샬 알고리즘을 이용하여 푸는 문제이다. 플로이드-와샬 알고리즘은 모든 정점 쌍에 대한 최단경로를 구할 수 있는 알고리즘으로, dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) 를 이용하여 구현하면 되고 시간복잡도는 O(V^3)이다. 이 문제에서는 친구 관계를 입력받으면서 dist[A][B]=dist[B][A]=1을..

www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 아이디어: 벨만-포드 알고리즘을 구현하여 푸는 문제는 맞는데, 조건을 따질 게 좀 있어서 헤맸다. 1. N, M, W를 TC for 문 안에서 받아야 하는데 바보처럼 밖에서 받음. 2. 도로는 양방향이고, 웜홀은 단방향임.. 3. 음수 사이클이 어디서 시작하는 지는 상관없이 존재 유무만 판단하는 것이므로, 1에서만 탐색하면 안되고 방문하지 않은 모든 정점을 탐색해야 함. import sys TC =..

www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 아이디어: 벨만-포드 알고리즘을 이용하여 최단경로를 구해야한다. 다익스트라 알고리즘은 간선의 가중치가 음수인 경우에는 사용하지 못하기 때문이다. 벨만-포드 알고리즘의 시간복잡도는 O(VE)이다. 벨만 - 포드 알고리즘은 존재하는 모든 간선을 V-1번 돌아보면서 이 간선을 통할 수도 있는 최단경로들의 거리를 갱신하는 것이다. 왜 V-1번 이냐면 최단 경..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 아이디어: 앞선 다익스트라 구현 문제와 똑같은 문제이다. 이것도 기본문제니까 다시 풀어보자. import sys, heapq N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) graph = [[] for _ in range(N+1)] for _ in range(M): s, e, w = map(int, sys.stdin.r..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 아이디어: 다익스트라 알고리즘을 활용하여 푸는 기본적인 문제이다. 다익스트라 알고리즘은 최단경로를 구하는데 사용하는 알고리즘이다. 시작정점으로부터 거리가 가장 작은 정점부터 방문하여 최소경로를 계속 갱신하는 방식이다. 이론은 이해가 가지만 구현하는 게 아직 익숙하지 않아서 어려웠다. 힙을 사용하여 시작정점으로부터의 거리를 저장하는 방식과, 이미 방문한 노드를 거르는 조건에 주의하자. ..

www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 아이디어: 처음에는 저번에 다른 회의실 문제를 풀었을 때처럼 종료시간을 기준으로 정렬하였다. 근데 그렇게 풀다보니 풀리지 않는 경우가 발생하였다. 4 1 3 2 4 4 8 3 9 이와 같은 경우에는 4 8 강의를 2 4 강의실에 배정해야 하는데 1 3 강의실에 배정이 되어서 오답이 나온다. 그래서 질문을 찾아보니.. 이 문제는 시작시간을 기준으로 정렬을 해서 풀어야 하는 문제였다. heapq를 사용하고, 끝나는 시간을 저장하는 배열end도 heapq를 사용하..

www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 아이디어: 이번에는 전위순회와 후외순회를 가지고 중위순회를 구하는 문제이다.. 앞선 문제와 비슷하게 풀 수 있을 것 같다. 전위순회는 제일 첫번째 원소가 루트니까 루트를 일단 찾으면 중위순회를 오른쪽, 왼쪽 서브트리로 나눌 수 있다. 그리고 후위순회는 루트를 제일 마지막에 출력하니까 배열에 순서대로 저장한 후 반대로 출력하면 될 것 같다. 익숙해지면 이 유형 문제는 빠르게 풀 수 있을 것 같다! #4..

www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 아이디어: 이진트리 / 입력의 첫줄은 inorder = 중위순회, 둘째줄은 postorder = 후위순회.. -> 전위순회 구하기. 중위순회(LVR) 후위순회(LRV) -> 맨 마지막 원소가 루트. 전위순회(VLR) -> 후위순회에서 중위순회를 사용하여 루트를 순서대로 뽑아내면 된다. 중위순회는 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누어지므로, 후위순회[-1](루트)를 중위순회에서 찾고그 인덱스-1까지를 후위순회에서 잘라서 다시 ..

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 아이디어: 트리의 지름에 대한 증명이 있다. 1. 트리에서 임의의 정점 x를 잡는다. 2. 정점 x에서 가장 먼 정점 y를 찾는다. 3. 정점 y에서 가장 먼 정점 z를 찾는다. -> y-z의 경로가 트리의 지름이다. 이 알고리즘? 정의? 를 이용해서 풀어보자. DFS와 재귀를 이용하여 구현했는데, 답은 제대로 나오는데 시간초과가 난다. pypy로 제출해도..ㅠㅠ import sys sys...

www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 아이디어: 모르겠어서 구글링했다. 전위순회니까 입력받는대로 노드를 삽입하면 그래프를 구할 수 있었다. 그.런.데. 정석대로(?) 풀면 파이썬은 시간 초과가 났다.. #시간초과 import sys sys.setrecursionlimit(10**9) class Node: def __init__(self, num): self.val = num self.left = None self.right = None..