백준 문제풀이(파이썬)/동적 계획법 1

숫자마다 최소 시행 횟수를 계산하다보면, i의 최솟값은 i가 3으로 나누어 떨어진다면, i//3의 최소 시행 횟수와 연관이 있고 2로 나누어 떨어진다면 i//2와, 둘다 나누어 떨어지지 않는다면, i-1과 연관이 있다는 사실을 알 수 있다. 그럼 우리가 비교해야 할 값들은 numbers[i-1]과 numbers[i//2]+1과 numbers[i//3]+1이다. 조심해야 할 점은 if ~ elif ~else로 쓰지말고 if~if로 써서 2와 3으로 모두 나누어 떨어지는 경우도 생각해줘야한다. ##변수 선언 부분## numbers = [] ##메인 함수 부분## if __name__ == "__main__": N = int(input()) numbers = [-1,0] #N=0, N=1일때 최솟값 for i..

계단을 오르면서 밟는 발판의 최댓값을 구하는 문제다. 이전에 풀었던 삼각형 문제나 집 색깔 문제처럼 뒤에서 차례대로 더하면서 갱신해주는 방식을 생각했지만, 경우가 깔끔하게 나뉘는 것도 아니었고 규칙이 있는 것도 아니었다. 꼭 나눠줘야 하는 경우는 i번째 발판(s[i-1])을 밟기 전에 바로 전 발판(s[i-2])을 밟았는지 전전 발판(s[i-3])을 밟았는지 경우를 나누어 주고, 바로 전 발판(s[i-2])을 밟았다면 그 바로 전 발판(s[i-3])은 밟지 못하기 때문에, 전전 발판(s[i-4])까지 밟기까지의 경우의 최댓값(dp[i-3])에 s[i-1] 값과 s[i]값을 더해준 경우와 전전 발판(s[i-3])을 밟은 경우의 최대값을 비교해서 큰 값을 dp에 append 해주면 i번째 발판까지의 최대값이..

최대의 합을 찾아가는 문제다. 백트래킹으로 구현할 수 있지만, 이 문제 또한 DP문제이기 때문에 시간 초과를 생각하고 문제를 풀어야 한다. 위에서 아래로 내려가면서 합을 더해주면서 진행하면 밑의 값이 무엇이 올 지 모르기 때문에, 모든 경우를 다 생각해야 한다. 반면에, 아래에서 위로 올라가면서 합을 갱신하면 모든 경우를 돌지 않아도 된다. 이런 방식은 이전에 풀었던 RGB거리 문제(https://aodtns.tistory.com/20)와 유사하다. 백준 1149번 - RGB거리 RGB를 같은 색이 반복되지 않게 나열하는 문제다. i번째 집의 색을 각각 빨강(0), 초록(1), 파랑(2)으로 칠하는 비용을 갱신해주면서 반복해주면 된다. i번째 집의 색을 빨강으로 칠한다면, i-1번째 aodtns.tist..

RGB를 같은 색이 반복되지 않게 나열하는 문제다. i번째 집의 색을 각각 빨강(0), 초록(1), 파랑(2)으로 칠하는 비용을 갱신해주면서 반복해주면 된다. i번째 집의 색을 빨강으로 칠한다면, i-1번째 집의 색을 초록, 파랑으로 칠하는 비용 중에서 더 작은 값을 칠해주면 되기 때문에 파이썬의 기본 함수 min을 사용하여 구해준 뒤, i번째 집을 빨강으로 칠하는 비용을 더해줘서 갱신을 해준다. 그 뒤 i+1번째도 같은 원리로 갱신이 되고 결국 N번째에는 각 최소 비용이 들어갈 것이기 때문에 그 3개 중에 최솟값을 찾아주면 된다. ##변수 선언 부분## cost = [] ##메인 함수 부분## if __name__ == "__main__": N = int(input()) cost = [[int(x) f..

노트에 그려가면서 풀면 왜 문제에서 첫 10개의 숫자를 줬는지 대충 감이 온다. 삼각형을 그려보면 N번째 삼각형의 한 변의 길이는 바로 이전 삼각형의 변의 길이에 5번째 전(한 바퀴 돌고 난 뒤) 삼각형의 변의 길이를 더한 값과 같다는 것을 알 수 있다. 그러므로 점화식은 P(N) = P(N-5) + P(N-1)이다. 이를 이용해서 재귀 함수를 사용하지 않고 반복문을 사용해서 배열을 append 해주면 된다. ##변수 선언 부분## p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9] ##메인 함수 부분## if __name__ == "__main__": T = int(input()) for i in range(T): N = int(input()) for j in range(11,N+1):..

주어진 재귀 함수를 동적 계획법으로 푸는 문제다. 처음에 봤을 때는 이전에 풀었던 피보나치 문제처럼 규칙이 있으면, append 해주면서 풀면 되겠구나 싶었지만, 딱히 규칙같은건 없었다. 재귀 함수를 보면, a,b,c의 입력이 -50~50이고, 21~50은 20,20,20으로 대체되고, -50~0은 1이 리턴되기 때문에 생각해야할 것은 1~20일 때다. 구한 값을 a= 1, b=1, c=1부터 a=20, b=20, c=20까지 총 20*20*20의 8000개의 배열이 필요할 것이다. 넉넉하게 10000개의 배열을 0으로 초기화하여 선언한다. 그 뒤 index를 계산해보면, 인덱스는 (a - 1) * 400 + (b - 1) * 20 + (c - 1)이 나온다. 만약 w[index]에 값이 없으면 캐싱해주..

피보나치 함수를 구현하는 문제이다. 하지만 일반적인 재귀함수를 이용하는 방법으로 풀면 시간 초과가 뜰 것이다. 이를 해결하기 위해서 동적 계획법에 대해 알아보자. 동적 계획법 (Dynamic Programming)이란, 하나의 복잡한 문제를 동일한 구조의 간단한 문제들의 합으로 푸는 방법이다. 하나의 문제를, 그것과 동일한 형태의 작은 문제들로 나눈 뒤, 작은 문제들을 풀어내어 최종적인 문제에 접근하는 것이 목적이다. 메모이제이션 (memoization)이란, 문제를 푸는 도중에, 여러개의 작은 문제들이 도출되는데, 이 문제들이 겹쳐지면 중복계산이 발생하여 시간이 오래 걸린다. 따라서, 한번 푼 문제는 중복하여 풀지 않도록 Cache를 저장해주는 작업을 해준다. 이를 메모이제이션이라고 한다. 동적 계획법..