문제 풀이/백준 알고리즘

[baekjoon 17298] 오큰수 (스택) (C++)

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 현재 수의 오른쪽에 있는 수 들 중 나보다 큰 가장 왼쪽의 수를 출력하는 문제이다. 즉, 1 9 8 10 이면 1의 오큰수는 9(큰 수 중 바로 왼쪽), 9의 오큰수는 10, 8의 오큰수는 10, 10의 오큰수는 없기에 -1을 출력하면 된다. 또한 입력값의 범위는 백만으로, 매 수마다 오른쪽 범위로 반복문을 돌려서 나보다 큰 수를 찾는 2중 for문을 이용하면 시간 초과가 날 것이다. 따라서, 스택 자료구조..

[baekjoon 15961] 회전 초밥 (슬라이딩 윈도우, 두 포인터) (C++)

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 회전 초밥처럼 입력된 값을 돌면서 연속해서 먹을 수 있는 K개 중 서로 다른 종류의 초밥이 최대 몇 가지 있을 수 있는지 푸는 문제이다. N이 최대 300만이므로 N^2은 당연히 시간 초과가 난다. 이렇게 K개의 수를 한번 훑어야 하는 경우 보통 슬라이딩 윈도우를 이용하면 O(N)만에 연산을 마칠 수 있다. 또한, 나는 가짓수를 관리해줄 때 map 자료..

[baekjoon 2021] 최소 환승 경로 (BFS, 0-1 BFS, 다익스트라) (C++)

https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 지하철 노선과 그 노선을 지나는 역의 개수가 주어진다. 이 정보를 갖고 어떻게 그래프화 시켜서 이동을 할까 고민을 했는데, 해당 역을 지나는 노선 정보와 노선을 지나는 역, 이 두 개를 저장했다. 10 3 1 2 3 4 5 -1 // 1번 노선 9 7 10 -1 // 2번 노선 7 6 3 8 -1 // 3번 노선 1 10 의 경우 route벡터에는 노선 번호에 해당하..

[baekjoon 2307] 도로검문 (다익스트라) (C++)

https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 용의자가 주어진 그래프를 빠져나가려는데, 그래프 중 하나의 간선을 막아서 얼마나 지연시킬 수 있는지 출력하는 문제이다. 구역은 최대 1000개, 간선의 개수는 최대 5000개가 주어진다. 따라서 완전 탐색으로 모든 도로를 지우며 비교하는 것은 시간 초과가 날 것이다. 우선 1번부터 N번까지 최단 거리를 구해야 하므로 다익스트라를 이용하고, 최단 거리가 나오는 경로를 구해서 그 경로에 해당하는 도로만 지우..

[baekjoon 21276] 계보 복원가 호석 (트리, 위상정렬, 맵) (C++)

https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 가문의 족보를 복원해야 하는 문제이다. 각 가문은 tree구조이고, 각 주민의 조상이 주어지는데 조상은 자신의 부모 또는 부모의 부모가 포함되어 있다. 따라서 이 문제를 풀기 위해서 필요한 것은, 순서 관계에 의해 주어진 입력값을 위상 정렬하는 것과 문자열로 주어진 입력값을 맵을 이용 해서 인덱싱 해주는 것이 필요하다. 전체적인 풀이 과정은 1. 입력값을 map을 이용해서 문자열, 숫..

[baekjoon 11779] 최소비용 구하기2 (다익스트라) (C++)

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 최소비용 구하기 1의 업그레이드 버전이다. 추가된 것은 최소비용뿐만 아니라 최단 거리를 출력하는 것이다. https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지..