https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 평범한 다익스트라 문제에 방문하지 못하는 정점의 조건을 더한 문제이다. 중간에 현재 방문한 정점과 연결된 정점이 방문할 수 있는 정점인지를 확인하는 조건문을 추가했다. import sys, heapq N, M = map(int, input().split()) check = list(map(int, input().split())) graph = [[] for _ in ra..
알고리즘💻/우선순위큐&다익스트라
https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 정점 1에서 V까지 가는 최단경로 중에 P를 지나는 경로가 존재하면 "SAVE HIM", 존재하지 않으면 "GOOD BYE"를 출력하는 문제이다. 최단경로를 찾는 데는 다익스트라 알고리즘을 사용하여 구현하였고, 기존 다익스트라 문제와 다르게 경로를 체크해야 하므로 save 배열을 따로 만들어 경로 중에 P가 있으면 True가 되도록 하였다. 또한..
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐를 이용하는 건데.. 내가 파이썬의 heapq 라이브러리를 착각했다. 우선순위 큐는 정렬이 된 상태랑은 다른 건데 자동으로 정렬이 된다고 생각해서 1차로 틀렸고 그 이후에는 다른 풀이들을 보며 힌트를 좀 참고했다. https://regularmember.tistory.com/142 이 블로그의 설명이 제일 이해하기 쉬웠는데, 이해하고 나니 알겠더라는,,, 근데!!! 파이..
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 알고리즘을 이용하여 풀 수 있는 문제였다. v1, v2를 지나야 하므로 가능한 경로는 두 가지 이다. 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 따라서 시작점을 1, v1, v2로 다익스트라를 실행하여 각각의 경우에 맞는 값을 구한 뒤 더하여 더 짧은 거리를 출력하면 된다. 경로가 없는 경우에 -1을 출력해야 한다는 ..
https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 꽤나 오래 걸린 문제였다.. 처음에는 어라 그냥 BFS로 탐색해도 될 것 같은데..? 하고 풀었더니 시간 초과가 나서.. 우선순위큐와 다익스트라를 이용해서 풀어보려고 했는데 머릿속에서 최단경로(?) 를 구하는 문제와 섞여서 로직을 생각하는 게 어려웠다. 또한 다 구현해놓고 왜 답이 안나오지 하다가.. [N-1][N-1] 에 도착하면 반복문을 종료해야 된다는 걸 뒤늦게 깨달았다.. 이렇게 구현해도 python으로는 시간초과가 났고 pypy3로 통과할 수 있었는데, 100프로에서 인덱스에러가 난 것은 질문 칸에 고마운..
www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 아이디어: 문제 이름 그대로 최대 힙을 구현하면 된다. 그런데 파이썬에서 제공하는 heapq 모듈은 최소힙이므로, 최대힙을 구현하려면 튜플을 이용하여 - 추가하는 첫번째 원소가 우선순위가 되고 이걸 기준으로 최소힙으로 정렬되므로 - 구현해야 한다. 출력할 때는 [1]번 원소를 출력하면 된다. #11279번 최대 힙 import sys, heapq N = int(sys.stdin.readlin..
www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 www.acmicpc.net 아이디어: 차량은 가로나 세로방향으로만 움직이므로 현재 위치에 인접한 정점은 상하좌우 좌표라고 할 수 있다. 그럼 인접한 정점을 이동하면서 최소 비용을 업데이트하면 되지 않을까? 했는데 해결됐다!ㅎㅎ 그냥 다익스트라 알고리즘과 똑같이 구현하면 된다. import sys, heapq m, n = map(int, sys.stdin.readline().split..
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를 사용하..
