[프로그래머스] 도둑질 / 동적 계획법(Dynamic-Programming)

💭 문제 이해 두 수를 인접하지 않게 선택하여 최대 합을 구하는 문제이다. 마을이 원형구조이므로 1, 2, 3, 4번 집이 있을 때, 1번은 2번, 4번과 인접해있다. 따라서 1번을 선택할 때의 경우(2, 4번은 선택불가)와 1번을 선택하지 않을 경우(1번만 사용불가)를 나누어서 두 결과값 중 최대를 반환하면 된다. 구현 언어: Python def solution(money): # 3 1 4 7 2 5 case1 = [i for i in money] case2 = [i for i in money] # 첫 번째를 선택하는 경우 case1[1], case1[-1] = case1[0], 0 # 첫 번째를 선택하지 않는 경우 case2[0] = 0 for i in range(2, len(money)): case..

→2021.03.11

[프로그래머스] 등굣길 / 동적 계획법(Dynamic-Programming)

💭 문제 이해 격자를 오른쪽과 아래쪽으로 이동하며 최단 경로의 수를 측정하는 문제이다. DP로 풀 수 있고, 물이 있는 부분을 어떻게 체크하느냐가 포인트인 문제이다. 구현 언어: Python def solution(m, n, puddles): maps = [[0]*(m+1) for _ in range(n+1)] dp = [[0]*(m+1) for _ in range(n+1)] # 물 체크 for pud in puddles: maps[pud[1]][pud[0]] = -1 dp[1][0] = 1 # 시작지점은 1 for i in range(1, n+1): for j in range(1, m+1): if maps[i][j] == -1: dp[i][j] = 0 else: dp[i][j] = (dp[i-1][j]..

→2021.03.11

[BOJ] 백준 1535 안녕 / 동적 계획법(Dynamic-Programming)

💭 문제 이해 세준이 체력이 최대 100이므로 숫자를 증가시키면서 해당 체력내에 얻을 수 있는 최대 기쁨을 갱신한다. 구현 언어: Python import sys r = sys.stdin.readline n = int(r()) hp_loss = list(map(int, r().split())) pleasure = list(map(int, r().split())) dp = [[0]*101 for _ in range(n+1)] for i in range(1, n+1): for j in range(100): if j < hp_loss[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-hp_loss[i-1]] + pleasure[i-1..

→2021.03.11

[BOJ] 백준 11055 가장 큰 증가 부분 수열 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 앞의 문제 11053번 가장 긴 증가하는 부분 수열 과 거의 유사하다. 동적 계획법 풀이 작성 언어: C++ #include int biggestIncreasingSeq (int arr[][1010], int size) { int sumMax = 0, l_result = 0; for (int i = 0; i < size; ++i) { for (int j = 0; j < i; ++j) { if (arr[..

→2020.04.27

[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 / 동적 계획법(Dynamic-Programming)

💣 문제 이해 수열 A = {10, 20, 10, 30, 20, 50}인 경우 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 동적 계획법(Dynamic Programming) 방식을 사용했다. 💭 풀이 과정 생각보다 풀이과정은 간단했다. 계속해서 DP 문제를 풀이하며 풀이 접근 방식 감을 잘 잡는 게 중요한 것 같다. 동적 계획법 풀이 작성 언어: C++ #include using namespace std; int longestSeqLength(int (*dpArr)[1010], int arrSize) { int max = 0, longest = 0; for (int i = 0; i < arrSize; ++i) { for (int j = 0; j..

→2020.04.24

[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