'동적프로그래밍'에 해당되는 글 2건

  1. 2007.06.11 동적프로그래밍, 그리디 알고리즘 by 지영아빠
  2. 2007.05.23 TOPCODER 문제:CaptureThemAll by 지영아빠

[ 동적프로그래밍 (Dynamic Programming Algorithm) ]
 - 분할정복 기번과 같이 부분 문제의 해를 결합해 문제를 해결한다.
 - 재귀호출에 동적프로그래밍을 사용하면 메모하기 (memorize) 혹은 동적프로그래밍 방법이라고 칭함
 
 - 4단계로 처리함
   1) 최적의 구조를 찾는다.
   2) 최적의 값을 재귀적으로 정의한다.
   3) 최적해의 값을 상향식(bottom-up) 방법으로 계산한다.
   4) 계산된 정보들로부터 최적해를 구한다.
- 최적 부분 구조(optimal substructure)를 가진다는 것은 동적 프로그래밍이 적용될 수 있는 좋은 단서임.
- 부분 문제의 최적해로부터 전체 문제의 최적해를 구함

[ 그리디 알고리즘(Greedy Algorithm)]  ==> 탐욕 알고리즘
 - 그리디 방법위 요소들
  1) 문제의 최적 부분구조를 결정한다.
  2) 재귀적 해를 만든다.
  3) 재귀의 각 단계에서 최적의 선택 중 하나가 그리디 선택임을 증명한다. 그렇기 때문에 그리디 선택을 하는 것은 항상 안전하다.
  4) 그리디 선택으로 유도된 하나의 부분 문제를 제외한 모든 부분 문제에는 고려할 활동이 존재하지 않음을 보인다.
  5) 그리디 방법론을 구현하는 재귀적 알고리즘을 만든다.
  6) 재귀적 알고리즘을 순환 반복되는(iterative)알고리즘으로 바꾼다.



출처: Introduction to Algorithms 2ed. (MIT Press, Cormen)

신고
Posted by 지영아빠

<TOPCODER 문제풀이>
문제명:  CaptureThemAll
문제: http://www.topcoder.com/stat?c=problem_statement&pm=2915&rd=5853
사용알고리즘: DFS, 동적프로그래밍(dynamic programming)
-----------------------------------------------------------
얼마전에 알게된 사이트인데.. 재미있네요.. 문제를 풀어봤습니다.
개발 및 테스트 언어: Visual C++ 2005
-----------------------------------------------------------

Problem Statement

    Harry is playing magical chess. In this version of the game, all pieces move the same way as in regular chess, but players can cast some magical spells. Unfortunately, Harry's opponent, Joe, has captured all of Harry's pieces except one knight; Joe, on the other hand, still has a queen and a rook. The only chance Harry has to win this game is to cast a spell, "Haste", that will allow Harry's knight to make several moves in a row. You should determine the minimal number of moves the knight needs to capture both the rook and the queen, assuming neither of them moves. You may capture them in either order - rook first or queen first.



You will be given a String, knight, containing information about the knight. You will also be given a String, queen, and a String, rook, giving you information about Joe's pieces. knight, rook and queen will be formatted as "cr", where c is a character between 'a' and 'h', inclusive, determining the column on the board ('a' is the first column, 'h' is the last), and r is a digit between '1' and '8', inclusive, determining the row (1 is the lowest, 8 is the highest).
 

Definition

   
Class: CaptureThemAll
Method: fastKnight
Parameters: String, String, String
Returns: int
Method signature: int fastKnight(String knight, String rook, String queen)
(be sure your method is public)
   
 

Notes

- A knight's jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if knight is in the (0,0) now, it can be in (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2) after his move.
- The knight will capture one of Joe's pieces if it ends its move in the cell that the piece occupies.
- The knight cannot jump out of the board.
- A chessboard has 8 rows and 8 columns.
 

Constraints

- knight, rook and queen will all be distinct.
- knight, rook and queen will be formatted as "cr", where c is a lowercase character between 'a' and 'h', inclusive, and r is a digit between '1' and '8', inclusive.
 

Examples

0)
   
"a1"
"b3"
"c5"
Returns: 2
From "a1", the knight can move directly to "b3" and capture the rook. From there, the knight can move directly to "c5" and capture the queen.
1)
   
"b1"
"c3"
"a3"
Returns: 3
The rook and the queen are both 1 move away from the knight. Once the knight captures one of them (it doesn't matter which one), it can return to its starting location, and capture the other piece in one more move.
2)
   
"a1"
"a2"
"b2"
Returns: 6
The rook and the queen are close, but it takes 6 moves to capture them.
3)
   
"a5"
"b7"
"e4"
Returns: 3
4)
   
"h8"
"e2"
"d2"
Returns: 6


-----------------------------------------------------------
#include <string>
#include <vector>
#include <stack>

using namespace std;

#define USE_PRINTMATRIX 0

typedef pair <int, int> PAIR;

const int MAXROW = 8;
const int MAXCOL = 8;
const int MAXMOVE = 8;
const int MAXINT = static_cast <int> ( static_cast<unsigned int>(1 << 31) -1);

int dist[MAXROW][MAXCOL]={0};
PAIR move[MAXMOVE] =
{
 PAIR (-2,-1), PAIR (-2, 1), PAIR (-1,-2), PAIR (-1, 2),
 PAIR ( 1, 2), PAIR ( 1,-2), PAIR ( 2, 1), PAIR ( 2,-1)
};

// 문자열에서 point로 뽑아줌..
PAIR getpoint (std::string p)
{
 return PAIR ( p.at (0) - 'a', p.at (1) - '1');
}

bool isvalidpoint (PAIR& point)
{
 if ( point.first < 0   ) return false;
 if ( point.second < 0   ) return false;
 if ( point.first >= MAXROW ) return false;
 if ( point.second >= MAXCOL ) return false;

 return true;
}

// 움직임이 가능한 다음 좌표를 뽑아줌..
std::vector < PAIR > getnextpoints ( PAIR cur)
{
 std::vector < PAIR > ret;
 for ( int i = 0; i < MAXMOVE; i++)
 {
  PAIR point = PAIR (cur.first + move[i].first, cur.second + move[i].second);
  if ( isvalidpoint ( point ) )
  {
   ret.push_back ( point ) ;
  }
 }
 return ret;
}

void print (int tmp[MAXROW][MAXCOL])
{
#if (USE_PRINTMATRIX==1)
 int i = 0, j = 0;
 printf ("---------------matrix begin---------------\r\n");
 for ( i = 0; i < MAXROW; i++)
 {
  printf("{ ");
  for ( j = 0; j < MAXCOL-1; j++)
  {
   printf ("%d, ", tmp[i][j]);
  }
  printf ("%d }\r\n", tmp[i][j]);
 }
 printf ("---------------matrix end---------------\r\n");
 printf ("\r\n");
#endif
}
void initdist (int dst[MAXROW][MAXCOL], PAIR start = PAIR(MAXINT,MAXINT) )
{
 for ( int  i = 0; i < MAXROW; i++)
 {
  for ( int j = 0; j < MAXCOL; j++)
  {
   dst[i][j] = MAXINT;
  }
 }
 if ( isvalidpoint (start) ) // 초기화 distance를 0으로 세팅함
 {
  dst[start.first][start.second] = 0;
 }
}

// DFS 탐색 알고리즘.., 동적프로그래밍도 (dynamic programming)
void dfs (PAIR start, std::stack < PAIR >& st, int dst[MAXROW][MAXCOL])
{
 std::vector < PAIR > ej = getnextpoints (start);
 std::vector < PAIR >::iterator pos;
 for (pos = ej.begin (); pos != ej.end (); ++pos)
 {
  int dsttmp = dst[start.first][start.second] + 1;
  if ( dsttmp >= dst[pos->first][pos->second] )   // 거리를 최소값으로 유지  ==> 최소값이 아니면.. 더이상 찾을 필요없음
   continue;          
  dst[pos->first][pos->second] = dsttmp;     // 거리를 업데이트
  st.push ( *pos );
  bfs (*pos, st, dst);
  st.pop ();   // 자기 자신을 pop시킨다.
 }
}

class CaptureThemAll
{
public:
 int fastKnight(string knight, string rook, string queen)
 {
  std::stack < PAIR > st;
  PAIR kp = getpoint (knight);
  PAIR rp = getpoint (rook);
  PAIR qp = getpoint (queen);

  // 1. knight<->rook, knight<->queen의 최단거리 계산
  initdist (dist, kp);     // 초기화 및 flag setting
  bfs ( kp, st, dist);     // BFS 탐색.. ---> 다 돌면..
  print (dist);        // distance 출력
  int dstktor = dist[rp.first][rp.second]; // knight <-> rook  최소거리
  int dstktoq = dist[qp.first][qp.second]; // knight <-> queen 최소거리

  // 2. rook<->queen의 최단거리 계산
  initdist (dist, rp);      // 초기화 및 flag setting
  bfs (rp,st,dist);
  print (dist);        // distance 출력
  int dstrtoq = dist[qp.first][qp.second]; // rook <->queen 최소거리

  // rook과 queen을 잡을 최단거리 계산
  int dst1 = dstktor + dstrtoq;    // knight->rook->queen
  int dst2 = dstktoq + dstrtoq;    // knight->queen->rook
  int dst3 = dstktor*2 + dstktoq;    // knight->rook->knight->queen
  return std::min ( dst1, std::min (dst2,dst3));
 }
};


void main(void)
{
 CaptureThemAll ca;
 print (dist);
 printf ("dst:%d\r\n", ca.fastKnight ("a1", "b3", "c5"));
 printf ("dst:%d\r\n", ca.fastKnight ("b1", "c3", "a3"));
 printf ("dst:%d\r\n", ca.fastKnight ("a1", "a2", "b2"));
 printf ("dst:%d\r\n", ca.fastKnight ("a5", "b7", "e4"));
 printf ("dst:%d\r\n", ca.fastKnight ("h8", "e2", "d2"));
}
------------------------------------------------------

신고

'관심분야 > 기타' 카테고리의 다른 글

[리뷰]자바 이론과 실습: 제네릭스 해부, Part 1  (0) 2008.10.21
실버라이트 2.0 RC버전 발표  (0) 2008.09.26
TOPCODER 문제:CaptureThemAll  (0) 2007.05.23
Silverlight관련글  (0) 2007.05.04
Posted by 지영아빠

티스토리 툴바