https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net DFS + 다이나믹 프로그래밍 어떤 한 좌표 (i, j)에 도달할 수 있는 경우의 수는, 주변 4방향 중 (i, j)보다 높은 곳에 도달할 수 있는 경우의 수의 합과 같다. 문제에서는 내리막길을 사용해서 (N, M)에 도달해야 한다고 적혀 있는데, 이는 반대로 말한다면 (N, M)부터 (1, 1)까지는 오르막길이라는 뜻이다. 이에 따라 다음과 같은 DFS 함수를 선언했다. private stat..
분류 전체보기
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 우선순위 큐를 이용한 BFS 벽을 최소한으로 부숴야 하기 때문에 BFS를 선택했다. 단, 그냥 큐를 사용해서 풀 경우에는 움직인 거리 기준으로 큐에 들어가기 때문에, 우선순위 큐를 사용하여 벽을 부순 횟수를 기준으로 정렬되도록 했다. 처음에는 방문 체크 배열 v를 int 배열로 만들어 어떤 위치에 도달했을 때, 그 때까지 부순 벽의 개수를 저장하려 했는데, 어차피 벽을 부순 ..
https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 매개변수 탐색 알고리즘 분류에 보면 "이분 탐색"과 "매개변수 탐색"이라고 적혀있는 것을 볼 수 있다. 이 문제는 아이디어가 도저히 떠오르지 않아 분류를 참고했는데, 매개변수 탐색이 큰 힌트가 됐다. 보통 이분 탐색을 통해 도출한 값 자체를 조건으로 해서 start값과 end값을 조절한다. 하지만 매개변수 탐색에서는 이분 탐색으로 도출한 값을 다시 함수에 매개변수로 ..
https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 다이나믹 프로그래밍 DP 모든 경우의 수를 찾는 것이므로 DP를 사용하여 풀었다. 파이프가 두 칸을 차지할 수 있기 때문에, 파이프의 r 값이 가장 작은 칸, 만일 r이 같다면 c값이 가장 작은 칸을 기준으로 파이프의 개수를 세도록 했다. 어떤 칸 (i, j)에 파이프가 존재할 수 있는 경우는 세 가지이다. 1. (i, j + 1)도 빈 칸이어서 파이프를 가로로 둔다. 2..
https://www.acmicpc.net/problem/30206 30206번: 차량 배치 첫 번째 줄에 지점의 개수 $N$과 도로의 개수 $M$이 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 200\,000;$ $N-1 \le M \le \min(\frac{N(N-1)}{2}, 200\,000))$ 이후 $M$개의 줄에 걸쳐 각 도로가 잇는 서로 다른 www.acmicpc.net 경우의 수 구하기 조건과 설명만 읽고 복잡해보일 수 있지만, 사실 뜯어보면 간단하기 그지없는 문제이다. 모든 연결은 가중치 1을 갖기 때문에 BFS로 1번 도로와의 거리를 구할 수 있다. 1번 도로까지의 거리를 깊이 라고 하자. 어떤 도로에서도 충돌이 일어나면 안되기 때문에, 깊이가 같은 도로가 두 개 이상이..
LIS LIS는 Longest Increasing Subsequence의 약자로, 주어진 배열의 부분 수열 중 각 원소가 이전 원소보다 커야 한다는 조건을 만족하는 가장 긴 부분 수열이다. 예시를 들자면 다음과 같다. [10 20 10 30 20 50] 위와 같은 배열에서 LIS는 10 20 10 30 20 50 으로, 길이는 4이다. 다이나믹 프로그래밍 DP LIS를 찾는 가장 간단한 방법은 DP를 이용하는 것이다. 주어진 수열을 저장할 배열 뿐 아니라, 각 원소가 포함된 가장 긴 부분 수열을 저장할 또다른 배열이 필요하다. 여기서는 주어진 수열을 저장하는 num, 가장 긴 부분 수열의 길이를 저장할 배열을 len이라고 하겠다. for (int i = 1; i < N; i++) { for (int j ..
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 LIS 가장 긴 증가하는 부분 수열을 구하는 문제를 LIS라고 한다. Longest Increasing Subsequence의 약자로, 배열의 일부 원소를 골라서 만든 부분 수열 중 각 원소가 이전 값보다 크다는 조건을 만족하는 가장 긴 수열을 뜻한다. 이번 문제는 수열의 길이 N의 최댓값이 1,000이기 때문에 시간 ..
https://www.acmicpc.net/problem/30205 30205번: 전역 임무 김 병장이 소속된 특수부대는 전역을 하려면 특이하게 대대장으로부터 주어진 임무를 달성해야 한다. 김 병장이 받은 임무는 적군의 $1$번 기지부터 $N$번 기지까지 모두 순서대로 격파하는 것이 www.acmicpc.net 우선순위 큐 PriorityQueue 김 병장이 전역을 하기 위해서는 항상 전투력 P를 최대로 유지할 필요가 있다. 다행히 적군과 싸워도 P가 깎이지는 않으므로, 최대한 큰 값을 만들도록 +연산과 *연산을 조절해야 한다. 어떻게 해야 P가 최댓값을 계속 가질 수 있을까? 마이너스 연산이 없기 때문에, 할 수 있는 한 최대로 + 연산을 하고, 그 결괏값에 *2 연산을 해주면 최댓값을 얻을 수 있다...
