문제 풀이

[프로그래머스 카카오 블라인드 채용 2021 4번] 합승 택시 요금 (다익스트라, 플로이드와샬) [C++]

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 밤늦게 귀가할 ..

[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벡터에는 노선 번호에 해당하..

[프로그래머스 LV3] 단어 변환 (BFS, DFS) [C++, JAVA]

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 단어 집합이 주어지고, 시작 단어에서 타깃 단어까지 몇 번만에 바꿀 수 있는지 리턴하는 문제이다. 그 대신, 단어는 한 글자만 바꿀 수 있다. 나는 처음에 DFS+백트래킹으로 단어의 문자 알파벳 하나하나를 바꿔가면서 ex) abc bbc cbc dbc ebc... 만약에 그 단어가 단어 집합에 ..

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

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