태그 : C

단어 뒤집기 알고리즘(?)... 행복한 프로그래밍

 올해 읽었던 책중에서 임백준 님이 쓰신 책이 나에게 상당히 많은 도움이 되었다. '누워서 읽는 알고리즘', '소프트웨어 산책'을 읽고 큰 감명(?)을 받은 나는 이 분의 책을 다 읽겠다는 생각으로 최근에는 '행복한 프로그래밍'을 읽고 있는데, 여기에 나오는 문제중에 단어 뒤집기 알고리즘이라는 것이 있다.

 책에는 Java로 짜놓은 버전만 나오고, C로 한번 짜보라는 얘기가 적혀 있는데 그냥 관심이 생겨서 C로 한번 짜보았다. 그다지 색다르거나 특이한 건 없지만 간만에 짧게나마 머리를 굴려봤다는 의미에서 포스팅 한다. 느낀 점이라면 C로 프로그램을 짤려면 포인터를 확실히 알아야 겠구나~ 하는 생각을 다시 한번 했다.
대충 이런 식으로 짜 보았다

by sakuragi | 2007/08/08 05:40 | :: R space :: 과제 | 트랙백 | 덧글(9)

N-여왕말 문제... N-Queen Problem

 어쩌면 이번 학기 이 과목의 마지막 과제가 될지도 모르는 과제가 나왔다. 되추적(Backtracking) 방법을 얘기 할 때 가장 많이 거론 되는 듯한 N-여왕말(N-Queen) 문제이다. 어떤 문제인가하면 서양 장기(Chess:이후 체스)의 여왕말(Queen:이후 퀸)을 서로가 서로의 이동경로가 아닌 위치에 있도록 최대한 많은 퀸을 체스판 위에 놓는 문제이다.

  원래 체스판은 8ⅹ8이지만 간단히 4ⅹ4일 경우에 좌측의 결과와 같이 되는 경우를 찾는 것이 바로 N-Queen 문제 이다.
 4ⅹ4일 경우에는 좌측과 같은 2가지의 경우만 나오지만 체스판이 커지면 커질수록 다양한 경우의 수가 나온다. 우선 정해진 것은 NⅹN의 체스판에 올라갈 수 있는 퀸의 최대 갯수는 언제나 N이 된다는 점이다.

 그렇다면 어째서 이것이 되추적(Backtracking) 방법이 되느냐 하는 것은
첫번째 퀸(1, 1) 위치에 오게 될 경우
두번째 퀸은 (2, 3) 과 (2, 4) 위치에 올 수 있다. 우선 (2, 3) 위치에 퀸을 놓는다면
세번째 퀸을 놓을 수 있는 자리는 없어진다. 그러면 다시 로 돌아가서 두번째 퀸(2, 4) 위치에 놓게 되면
세번째 퀸(3, 2) 위치에 놓을 수 있지만 이렇게 되면 네번째 퀸을 놓을 수가 없어진다. 그렇게 되면 이번엔 다시 로 돌아가서 첫번째 퀸(1, 2)에 놓고 다시 시작한다.

 위의 과정과 같이 결과값을 찾아가다가 그 방법이 아니라는 것을 알았을 때 이전 단계로 돌아가는 것이 바로 되추적 방법이다.

 N-Queen의 문제의 경우 참고 자료에 있는 책을 본다면 좀 더 쉽게 알 수 있을 것이다. 언제나와 같이 나는 참고자료에 있는 'Foundations of Algorithms.....' 책을 참고로 해서 프로그램을 작성하였다.
N-여왕말 문제

by sakuragi | 2007/06/03 01:41 | :: R space :: 과제 | 트랙백(1) | 덧글(9)

데이터 압축에 쓰인다는(?) 허프만 코드... Huffman code

 이번 것은 과제는 아니였는데, 오기로(?) 해 버렸다. 크루스칼 알고리즘을 힘들게 해결한 이후에, 이제는 슬슬 인터넷에서 소스를 찾기보다는 내 자신이 교재(참고자료 참고)의 pseudo code(의사 코드)를 보고, 몇시간을 감이 잡힐 때까지 그림을 그려보거나 골똘히 생각하다가 조금씩 실마리가 잡히면 코딩을 시작하는 형태가 되어 가고 있다.
 (참고로 나는 프로그램을 잘하거나 소질이 있는 것이 아니라서 이 정도의 프로그램을 짜려면 며칠이 걸린다. 이 허프만 코드의 경우 코딩을 시작 하기까지 두시간 정도를 책을 보면서 어떻게 구현할 수 있을까 생각한 후에, 코딩을 시작했고 꼬박 앉은 자리에서 열시간 정도를 삽질을 하면서 프로그램을 트리 구성까지 완성시켰다. 그리고 마지막 결과 트리 출력 부분을 만들기 위해 추가로 서너시간 가량이 걸렸다.)
  이렇게 최근 알고리즘에 열을 올리면서 이전에는 왜 알고리즘이나 자료구조 책에는 바로 컴파일을 할 수 있는 소스가 아니고, pseudo code만 나와있어서 이렇게 사람을 힘들게 하냐고 생각 했는데... 최근 1~2주 사이에는 힘들어도 pseudo code를 보면서 내 입맛에 맞춰서 코딩(요리)을 하는 재미도 나름대로 솔솔하다는 생각도 든다.

 그리고 지금 보고 있는 교재의 pseudo code가 다른 알고리즘이나 자료구조 책보다 깔끔하게 정리가 잘 되어 있다는 생각이 든다. 필요한 부분만 쉽게 설명해주고 pseudo code로 보여준다는 느낌이다.

 허프만 코드는 기존의 영문자 ASCII 코드가 7비트(8비트)로 문자를 표현하고 있지만, 실재로는 하나의 문서에서 몇백개나 되는 문자를 모두 쓰는 경우는 매우 드문다는 점에 착안해서, 쓰는 문자만 뽑아내고 그 문자에 가중치(빈도수)를 주어서, 자주 나오는 문자를 짧게 부호화(이진코드화)해서, 하나의 문자로 봤을때나 전체의 문자열로 봤을 때나, ASCII 코드보다 적은 비트로 표현이 가능해져서 압축을 하는 효과가 된다는 개념이다.

   지금 학교에서 배우는 교재(참고자료 참고)에서는 이번 알고리즘 역시 탐욕적인 방법으로 분류되어 나온다. 지금까지 탐욕적인 알고리즘을 몇가지 봤는데, 분할정복법의 요점이 재귀, 동적계획법의 요점이 행렬(배열)이였다면 탐욕적인 알고리즘의 요점은 정렬이라고 느꼈다. 크루스칼이나 프림의 알고리즘도 그 순간에 최적인 방법을 택하기 위해서는 정렬이 필수였고, 지금 보는 허프만 코드 역시 이진 트리를 구성하기 위해서는 정렬된 우선순위 대기열을 사용한다.

 허프만 코드에서 이진 트리를 어떻게 만드는지와 같은 알고리즘이 돌아가는 방식에 대해서는 인터넷에서 검색하면 많이 나오므로 생략한다. 소스는 철절히 교재의 pseudo code의 리듬으로 짰으므로, 교재가 있다면 이해하는데 어렵지 않으리라 생각된다.

 이건 개인적인 얘기이고 지난번에도 얘기 했지만, 알고리즘 관련 포스팅의 경우 조회수는 참 높은데, 조회수에 비해 댓글은 거의 없다. 뭔가 댓글을 좀 달아주셨으면 좋겠다. 이 부분은 이렇게 하는게 더 좋다라든지... 소스의 어느 부분이 문제라든지.. 아니면 잘 가져가서 쓴다라는 댓글이라도 좋다. 자기 블로그(홈페이지)가 있다면 주소도 좀 남겨주셨으면 좋겠다. 아니면 리퍼러에 남도록 방문해 주면 알아서 찾아갈터인데...

데이터 압축에 쓰이는 허프만 코드 알고리즘

by sakuragi | 2007/05/17 02:39 | :: R space :: 과제 | 트랙백 | 핑백(1) | 덧글(75)

단일출발점 최단경로... Dijkstra Shortest Path

 이번에는 특이한 이름만큼이나 유명하신(?) Dijkstra께서 만드신 단일 출발점에서 최단 경로를 구하는 다익스트라 알고리즘이다. 플로이드의 알고리즘과의 차이라면 플로이드의 알고리즘이 각 정점에서 다른 모든 정점으로 가는 최단 경로를 모두 구했다면, 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다는 것이다.

 그러면 왜 플로이드 알고리즘과 세트로 포스팅 한 것이 아니고, 이렇게 떨어져서 포스팅 하게 되었냐고 한다면, 플로이드 알고리즘은 동적 계획법으로 만들어진 알고리즘이고, 다익스트라 알고리즘은 앞의 두 포스팅인 최소비용 신장 트리처럼 탐욕적인 방법으로 만들어진 알고리즘이기 때문이다.

 알고리즘의 전체적인 구조는 프림의 알고리즘과 거의 차이가 없으므로, 아래의 프림 알고리즘을 알고 있다면 이 알고리즘은 10~20분만에 해결 할 수 있다.
다익스트라 단일 출발점 최단 경로 알고리즘

by sakuragi | 2007/05/09 03:01 | :: R space :: 과제 | 트랙백 | 덧글(7)

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: