https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. Preview 시간 복잡도: O(M*logM) 공간 복잡도: O(M) 참고 : - 유형: MST 2. 초기 접근 방법 MST(Minimum Spanning Tree) 알고리즘 그래프 내의 모든 정점을 포함하는 트리를 구성하는데, 구성 간선들의 가중치 합의 최소를 목표로 한다. 프림 알고리즘 : 방문한 노드의 미방문 노드 간선들 중 최소 간선을 선택 - ..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에www.acmicpc.net   1. Preview시간 복잡도: O(V+E) 공간 복잡도: O(V or E) 참고 : https://ji-gwang.tistory.com/293 유형: dfs, bfs   2. 초기 접근 방법이분 그래프: 인접한 정점끼리 서로 다른색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프   2개의 집합을 두고, 인접 노드를 번갈아 저장하는 이상한 방식으로 문제를 접근해 관련 내용 정리는 생..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. Preview 시간 복잡도: O(2N^2) 공간 복잡도: O(2N^2) 참고 : https://hongcoding.tistory.com/18 (최적화) 유형: bfs 2. 초기 접근 방법 1개의 벽을 부술 수 있는 "item"이 있다고 생각하자. 기존의 visited 배열에서는 item 사용 유무를 판단할 수 없으므로 visited[i][j] → visited[i][..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. Preview 시간 복잡도: O(NlogM*N) N : 현재 노드와 연결된 간선 수 (최대 N) logM : 간선 heap 추출 N : N번의 다익스트라 공간 복잡도: O(M) 참고 : - 유형: 다익스트라 2. 초기 접근 방법 'i에서 X까지의 소요시간' 과 'X에서 i까지의 소요시간' 을 구한 뒤 가장 오래 걸리는 소요시간을 구하면 된다. # x에서 i까지..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 1. Preview 시간 복잡도: O(3(V+E)) 공간 복잡도: O(N) 참고 https://frog-in-well.tistory.com/68 https://ddingmin00.tistory.com/entry/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-9370%EB%B2%88-%EB%AF%B8%ED%99%95%EC%9D%B8-%EB%8F%84%EC%B..

https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 1. Preview 시간 복잡도: O(N^2) 공간 복잡도: O(N^2) 참고 : https://burningjeong.tistory.com/525 유형: 수학 2. 초기 접근 방법 각도에 따라 의자를 배치하도록 했다. 하지만 이 방법은 부동소수점 오차로 인해, 기존에 놓았던 각도인지 판별이 불가능하다. circle = set() for i in range(a, b+1): init = 360 / ..