|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
11/08/12 01:06
UVA에 있던 문제인데요 98 France라는 문제가 있습니다. 제가 2년전에 푼 문제인데 몇번인지는 기억이 안나네요.
그 문제를 보면 어느 나라대 어느 나라는 승률이 몇퍼센트고 이런 표가 주어지고 최종적으로 16개국중 우승할 확률이 가장 높은 국가를 구하는 것이었습니다. 이런 표가 있다고 칩니다 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 이 표를 토대로 각 국끼리의 승리 확률을 표로 넣습니다. 0 대 A는 0이 70 A가 30 이런식으로 말이죠. 0 1 2 3 4 5 6 7 8 9 A B C D E F 이런 순서대로 토너먼트 대진을 치루는데 0 이 1과 50 대 50이고 2 와 3이 70 대 30 이런식으로 승리 확률이 있을 겁니다. 이 때 가장 단순하게 프로그래밍 하면 0이 우승할 확률을 매겨보고 그 다음 처음부터 다시 해서 1이 우승 확률 매기고...이런식으로 한다면 같은 계산을 수십번 해야 합니다. 정말 비효율 적이죠 이걸 그런 비효율적인 방법 없이 해결하기 위한 방법이 다이나믹 프로그래밍입니다.
11/08/12 01:10
제가 저 문제를 풀때는 이미 저장된 계산 결과와 원래 테이블의 계산 결과를 섞어서 사용했기 때문에 중첩되는 계산은 나오지 않았습니다.
메인 테이블과 계산용 테이블 2개(데이터의 변화를 막기 위해)를 써서 해결했습니다. 그 과정이 좀 복잡해서 다시 설명드리기가 좀 애매하네요;; 혹 필요하시면 쪽지로 메일 주소 보내주시면 제가 주석 좀 더 달고 명확하게 해서 보내드리겠습니다.
11/08/12 01:40
예가 좀 조잡하지만 앞서에서 어떤 문제를 풀기 위해서 일단 27 * 13 = 351을 계산했다고 칩시다. 이걸 다른데 저장해 놓습니다. 한참 뒤에 (27*5) * (13*2) 라는 걸 풀어야 하는 상황이 왔습니다. 이걸 다시 계산하지 말고 앞서 계산한 결과를 이용해서 351 * 5 * 2 를 푸는 게 그냥 27*5*13*2를 계산하는 것보다 좋겠죠... 원글에 써 주신 점화식도 좋은 예죠 An = An-1 *3 + 1이 있다고 할 때 An-1항을 미리 계산해 놨다면 An 구하는 건 엄청 쉽겠죠. 이런 식으로 An를 계산하기 전에 An-1항을 미리 계산하게끔 계산 과정을 잘 설계하고 이용하면 그게 dynamic programming이 되는 거죠...
11/08/12 10:33
크크 ACM-ICPC 단골손님 DP군요. 꼭 마스터 하시기 바랍니다.
그리고 알고리즘 쪽에 관심이 많으시다면 MEMOIZATION (메모이제이션)도 같이 공부하시면 되겠네요 :-)
|
||||||||||