[BOJ] 백준 9251 LCS / 동적 계획법(Dynamic-Programming)

💣 문제 이해 많이 알려진 Longest Common Sequence(LCS) 문제이다. 두 문자열이 입력으로 주어질 때, 이 두 문자열의 공통되는 부분 중 가장 긴 문자열의 길이를 출력하는 문제이다. 이 외국 유튜버의 풀이 를 참고하며 3가지 풀이로 접근해보았다. 1. 재귀 (Recursion) 2. 메모이제이션 (Memoization) 3. 동적 계획법 (Dynamic Programming) 💭 풀이 과정 1. 재귀 방식의 풀이 작성 언어: C++ #include // c 표준 입출력 #include // std::max char str1[1001], str2[1001]; int LCS_recurs(int index1, int index2){ if (str1[index1] == '\0' || str2..

→2020.03.14

[BOJ] 백준 12865 평범한 배낭 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 0-1 Knapsack Problem 과 동일한 문제이다. N 개의 물건이 입력으로 주어진다. 각 무게 W , 가치 V 를 가진다. 최대 K 무게를 가방에 넣을 수 있다고 할 때, 포함한 물건의 가치 V 합의 최대를 구해야한다. 3학년 학기 중에 풀어보았지만 가물가물해서 이 외국 유튜버의 풀이 가 상당히 유익했기에 다시 한 번 참고했다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 dp[i][j] = max(dp[i-1][j] , dp[i][j-index] + value) 의 점화식을 가진다. 1. 가방 공간보다 이 물건의 무게(product[i][1]) 이 더 클 때는 포함하지 못하므로 이를 제외한 무게로 대체한다. 2. 가방 공간보다 이 물건의 무게..

→2020.03.12

[BOJ] 백준 11051 이항 계수 2 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 10,007로 나눈 나머지를 구하는 문제이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 nCr = n-1Cr + n-1Cr-1 식 이 성립하게 된다. 사탕 4개 중에 2개를 선택할 때 (4C2) , 어떤 한 사탕을 제외한 3개 중에 2개를 뽑는 경우 (3C2) 와 그 한 사탕을 무조건 뽑고 남은 3개 중에 1개를 더 뽑는 경우 (3C1) 를 합한 것과 같기 때문이다. 이를 그림으로 나타낸 것이 파스칼의 삼각형이다. 점화식은 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] 이다. 작성 언어: C++ #include int dp[1001][1001] = {1, }; const ..

→2020.03.11

[BOJ] 백준 11057 오르막 수 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 2234와 3678, 11119 와 같이 인접한 수가 같거나 오름차순을 이루는 수를 오르막 수 라고 정의한다. 2. 수는 0 으로 시작할 수 있다. 3. 입력으로 주어지는 N 자리 수에서 오르막 수의 갯수를 출력한다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 로 총 10 가지이다. N = 2 인 경우 00~09, 11~19, 22~29, .... , 88~89, 99 로 총 55 가지이다. 여기서 규칙을 찾아보면 2자리 수 (ab) 에서 일의 자리 수 (b) 는 십의 자리 수 (a) 와 같거나 크다는 것을 발견할 수 있다. 즉,, 0b 의 경우 b 는 0보다 크거나 같은 경..

→2020.03.09

왜 정답을 나눈 나머지를 출력하라고 할까? - 나머지 연산

요즘 dp 문제를 풀면서 정답을 특정 값으로 나눈 나머지를 출력하라는 조건을 많이 발견했다. 다른 사람들의 풀이를 보고 블로그들을 찾아보면서 다음과 같은 성질을 활용한다는 것을 알 수 있었다. (A + B) % M = (A % M + B % M) % M 최종적으로 구한 dp 배열에 특정 값들을 합한 결과를 출력하고는 한다. 그런데 dp 배열을 구하는 과정에서 매번 그 값들의 나머지를 구해줘도 동일한 결과값이 나온다는 말이다. 실제로 그러한지 간단한 소스코드로 구현해보았다. #include #include // INT_MAX 상수 using namespace std; int mod = 1e+7;// 10^7 int main(){ long a = INT_MAX, b = INT_MAX; cout

→2020.03.06

[BOJ] 백준 10844 쉬운 계단 수 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 45656 과 같이 모든 자리 수가 인접한 자리 수와 1 차이날 때, 그 수를 계단 수 라고 한다. 2. 입력으로 1~100 사이의 자연수 N 이 주어진다. 3. N 자리 자연수 중 계단 수가 총 몇 개인지 찾아 출력하면 된다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 가능하다. 문제에 제시된 조건에 따라 0은 불가하다. N = 2 인 경우, 10, 12, 21, 23, 32, 34, .... 98 가 가능하다. 1 ~ 9 사이 수를 십의 자리로 하여 일의 자리는 -1 한 수 또는 +1 한 수라는 것을 알 수 있다. 점화식으로 정리하자면 다음과 같다. dp[i][j] = d..

→2020.03.06

[BOJ] 백준 1699 제곱수의 합 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 어떤 자연수 N 은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 2. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구해야 한다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 DP 방식을 활용하기로 하면서 제곱수가 1 로만 구성되어있을 때, 1, 2 로 구성되어 있을 때, 1, 2, 3 으로 구성되어 있을 때 .... 등등 순차적으로 하나 씩 포함하며 모든 경우를 따져보기로 했다. N 이 15 인 경우를 예로 들어보자면 다음과 같다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 각 인덱스가 입력으로 받는 자연수 N 이다. N = 5 의..

→2020.03.04

[BOJ] 백준 11726 2xn 타일링 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 앞에 풀었던 2193번 이친수, 1904번 01타일 과 상당히 비슷한 문제이다. 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 출력하면 된다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 | 를 2x1 사각형, == 를 1x2 사각형으로 가정하겠다. N = 1 인 경우 1가지 | N = 2 인 경우 2가지 | | , == N = 3 인 경우 3가지 | | | , == | , | == N = 4 인 경우 5가지 | | | | , == | | , | | == , | == | , == == 이런 방식으로 변화한다. 여기서 두 가지의 규칙을 찾을 수 있었다. 1) N-2 번째 경우의 수와 N-1 번째 경우의 수를 합한 것이 N 번째 경우의..

→2020.03.04

[BOJ] 백준 1904 01타일 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 앞에 풀었던 2193번 이친수 와 상당히 비슷한 문제이다. 1. 0 과 1 로 이진수를 만들고자 한다. 2. 0 은 무조건 00 형태로만 쓰이고 1 은 원하는 대로 쓸 수 있다. 3. 입력으로 주어진 N 자리 수의 이진수를 총 몇 가지 만들 수 있는지 구하면 된다. 4. !! 찾은 수열의 개수를 15746 으로 나눈 나머지를 출력해야 한다 !! 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우 1 로 총 1가지 N = 2 인 경우 11, 00 으로 총 2가지 N = 3 인 경우 111, 100, 001 으로 총 3가지 N = 4 인 경우 1111, 1001, 1100, 0011, 0000 으로 총 5가지 N = 5 인 경우 11111, 1..

→2020.03.04

[BOJ] 백준 2193 이친수 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 1. 첫 번째 자리가 1로 시작하는 수이다. 2. 1과 1이 인접할 수 없다고 했으니, 두 번째 자리는 0 이다. 3. N 자릿수 중에서 이러한 규칙을 만족하는 수의 개수를 구해야 한다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 N = 1 인 경우는 1 하나밖에 없다. => 1 N = 2 인 경우는 10 하나밖에 없다. => 1 N = 3 인 경우는 100, 101 두 가지이다. => 2 N = 4 인 경우는 1000, 1001, 1010 세 가지이다. => 3 N = 5 인 경우는 10000, 10001, 10010, 10100, 10101 다섯 가지이다. => 5 이 규칙을 토대로 발견할 수 있는 것은 1) 바로 앞 케이스에 따라 다음 케이스가 ..

→2020.03.04