12개의 댓글이 있습니다.
-
-
VOCList -
DP를 푸시다 보면 상태 테이블 중 여 타 상태를 참조하지 않고서 테이블을 채워나갈 수 있는 부분이 있습니다. 그런 부분을 가장 먼저 채우신 뒤에, 현재까지 채워진 테이블만을 참조해서 새로이 만들 수 있는 부분을 하나씩 늘려나가시면 될거같네요.
위 문제에서 테이블은 index 변수가 자기보다 큰 것만 참조한다는 방향성을 가집니다. 그렇다면 다른 테이블을 참조하지 않고 채워 나갈 수 있는 부분은 어디일까요? 자기보다 index가 큰 테이블이 없는 가장 마지막 index일 것입니다. 가장 마지막 index에서의 DP 테이블 값은
i) 내가 가진 돈이 마지막 index를 선택할 시 지불 가능하면 = 마지막 index의 점수
ii) 내가 가진 돈이 마지막 index를 선택할 시 지불 불가능하면 = 0
입니다.자 이제 우리는 가장 마지막 index(이하 n이라고 가정) 을 채웠습니다. V(n, 0~remainMax)에 대한 모든 값을 알고 있다는 뜻인데요. 그렇다면 이제 우리는 V(n-1, 0~remainMax)에 대한 값도 계산해볼 수 있습니다. 왜냐면 V(n-1, 0~remainMax)에서 값 계산을 위해 참조해야 하는 테이블이 모두 채워져 있거든요.
이와 같이 마지막 인덱스에서부터 한 단계씩 인덱스를 줄여가며 모든 remain에 대해서 테이블을 채워 간다면 모든 테이블을 3중포문 정도로 채울 수 있습니다.
13년 전 link
-
-
-
룡이 -
VOCList 님 답변 감사합니다. 가닥이 잡히는 것 같네요 ! 도전해볼게요 ^^
리베님 이건 알고리즘 문제풀이로 있는 문제가 아니라 제가 연구실에서 하는 연구를 DP 로 변형시킨 거라서요. 링크해드릴 문제 페이지는 없습니다. 개념적으로 좀 포장해본다면,엘리베이터가 건물 꼭대기에서부터 내려가는데 (올라갈 수는 없고) 최대로 탈 수 있는 사람수(비용)는 주어진다. 각 층에서는 서거나 서지 않거나 할 수 있는데 그 층에서 서게 되면 기다리던 사람 모두를 태워야 한다. 각 층에서 타는 사람수와 사람들이 각각 가지고 있는 돈은 알고 있다.
나는 엘리베티어가 1층까지 내려왔을 때 엘리베이터에 타 있는 사람들을 협박해 지갑에 있는 돈을 꺼내 갈 수 있다. 돈을 최대로 많이 가져가려면 몇층몇층에서 세워야 할까요 ?
정도 입니다. ㅋ
13년 전 link
-
-
-
룡이 -
덕분에 성공했습니다 ^ㅡ^
2중 포문까지는 아이디어가 안 떠오르고 ;; 3중으로 해결했네요.
일단 마지막 한 줄 채워두고,
for(int k=lastIndex-1 ; k >= 0 ; k--) {
for(int c=0 ; c <= maxEnergy ; c++) {
for(int j=k+1 ; j <= lastIndex ; j++) {
}
}
}
이렇게 포문을 돌려서 해결했습니다.
Recursion 이 제거되서 Large-set 도 잘 돌아가고 Running Time 도 빨라진것 같네요.
근데 실질적인 이론적 Complexity 는
Recursion 은 2차원 Array 를 채우는 거니까 array 의 O(row * col),
이 For 문 방식은 O(row * col * row) 가 되는 것 같네요.
그래도 실질적 Running Time 은 훨씬 빨라진 것 같습니다. ^^
13년 전 link
-
-
-
VOCList -
사실은 Recursion 판에서도 시간 복잡도는 O(row * col * row)라고 보시는 것이 맞습니다.
음... 이렇게 생각해보시면 간단한데요. solveDp(r, c)가 한번 호출될 때 마다 DP Table중 한 칸이 채워지게 되잖아요? 그런데 이 함수를 한번 호출할 때 마다 함수 안에 있는 for loop가 row에 대해서 loop를 돌게 됩니다. 요컨데 한개의 (r, c) 조합에 대해서 row만큼의 연산을 하고 나서야 이 테이블을 채울 수 있습니다. 그런데 이와 같은 (r, c) 상태는 row * col 개 만큼 있음으로 모든 테이블을 채우는데는 상태갯수 * row == row * col * row 만큼의 연산이 필요하게 됩니다.
13년 전 link
-
-
-
hyunhwan -
잠이 안와서 이 문제에 대해 잠깐 생각을 해봤는데, 시간 복잡도 O(NC), 공간 복잡도 O(C)에 풀릴 것 같네요. 여기서 N은 층 수, C는 최대 에너지를 뜻합니다.
아마 DP를 위해서 저장하는 테이블을 관찰해 보면, 동일한 에너지에 대한 최적값들을 층의 역순으로 나열하면 단조 증가의 형태를 보일 것 입니다. 이는 (현재층수,사용한에너지)에 대한 최적 값은 (현재층수-1,사용한에너지)의 최적 값이나
(현재층수,사용한에너지-현재층에서필요한에너지)(현재층수-1,사용한에너지-현재층에서필요한에너지)의 최적값에 (해당층에서 얻는 이득을 합한 값) 둘 중에 하나가 되기 때문입니다.음 말이 복잡한데 조금 더 정리를 해보자면, 가령 (현재층수,사용한에너지) 의 값이 바로 앞층에서 똑같은 에너지를 썼는데도 이득이 나아지지 않을 경우에는 바로 앞층에서 똑같은 에너지를 써서 만든 답을 유지 하는 게 좋은 것이고, 더 좋은 경우가 있을 경우 이것으로 갱신을 해두는데 이역시도 바로 앞 층에서 계산된 결과를 바탕으로 유지가 됩니다. 따라서 맨 끝 층까지 볼 필요 없이 현재 층보다 바로 윗층과 현재 층에 대한 계산값의 테이블만 참조를 하면 된다는 것입니다. 따라서 시간복잡도는 앞서 이야기한 복잡도가 나옵니다. 그리고 여기서 조금 더 머리를 굴리면 필요한 메모리 역시 사용한 최대 메모리에 비례하는 양 만큼만 잡아 놓으면 값을 계산할 수 있습니다.
생각나는데로 적다보니 잘못된 부분도 있을지 모르겠네요. 도움이 되길 바랍니다.
잘못된 부분이 있어서 수정하였습니다.
13년 전 link
-
-
-
Taeyoon_Lee -
그럼 논문에 libe's method, libe's theorem 으로 소개가 되었겠군요~ +_+
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
룡이
DP 에 있어서 도움을 요청합니다.
DP 문제를 Recursion 방식으로 풀도록 코딩을 했는데
Small-set 에서는 시간 내에 결과가 잘 나오는데 Large-set 에서는 Stack Overflow 가 납니다.
For 문 형태로 바꾸려고 시도해보고 있는데 내공이 부족하다보니 잘 안 되네요.
도움을 부탁합니다 ' ㅁ'
State 는 두 개 입니다. (현재 index, 사용가능 money (정수))
각 State 마다 얻는 점수(정수)가 있고, 그 index 를 선택할 경우 쓰는 비용(정수)이 있습니다.
목적은 있는 돈을 다 쓰면서 점수를 최대화 하는건데요.
이동은 index 가 작은거에서는 큰 걸로 다 이동할 수 있습니다.
DP 를 푸는 수식은 이렇구요 (여기에 Latex 수식 쓰면 이미지로 변환해주는거 있으면 좋겠어요)
V(index,money) = Max_(k=index+1 to last) ( V(index, money), R(k)+V(k,money-C(k) )
V() 는 결과함수, R() 는 각 Index 마다 점수가 저장된 배열, C() 는 각 Index 마다 비용이 저장된 배열.
비교적 간단한 DP 형태인거 같은데, For 문으로 바꾸려니 어렵네요 ;;
아래처럼 코딩을 했는데요.
시작 index 는 0, 주어지는 money 는 case 마다 다 다릅니다.
int solveDp(int index, int remain) {
// 여긴 Memoization 부분, -1 이면 가능한 경우가 없는 걸로 사용
if(dp[index][remain] >= -1) {
return dp[index][remain];
}
}
Recursion 없이 For 문으로 할려면 Index 를 Last 부터 시작해서 0 으로 거꾸로 채워 올라와야 할 것 같은데,
가르침을 부탁드립니다. 대부분의 DP 는 FOR 문으로도 된다고 배운것 같은데 얘도 되는 문제가 맞나요 ?
13년 전