다이나믹프로그래밍

[python3] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP )

상당히 헤맸던 문제다. 갈피를 못 잡다가 문제의 알고리즘 분류를 힌트로 보고 방향성을 잡을 수 있었다. 그럼 문제를 보자 문제를 읽어보면 건물의 순서가 주어진다. 이때 목표하는 건물을 만들기까지 걸리는 최소 시간을 출력한다. 보면 건물의 순서가 그래프로 주어지기 때문에 사이클이 존재하지 않는다. 즉, DAG그래프처럼 보인다. 그럼 당연히 자연스럽게도 위상정렬이 떠오른다. 그럼 생각을 해본다. 위상정렬은 BFS처럼 동작한다. 큐에서 노드를 뽑고, 노드의 out degree접선을 제거하면서 진행한다. 그리고 만약 한 노드의 in degree접선이 0이라면 큐에 넣는다. 위상정렬의 원리는 아래의 글을 읽으면 된다. [python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 ) 위상정렬 어떤..

백준 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..

백준 2579 풀이 (다이나믹 프로그래밍, bottom-up, 계단 오르기)

이번 문제는 매번 그렇듯이 나에게 상당히 어려웠다. 재귀로 풀면 안된다는 느낌은 단박에 왔고, 다이나믹 프로그래밍을 써야한다는 느낌이 들었다. 물론 어떻게 써야할지 몰라서 문제였다. 그래서 다이나믹프로그래밍의 강좌를 듣고 bottom-up형식으로 풀어야한다는 것을 알게 되었다. bottom-up이란 작은 문제부터 풀어나가면서 결과를 저장시켜서 for 구문을 사용하여 푸는 방식이다. 일단 계단 오르기의 규칙은 다음과 같다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 여기서 중요한 ..

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

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