장기판에서 馬 가 시작지점에서 원하는 지점까지
최소 움직임을 보이는 경로를 찾는 문제이다.
이는 최소비용을 구한다는 점과 , 그 경로를 구한다는 점에서
DP( Dynamic Programming) 문제임을 눈치챌 수 있다.
이를 해결하기 위한 아이디어를
밑에 그림으로 설명을 하였다.
실제로 이 아이디어를 C언어 코드로 구현을 하였다
밑에 링크에서 코드를 볼수 있다.
http://ideone.com/QYOfU
실제로 2차원 배열에 기록을 하면서
시작지점의 값이 INF 에서 다른 값으로 변하는 순간
바로 그값이 최소비용이다. 그리고 메모라이즈 된 값들을
이용하여 값을 역추적.. 루트를 찾아낼수 있는 것이다.
'알고리즘' 카테고리의 다른 글
장기판 馬 원하는 지점까지 최소움직임을 보이는 이동경로 구하기 (DP) (1) | 2012.03.11 |
---|---|
[python] 하향식 연산자 우선순위 (0) | 2011.08.07 |
피어슨(pearson) 스코어 (1) | 2011.05.09 |
유클라디안 스코어 (0) | 2011.05.09 |
Fuzzy C-Means , (4) | 2011.03.27 |
헝가리안 알고리즘 hungarian algorithm 구현 (2) | 2011.02.20 |
댓글을 달아 주세요
완전상미분방정식 검색했다가 좋은 글들 보고갑니다. ^^ 이제 막 컴퓨터공학과 2학년인 사람으로써 정말 멀게만 느껴지지만 열심히 하면 성대아싸님 처럼 멋지게 프로그램도 짜보고싶습니다. ㅎㅎ!! 내일도 화이팅이요!!!
2012.03.14 00:30 신고 [ ADDR : EDIT/ DEL : REPLY ]