다이나믹프로그래밍 검색 결과

해당 글 4건
부분 문제 그리고 메모이제이션 : 다이나믹 프로그래밍 할 때 많이 나오는 데 무엇일까요?

간혹 가다가, 이런 이야기를 들으실 수 있을 거에요. 사실, 이 용어는 다이나믹 프로그래밍 뿐만이 아니라, 다른 기법에서도 종종 나오니, 고수 분들의 설명을 들으시려면, 정확한 정의는 모르셔도 됩니다. 그냥 아. 이런 거구나. 이해만 하셔도 무난합니다. 솔직하게 말해서, 시험에 나올 일도 거의 없을 겁니다. 간단한 예제를 들기 위해서, 16690번 paper Cuts 문제를 보도록 합시다. 문제를 요약하면 아래와 같습니다. str이 "abbaaddccee"이고 pat이 aaabbeeddcc입니다. 저는 str에서 칸막이 몇 개를 사용해서 잘게 쪼개려고 합니다. 위 그림에서는 "abb", "aa", "ddcc", "ee" 이렇게 쪼개졌습니다. 칸막이 u개를 써서 잘 쪼갠 문자열들을, 어떻게 잘 배치해서 p..
자료알고/알고리즘 2020. 2. 7. 22:02
leetcode 338 counting bits : 마지막 켜진 비트만 알면 된다.

leetcode 338번, Counting bits를 풀어보도록 합시다. 1부터 n까지 켜진 비트의 수를 구하려고 합니다. 그런데 이것을 O(n)에 구하려고 합니다. 어떻게 하면 좋을까요? n이 100만까지 있을 때, 20개의 비트를 일일히 보는 것은 꽤 큰 낭비입니다. 이를 어떻게 하면 좋을까요? 이전에 계산했던 정보를 다시 재사용하는 방법은 없을까요? 먼저 dp[x]를 위와 같이 정의합니다. 그러면, dp[0]은 0일 겁니다. 0을 2진수로 표현하면 00..00입니다. 비트 값이 1인 것이 없습니다. 따라서, dp[0]의 값은 0으로 초기화를 합니다. 그러면, dp[x]의 값은 어떻게 구하면 좋을까요? 6을 생각해 봅시다. 이것은 2진수로 0110로 나타낼 수 있습니다. 켜져 있는 비트 1의 수가 몇..
자료알고/알고리즘 2019. 11. 22. 04:02
냅색 알고리즘 문제 : 가방에 어떻게 넣어야 이득이 최대일까?

12번째 글은, 냅색 알고리즘 문제입니다. 이것도 꽤 여러 종류가 있는데요. 쪼갤 수 있는 물건이냐, 그렇지 못하냐에 따라서, 그리디로 접근을 할 수 있는지, 아니면 dp로 접근해야 하는지가 나뉩니다. 저는 0/1 냅색 문제를 다뤄 보겠습니다. 이것은 물건을 쪼갤 수 없어요. 물건이 n개가 있습니다. 그리고 가방에 넣을 수 있는 무게는 W입니다. 이 때, 가방에 넣을 수 있는 물건들의 최대 이익은 얼마나 될까요? 먼저 기저 조건을 생각해 봅시다. 물건 0개를 넣었을 때, 가방에 넣은 물건의 총 무게는 0, 이익 또한 0일 겁니다. 따라서, dp[0개][용량 0]을 넣었을 때 값은 0입니다. 대충 이런 경우입니다. 만약에 물건 0개를 넣었는데, 가방에 넣은 물건의 총 무게가 x(x>0)라면 이건 어떨까요?..
자료알고/알고리즘 2019. 7. 3. 00:25
외판원 문제 : 팩토리얼을 지수 복잡도로 낮춰보자

우리가 흔히 말하는 TSP, 외판원 문제는, 어떠한 도시에서 출발해서, 모든 도시를 방문하고 다시 출발점으로 돌아왔을 때, 최단 경로의 길이를 구하는 문제입니다. 이것을 단순하게, 모든 경우를 따져가면서 푼다면 n! 의 가짓수를 모두 따져야 할 겁니다. n이 12만 되어도 4억이 넘어갑니다. 이렇게 비효율적인, 팩토리얼급을 어떻게 지수급으로 낮추느냐가 핵심인데요. 중복된 상태를 memoi 하는 방법으로, O(n^2*2^n)으로 줄일 수 있습니다. dp를 다음과 같이 정의합시다. 시작점과 끝점은 0이라고 가정합시다. dp[state][s] : 현재 s에 있고, state 상태일 때 최단 거리. 그러면, 이 state가 무엇인지 궁금하실 텐데요. s에서 출발하였을 때, 방문한 도시들의 집합을 나타낸 겁니다...
자료알고/알고리즘 2019. 6. 27. 04:21