1. 문제정보 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 해결전략 처음 생각했던 전략은 리스트를 오름차순으로 정렬하고 합계를 더해가는 방식으로 구현했습니다. 입력 횟수가 최대 10만번 이기 때문에 입력 시간을 줄이기 위해 readline을 사용했지만 리스트를 이용한 방법은 연산 횟수가 최대 10만x10만으로 시간 초과를 받았습니다. 결국 우선순위큐에 대한 힌트를 확인한 후 우선순위큐로 구현하였습니다. 3. 코드 impo..
1. 문제정보 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 해결전략 BFS와 다익스트라를 우선으로 고려했습니다. 문제 해결의 키 포인트는 간선 그래프를 작성하는 것입니다. 3. 코드 import sys import heapq INF = int(1e9) MAX = 100001 visited = [False] * MAX distance = [INF] * MAX input = sys.stdin.readlin..
1. 문제정보 https://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 2. 해결전략 최단 거리를 구하는 문제이기 때문에 다익스트라 알고리즘을 우선으로 고려했습니다. 다만 간선의 입력이 최대 30만개 이기 때문에 입력 부분을 개선하였습니다. 3. 코드 import sys import heapq input = sys.stdin.readline v, e = map(int, input().split()) start = 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 해결전략 노드, 간선, 가중치가 주어지고 최단 거리를 구하는 문제입니다. 다익스트라를 이용해서 해결이 가능하지만 일반적인 다이스트라로는 시간 초과가 발생합니다. heapq를 이용하여 가중치가 가장 작은 노드를 얻으면서 복잡도를 낮출 수 있습니다. 코드 (정답 코드) import sys import heapq input = sys.stdin.readline I..