DP

[python3] 백준 1937 풀이 (욕심쟁이 판다, DFS, DP)

어떤 문제이던 DP가 들어가면 난이가 확 올라가는것 같다. 이 문제는 처음에는 DFS로만 풀었다. 각 좌표별로 DFS를 실행했고 DFS에 시간복잡도에 N*N만큼 곱해져서 상당히 시간복잡도가 컸다. 그래서 시간초과가 났고 새로운 풀이를 찾아야 했다. 우선 고수들의 예시를 보자 위와 같이 대나무가 있다고 가정한다. 우리는 (0,0)부터 탐색을 시작한다. 그렇다면 자신보다 큰 값으로 최대한 이동할때의 DFS를 생각해본다. 그렇다면 DP배열은 아래와 같이 설정된다. 그러면 결국 DFS한번 만으로 각 좌표에서의 최대 일 수를 구할 수 있다. 그렇다면 DP가 계산되지 않은 (1,0)을 살펴본다. 그러면 이미 DP(0,0)은 최댓값을 가지고 있으므로 2의 값을 가져와서 1을 추가한다면 DFS없이 최대 일 수를 구할 ..

백준 11049 (행렬 곱셈 순서, DP)

처음에 보고 먼소린가 했는데 행렬의 곱셈이 이루어진 후의 연산 비용을 계산해보는 문제이다. 따라서 최소값을 구하면 된다. 그럼 식을 세워야 한다. 저번에 풀었던 11066문제와 비슷하다. 양옆으로 연산을 하기 때문에 잘 쪼개서 계산하면 된다. 그래서 일반항으로 나타내면 아래와 같다. 아주 다행인건 최적화 따위를 안해도 된다는 것이다. 여기서 팁은 최솟값이 적어도 2^31-1보다 작아야한다는 것이다. 따라서 이부분을 놓치지 않고 코딩으로 바꾸어 주면 아래와 같다. n = int(input()) p = [] for i in range(n): p.append(tuple(map(int, input().split()))) D = [[0 for i in range(n)] for i in range(n)] # 연산시..

백준 11066 풀이 (파일 합치기, DP, Knuth Optimization)

문제 이해가 어렵지는 않다. 양 옆으로만 더할 수 있고 이에 대한 비용을 계산하여 최종 비용이 가장 낮은 경우의 값을 구하는 것이다. 만약 재귀로 푼다면 말도 안되는 연산을 해야하기 때문에 DP로 풀어야 한다. 처음에 갈피를 못잡다가 이미지를 검색해 보니 묶어서 DP로 푸는걸 알게 되었다. 따라서 대강 점화식을 세우다 보니 다음과 같은 점화식을 세울 수 있었다. 복잡해 보이지만 이러한 방식으로 점화식을 세웠다. 그러나 문제는 이러한 점화식으로 프로그램을 제출 했을때 시간초과가 뜨는 것이었다.......ㅠㅠ 솔직히 나름 식도 잘세우고 어렵던 DP문제를 혼자 풀었던 느낌이라 기분 좋았는데 시간초과가 떠서 무엇을 더 손대야 할지 감을 못잡았다. 그래서 구글링을 해본 결과 저런 형태의 수식인 경우 최적화를 해줄..

백준 11051 풀이 (이항 계수 2, 다이나믹 프로그래밍)

11050에서 풀었던 방식대로 대강 풀어봤으나 재귀함수의 recursion 제한때문에 연산에 어려움이 있었다. 그래서 연산을 줄이기 위해 DP를 생각해보았다. 메모제이제이션을 어떻게 사용해야하나 고민을 하다가 팩토리얼 자체를 for구문으로 구해서 연산할 생각을 했다. 문제는 그렇게 하는 경우 메모리에서 뻗는걸 확인했다. 그래서 도대체 어떻게 DP를 쓰라는 건지 모르겠어서 고수의 방식을 살짝 엿보러 구글링을 해보았다. 알고보니 조합에도 규칙이 있었다. 이걸 도대체 어떻게 생각해 낸건지 나의 머리로는 아마 일주일이 걸려도 못찾았을 것 같다. 그래서 저 규칙을 토대로 DP 코딩을 하면 아주 간단하게 큰 값의 조합을 구할 수 있다. a,b = map(int, input().split()) memo = [[0 f..

백준 11054 풀이 (가장 긴 바이토닉 부분 수열, 다이나믹 프로그래밍)

이번에는 저번 시간에 풀었던 11053을 응용한 문제를 풀어보자. 처음 보면 솔직히 나야 역시나 무슨 말인지 몰라서 2~3번은 더 읽어보았다. 간단히 요약하자면 S1 Sk+1 > ... SN-1 > SN 과 같은 수열의 형태인 바이토닉 부분 수열을 찾되 가장 긴 부분 수열을 찾아보자는 것이다. 11053번에서 나는 오름차순으로 가장 긴 부분 수열을 찾을 수 있었다. 11054는 내림차순을 구해보라는 문제이다. 일단 문제를 풀기에 앞서 표를 그리며 생각해본다. number 1 5 2 1 4 3 4 5 2 1 dp (->) 1 2 2 ... ..... ... 4 5 2 1 dp2 ( dp[target]: dp[target] = dp[i] + 1 target2 = le..

백준 9184 풀이 (재귀함수, 메모제이션, 다이나믹 프로그래밍)

우선 이 문제를 보고 당혹감을 감출 수 없었다. 식을 그냥 줬다. 그냥 풀어보라고 줘버린것이다. 이런건 유저가 만들어야하는데 주는 이유가 있을것이다. 처음에는 규칙을 찾아야하나?하고 고민을 했다. 솔직히 저렇게 복잡하게 얽히고 섥혀있는데 규칙을 어떻게 찾나 고민을 했다. 그러다가 9184를 구글링 했더니 메모제이션이라는 기법이나 DP가 같이 쓰여있는 것을 확인했다. 그래서 메모제이션을 찾아보았다. 메모제이션이란 일반적인 재귀에서 이미 같은 인자를 연산했더라도 또 연산하는 경우가 존재한다. 그래서 이미 연산한 결과는 저장해두고, 만약 같은 연산이 필요할때 꺼내어 쓰자는 의도이다. ssminji.github.io/2020/02/05/the-cake-thief/ [알고리즘] Memoization(메모이제이션)..