[백준] 20167, 20181 꿈틀 꿈틀 호석 애벌레
참고: https://www.acmicpc.net/problem/20167, https://www.acmicpc.net/problem/20181 꿈틀꿈틀 호석 애벌레 - 기능성 문제에 주어진 조건이 크지 않으므로 브루트 포스로 해결할 수 있다. 애벌레가 먹이를 먹는 경우와 그렇지 않은 경우로 나눌 수 있고, 만족도가 K 이상일 때 만족도를 0 으로 하고 탈피 에너지를 증가하면 해결할 수 있다. 꿈틀꿈틀 호석 애벌레 - 효율성 동일한 문제로 제한 조건만 달라졌다. 먹이의 개수가 100,000개이며 만족도가 10^8 까지 가능하다. 따라서 브루트 포스로 해결할 수 없다. 일단 특정 구간에서의 누적된 만족도를 구해야하므로 투 포인터(left, right)를 사용하여 누적합을 구할 수 있을 것 같다. 그리고 해..
[백준] 20166 문자열 지옥에 빠진 호석
문자열 지옥에 빠진 호석 주어진 이차원 배열을 8 방향으로 이동하며 가능한 모든 문자의 수를 구하고, 신이 좋아하는 단어가 나타나는 개수를 구하는 문제입니다. 문제의 조건은 아래와 같습니다. 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자. 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다. 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다. 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 ..
참고: https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP로 해결해야 하는 문제이기 때문에 점화식을 세우는 것이 중요합니다. 점화식은 아래와 같습니다 DP[i][j]: files[i]에서 files[j]까지 합치는 총 비용 1 2 3 4 의 파일들이 존재할 때 files[0]에서 files[3]까지 파일을 합치는 방법은 여러가지가 있습니다. (1 + 2) + (3 + 4) 1 + ((2 + 3) + 4) (1 + (2 + 3)) + ..
참고: https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net DP로 해결할 수 있는 문제입니다. 따라서 점화식을 세워야 합니다. 최종 점화식은 아래와 같습니다. DP[N] = DP[N-2] * 3 + DP[N-4] * 2 + ... + DP[0] * 2 ( N >= 4인 짝수) 점화식을 이해하기 위해서 N을 1에서 부터 대입하여 직접 그림을 그려 보아야 할 것입니다. 1. N = 1 3 * 1 크기의 타일을 채워야 하지만, 주어진 1 * 2 와 2 * 1 타일로 채울 수 없습니다. 2. N = 2 3. N = 3 3 * 3 크기의 타일을 채울 수 있는 경우의 ..
참고: https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 옮겨지는 아이의 최소한의 수를 구하는 문제입니다. 옮길 아이의 최소라는 것은, 옮기지 않을 아이의 최대라고도 할 수 있습니다. 현재 문제는 아이들의 순서 번호를 오름차순으로 정렬해야하기 때문에, 옮기지 않을 아이의 최대 수는 증가하는 부분 수열을 구하는 문제와 동일합니다. 즉, 증가하는 부분 수열의 최대 길이를 구할 수 있다면 최소한으로 옮길 아이들의 수를 구할 수 있을 것입니다. 이렇게 정렬되어..
참고: https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 주어진 수들의 연산(+, -) 결과가 배열의 마지막 수가 되는 경우의 수를 구하는 문제입니다. 일단 문제에서 주어진 단서들을 나열합니다. 수의 범위는 0이상 20이하이고, 배열의 크기는 3이상 100 이하 입니다. 그리고 올바른 등식의 개수의 범위가 2^63 - 1까지 입니다. 여기서 얻을 수 있는 힌트는 배열의 크기가 그리 크지 않으므로 이중 for문 정도는 사용할 수 있고, 정답..
참고: https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net n * m 크기의 배열에서 1로된 가장 큰 정사각형의 크기를 구하는 문제입니다. DP를 사용하여 해결할 수 있습니다. 이미 DP로 분류되어있는 것을 알았기 때문에, 저는 바로 DP로 접근했습니다. 하지만 문제 유형에 대한 단서가 주어지지 않았다면 해결 방법을 찾는데 시간을 좀 더 많이 소비 했을 것 같습니다. 다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해 뒀다가 나중에 큰 문제의 결과와 합하여 푸는 알고리즘입니다. 이러한..
참고: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열 (LCS: Longest Common Subsequence) 문제입니다. 문제를 처음 보면 모든 가능한 수열을 구해서 비교하는 브루트포스 알고리즘이 떠오를 수 있습니다. 하지만 순열(Permutation) 알고리즘은 O(N!) 시간 복잡도를 가지기 때문에 적절한 해법이 아닌 것 같습니다. 그렇다면 다이나믹 프로그래밍으로 풀 ..
참고: https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 다이나믹 프로그래밍을 공부했다면 한 번쯤 풀어 봤을 배낭 문제입니다. 사실 배낭 문제는 두 가지 유형으로 나눌 수 있습니다. 하나는 배낭에 들어갈 물건을 나눌 수 있는 '분할 가능 배낭 문제' 이고, 다른 하나는 물건을 나눌 수 없는 '0-1 배낭 문제' 입니다. 위 문제는 0-1 배낭 문제에 해당하며, 분할 가능 배낭 문제..
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 각 수업의 시간이 겹칠 경우 강의실이 추가된다. 단, 한 수업의 끝 시간과 시작 시간이 동일하면 겹치지 않는 것으로 한다. 먼저 수업들을 시작 시간을 기준으로 정렬한다. 그리고 이미 시작한 수업을 끝나는 시간을 기준으로 우선순위 큐에 삽입한다. 이미 시작한 수업의 끝 시간과 다음에 시작할 수업의 시작 시간을 비교하며 수업이 겹치지 않는 경우, 우선순위 큐에서 수업을 제거한다. 최종적으로 우선순위 큐에는 수업 시간이 겹치는 수업들만 남아있게된다...