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

가치합의 최댓값을 구하는 문제이다. 흔히 배낭 문제라고 하는데, 밑은 이 배낭 문제의 알고리즘을 잘 설명해놓은 글이므로 참고해서 어떻게 구현할 지 생각해보면 좋을 것 같다. (출처:huiyu's blog) https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C [DP] 0/1 Knapsack(배낭) 문제 배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말 huiyu.tistory.com 예제 입력 1을 보면 4개의 물건과 최대 무게와 각 물건의 가치를 입력..

연속된 수의 합의 최댓값을 구하는 문제이다. 입력값의 개수가 100,000까지 가능하기 때문에, 모든 경우를 비교하면 시간 초과가 뜰 것이다. 그러므로 불필요한 경우를 dp를 이용해서 제거해야 한다. 예제 입력 1을 보면 10개의 수를 입력받는데, 이 중에서 앞의 4개만 예시로 들자.(10, -4, 3, 1) 비교해야 하는 모든 경우의 수를 보면, 1. 10 2. 10 -4 3. 10 -4 3 4. 10 -4 3 1 5. -4 6. -4 3 7. -4 3 1 8. 3 9. 3 1 10. 1 총 10개의 경우를 비교해야 하는데, 2번부터 4번까지는 5번부터 7번까지의 경우에 10, 즉 A[0]을 더한 값이고 1번은 A[0]이다. 또한 6번과 7번은 8번과 9번에 -4, 즉 A[1]을 더한 값이다. 그러므로..

각 문자열의 길이 + 1만큼의 2차원 배열을 선언해주고, 문자를 하나하나씩 비교하면서 최장 공통 부분수열의 길이를 구해야한다. 예제 입력을 예로 들면, 첫 번째 문자열의 앞 세글자 ACA와 두 번째 문자열의 앞 5글자 CAPCA를 비교해보면, 각 글자가 붙여지기 이전인 AC와 CAPC에 두 문자열에 모두 A가 붙여졌기 때문에, AC와 CAPC의 LCS에 1을 더한 값이 ACA와 CAPCA의 LCS일 것이다. 즉 하나하나 비교하면서, 같은 문자가 다음에 붙여진다면, 각 문자열의 이전 LCS값에 1을 더한 값이 LCS가 될 것이다. 반면에 ACAYKP와 CAPC를 예로 들면, 마지막 문자인 P와 C가 다르기 때문에, ACAYK와 CAP의 LCS에 1을 더하는 이전의 경우는 성립하지 않는다. 그러므로 각 문자..

교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제이다. 어떻게 하면 전깃줄이 교차되는 지를 생각해보자. 예시에서 A가 1일 때 B가 8이고 2일 때 9인 경우에는 교차하지 않는다. 왜냐하면 A와 B 모두 각각 오름차순이기 때문이다(1~2, 8~9). 반면에 A가 1일 때와 A가 2일 때를 보면 A는 오름차순이지만, B는 각각 8,2로 내림차순이기 때문에 교차한다. 어차피 A든 B든 한쪽의 순서는 상관이 없기 때문에, A를 오름차순으로 정렬을 해준 뒤에 문제를 풀어도 된다. 정렬한 뒤 B를 보았을 때 가장 길게 오름차순으로 구성되어있는 수열(가장 긴 증가하는 부분 수열)을 구하면 이 수열이 전깃줄에서 가장 교차하지 않게 구성되어있는 경우가 된다. 즉, 이 수열의 길이만큼을 빼주면 없애..

이전 문제에서 O(n^2)코드를 사용해도 시간 초과가 뜨지 않는 것을 알았기 때문에, 이번 문제에서는 코드가 좀 더 깔끔하게 짜기 위해서 O(n^2)코드를 사용했다. 바이토닉 부분 수열은 한 수열 안에서 증가하는 부분과 감소하는 부분이 존재하는 수열이다. 증가하거나 감소하는 부분이 둘 중 하나 없어도 바이토닉 수열이라고 할 수 있다. 바이토닉 부분 수열 자체가 증가하는 부분과 감소하는 부분이 결합된 형태이다보니 그냥 한번 각 경우에 따른 dp를 구해보고 꺾이는 부분(변곡점이랄까)은 무엇이 다른가를 봤는데 두 dp의 합이 가장 큰 것을 알 수 있었다. 즉, 증가하는 부분의 길이와 감소하는 부분의 길이의 합이 가장 큰 것이 가장 긴 바이토닉 부분 수열이었던 것이다. 그러므로 두 부분의 dp를 각각 구해준 뒤..

가장 긴 증가하는 수열을 찾는 문제이다. A[0] 부터 A[N-1]까지 돌면서 증가하는 각각의 수열들을 모두 구하고 비교하면 시간 복잡도가 O(n^2)이기 때문에 백준에서는 오답일 것이다. 각 원소마다 비교하는 것은 맞지만 비교할 때 모든 원소를 비교하는 것이 아니라, 이전에 증가했던 수들에 대해서만 비교를 해주면 문제가 풀릴 것이다. A = 10 3 4 5 1 2 3 4 이라고 할 때, index의 편의성을 위해서 A[0]에 0을 넣어줬다. 즉, A = 0 10 3 4 5 1 2 3 4이다. 기본 컨셉은 각 원소들을 돌면서 이전의 수보다 크면 cnt를 증가시켜서 몇번째에 위치하는 수인지를 구하는 것이다. 예를 들면 10보다 작은 수는 0 하나이기 때문에, 10의 max_cnt는 1이고, 3의 max_c..

최대로 마실 수 있는 포도주의 양을 구하는 문제이다. 이 문제는 백준 2579번(계단 오르기)과 매우 유사하다. https://aodtns.tistory.com/22 백준 2579번 - 계단 오르기 계단을 오르면서 밟는 발판의 최댓값을 구하는 문제다. 이전에 풀었던 삼각형 문제나 집 색깔 문제처럼 뒤에서 차례대로 더하면서 갱신해주는 방식을 생각했지만, 경우가 깔끔하게 나뉘는 것도 aodtns.tistory.com 계단 문제에서 연속으로 세 칸을 밟을 수는 없는 것처럼 이 문제에서는 연속으로 3잔을 모두 마실 수는 없다. 계단 문제에서는 마지막 계단을 꼭 밟아야 했기 때문에, 마지막 계단을 밟기 전의 경우들의 최댓값을 구해서 비교해주었다. 반면에 이 문제는 그런 조건이 없기 때문에 경우를 새롭게 나눠줘야 ..

첫 번째 자릿수가 1인 경우부터 9인 경우까지 계산을 해서 더하기엔 시간 초과가 뜰 것이 분명하다. 이전에 풀었던 RGB거리 문제를 생각해보면 i번째를 R로 칠한 값은 i-1번째를 G 혹은 B로 칠한 값 중에 작은 값에 R의 값을 더해주는 방식으로 최솟값을 갱신해주며 진행했다. 이 문제도 똑같은 방식으로 적용해보면, N번째 자릿수의 값이 각각 0~9일 때는 그 전인 N-1번째 자릿수까지의 경우들의 합일 것이다. ##변수 선언 부분## div_num = 10**9 data = [] sum = 0 ##메인 함수 부분## if __name__ == "__main__": N = int(input()) data = [[0]*10 for x in range(N+1)] for i in range(1,10): #자리수..