백준 | 1956번. 운동 - 플로이드에 대한 RE 풀이
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 19.
백준 | 5719번. 거의 최단 경로 - 다익스트라 문풀
⬛ 백준 5719번. 거의 최단 경로 - 다익스트라 문풀 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 17.
백준 | 1916번. 최소비용 구하기 - 다익스트라 문풀
⬛ 백준 1916번. 최소비용 구하기 - 다익스트라 문풀 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 17.
백준 | 1865번. 웜홀 - 벨만포드 문풀
⬛ 백준 1865번. 웜홀 - 벨만포드 문풀 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 17.
백준 | 1956번. 운동 - 플로이드 문풀
⬛ 백준 1956번. 운동 - 플로이드 문풀 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 17.
최단 경로| 다익스트라, 벨만포드, 플로이드 비교
최단 경로 알고리즘 1) 다익스트라 : one-to-all (가중치는 양수만) 2) 벨만-포드 : ont-to-all (가중치 음수도 가능, 음수 사이클 여부 판단 시 多 사용) 3) 플로이드 : all-to-all 1) 다익스트라 (dijkstra) 알고리즘 | One-to-One 출발 노드→ 다른 모든 노드로의 최단 거리 구하는 알고리즘 특징은 엣지 (가중치)가 모두 양수 시간 복잡도 : O(E logV) → 특정 노드 (1개)에서 다른 노드들(all)에 대한 최단 거리 구하라는 문제가 주어졌을 때 ‘다익스트라’를 떠올려라 ⬛ 다익스트라 알고리즘 수행 과정 1) 인접 리스트로 그래프 표현 2) 최단 거리 distance[] 1차원 배열 선언 → 최초 초기화 시 Integer.MAX_VALUE로 초기화..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 13.
백준 | 11657번. 타임머신 - 최단 경로 (벨만 포드) 문풀
⬛ 백준 11657번. 타임머신 - 벨만 포드 문풀 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 13.
백준 | 11404번. 플로이드 - 최단경로 (플로이드) 문풀
⬛ 백준 11404번. 플로이드 - 최단경로 (플로이드 문풀) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 13.
백준 | 1753번. 최단 경로 - 최단 경로 (다익스트라) 문풀
⬛ 백준 1753번. 최단 경로 - 다익스트라 문풀 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 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 13.
백준 | 9251번. 최장 공통 부분 수열(LCS) 찾기 - DP 문풀
⬛ 백준 9251번. 최장 공통 부분 수열(LCS) 찾기 - DP 문풀 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 11.
DP 알고리즘 | LCS (최장 길이 공통 부분 수열)
LCS (Longest Common Subsequence) 두 개의 문자열 X, Y가 주어졌을 때, X와 Y에서 공통으로 나타나는 부분 문자열을 찾고자 한다. 부분 문자열 길이가 최대가 되도록 부분 문자열 찾는 방법은 ? LCS 는 두 개의 문자열 X, Y가 주어졌을 때 공통의 부분 문자열 길이 최대값을 찾는 문제다. X = ABDCDC Y = ACADC => 두 문자열 최장 길이 공통 부분 수열은 길이 4의 "ACDC " 가 된다. DP[i][j] 의 정의 : 각 위치 인덱스를 각각 마지막 문자로 포함하는 두 문자열의 LCS 길이값 즉, A[i]와 B[j] 를 기준으로 경우를 나눠 D[i][j]에 최장 길이를 갱신해줘야 한다. => D[i][j]에 올 수 있는 값의 경우는 크게 4가지로 나눌 수 있다...
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 11.
백준 | 1890번. 점프 - DP 문풀
⬛ 백준 1890번. 점프 - DP 문풀 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 11.
백준 | 11053번. 가장 긴 증가하는 부분 수열 - DP 문풀
⬛ 백준 11053번. 가장 긴 증가하는 부분 수열 - DP 문풀 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 10.
백준 | 1912번. 연속합 - DP 문풀
⬛ 백준 1912번. 연속합 - DP 문풀 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 8.
백준 | 2579번. 계단 오르기 - DP 문풀
⬛ 백준 2579번. 계단 오르기 - DP 문풀 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 8.
이분 탐색 | Parametric Search 에 대한 이론 비교
Binary Search | 이분 탐색 = 이진 탐색 = 이분 검색 정렬된 데이터에서 특정 값을 찾기 위해 (특정 범위)를 절반으로 줄여나가면서 중앙값과 비교해가며 빠르게 탐색하는 기법이다. Parametric Search | 파라메트릭 서치 이러한 이분 탐색의 응용을 Parametric Search 라고 부르다. 최적화 문제를 결정 문제로 환원하면 더 쉽게 풀 수 있다면 고려해봐라 (1) 예, 아니오 판단할 함수 만들고 (2) 판단 함수를 활용하여, 이분 탐색 범위를 좁혀가면서 타겟값을 구하는 거다. 1) 최적화 문제 : 여러 해답 중 기준에 따라 최소, 최대값 등을 구하는 문제 : f(i) = 1 이 되는 i의 최솟값을 구하라 2) 결정 문제 : 예 아니오로 답할 수 있는 문제 : 어떤 i에서 f(i..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 7.
백준 | 2110번. 공유기 설치 - 이분 탐색 문풀
⬛ 백준 2110번. 공유기 설치 - 이분 탐색 문풀 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 6.
백준 | 2805번. 나무 자르기 - 이분 탐색 문풀
⬛ 백준 2805번. 나무 자르기 - 이분 탐색 문풀 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 6.
백준 | 2580번. 스도쿠 - 백트래킹(DFS) 문풀
⬛ 백준 2580번. 스도쿠 - 백트래킹(DFS) 문풀 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 4.