기본 콘텐츠로 건너뛰기

개발 공부 - [동적계획법 (Dynamic Programming)] Dynamic Programming - 1

다이나믹 프로그래밍 = 동적계획법


피보나치 수열
: 많은 계산이 중복됨
-> recursion 으로 계산하니까 중복현상이 있음!


Memoization
int fib(int n)
{
     if (n==1 || n==2)
         return 1;
     else if (f[n] > -1) /* 배열 f가 -1으로 초기화되어 있다고 가정 */
         return f[n]; /* 즉 이미 계산된 값이라는 의미 */
     else {
         f[n] = fib(n-2) + fib(n-1); /* 중간 계산 결과를 caching */
         return f[n];
     }
}


bottom-up 방식으로도 중복 계산을 피할 수 있다.

이항 계수(Binomial Coefficient)


int binomial(int n, int k)
{
     if (n == k || k == 0)
         return 1;
     else
         return binomial(n - 1, k) + binomial(n - 1, k - 1);
}

역시 많은 계산이 중복되어 일반적으로 
n     n-1             n-1
   =           +                   과 같은 경우의 수를 볼 수 있다.
k       k              k-1



Memoization
int binomial(int n, int k)
{
     if (n == k || k == 0)
         return 1;
     else if (binom[n][k] > -1) /* 배열 binom이 -1로 초기화되어 있다고 가정 */
         return binom[n][k];
     else {
         binom[n][k] = binomial(n-1, k) + binomial(n-1, k-1);
         return binom[n][k];
     }
}



Dynamic Programming
int binomial(int n, int k)
{
         for (int i=0; i<=n; i++) {
             for (int j=0; j<=k && j<=i; j++) {
                 if (k==0 || n==k)
                     binom[i][j] = 1;
                 else
                     binom[i][j] = binom[i-1][j-1] + binom[i-1][j];
                 }
         }
         return binom[n][k];
}

bottom-up 방식으로 중복 계산을 피함 



Memoization vs. Dynamic Programming

- 순환식의 값을 계산하는 기법들이다.
- 둘 다 동적계획법의 일종으로 보기도 한다.
- Momoization은 top-down방식이며, 실제로 필요한 subproblem만을 푼
다.
- 동적계획법은 bottom-up 방식이며, recursion에 수반되는 overhead가
없다.






댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - PC 카카오톡 작업 표시줄 아이콘 이미지 변경 방법

PC 카카오톡 사용시 작업 표시줄에서 아이콘 이미지를 변경하는 방법이다. 1) 작업 표시줄 내 카카오톡 아이콘에서 마우스 오른쪽 버튼을 누른  뒤 속성에 들어간다. 2) 아이콘 변경에서  C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS DOS Icons) 등을 누른 뒤 적당한 것을 선택하여 적용한다. * 사내 메신저 아이콘을 참고해도 된다. 참고 : 기본 아이콘 위치 https://blog.silnex.kr/windowstip-windows-%EA%B8%B0%EB%B3%B8-%EC%95%84%EC%9D%B4%EC%BD%98-%EC%9C%84%EC%B9%98/ 2022. 11. 29.  생각보다 유입이 많아서 놀랐습니다. PC 카톡 사용자 화이팅!