oVeron

https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 문제의 기본적인 토대는 평범한 벨만-포드 알고리즘이다. 이 문제가 G1인 이유는, 사이클이 존재할 때 그대로 Gee를 출력하면 안 된다는 것을 놓치기 쉽기 때문이다. 사이클이 존재하더라도 사이클을 이루는 노드들로부터 도착 지점까지 갈 방법이 없다면, 도착 지점에서 돈을 무한히 가질 수 없다. 따라서 사이클의 노드들로부터 도착 지점까지 갈 수 있는지 확인하는 과정을 반드시 거쳐야 한다. #incl..

알고리즘/baekjoon 2023. 1. 20. 02:53

https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 경로를 어떻게 찾아낼 것인가가 가장 중요했던 문제다. 본인은 플로이드-워셜에서 마지막으로 경유한 노드(k)를 저장하고, 시작점을 i, 도착점을 j라 하였을 때, (i, k)와 (k, j)의 마지막 경유 노드를 추적하였다. 이 방식을 찾아낸 경유 노드에 동일하게, 연속적으로 적용하여 경로를 찾아냈다. #include #include #include #include #include #include..

알고리즘/baekjoon 2023. 1. 19. 22:38

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 다익스트라를 통해 한 노드에서 다른 노드로 거리 완화를 시도하는 과정에서, 2가지 방법이 있음을 알 수 있다. 1. 포장을 하지 않는다. 2. 포장을 한다. 1번을 택할 경우 평범하게 다익스트라로 거리 완화를 하면 된다. 2번을 택할 경우, 포장을 한 번 했다는 사실을 저장한 후 거리 완화를 해야 한다. 이 포장을 한 번 했다는 사실을 저장하기 위해, 원래 1차..

알고리즘/baekjoon 2023. 1. 19. 19:44

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 빨간 구슬과 파란 구슬의 좌표를 bfs에 넣고 돌리는 문제이다. 구현하는 것 자체는 문제가 되지 않지만, 1. 파란 구슬이 빨간 구슬보다 동시에, 또는 먼저 들어갔을 때 골 처리를 했거나 2. 한 구슬의 이동 경로에 다른 구슬이 있을 경우 구슬의 최종 위치를 잘못 설정했을 때 의 예외를 제대로 처리하지 않았다면 무조건 틀린다. 1번 볼드체 표시한 ..

알고리즘/baekjoon 2023. 1. 19. 11:51

https://www.acmicpc.net/problem/25686 25686번: 1차원 $[a_1, a_2, a_3] = [1,3,2], [2,1,3], [2,3,1]$ 또한 답으로 인정됩니다. 이 예제는 서브태스크 1의 조건을 만족합니다. www.acmicpc.net 핵심적인 생각 : 홀수와 짝수를 더해 2를 나누면 자연수가 될 수 없다. N = 9일 때를 생각해보자. 1 2 3 4 5 6 7 8 9 이 배열을 홀수와 짝수 두 배열로 나눠보자. 1 3 5 7 9 / 2 4 6 8 두 배열을 각각 어떻게 정렬하든, 두 배열에서 원소를 하나씩 뽑아 더해 2로 나눈 수는 무조건 자연수가 될 수 없다. 즉 문제의 조건을 만족할 수 있다. 이는 홀수와 짝수 각각의 배열에서도 성립한다. 1 5 9 / 3 7 2..

알고리즘/baekjoon 2023. 1. 18. 11:03

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int N; ll A[4001], B[4001], C[4001], D[4001]; vector AplusB; v..

알고리즘/baekjoon 2023. 1. 17. 22:17

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net ..

알고리즘/baekjoon 2023. 1. 12. 14:44