태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Notice

'(탈퇴) Reuent's Post'에 해당되는 글 25

  1. 2010.03.24 Computer Vision #3. My first OpenCV Project.(1)
  2. 2010.03.24 Computer Vision #2. Setting OpenCV 2.0 with VS 2008.
  3. 2010.03.05 Computer Vision #1. An Introduction.(2)
  4. 2010.03.05 2010. 3. 5
  5. 2010.03.04 죄송합니다. -_-;;;; 조금 더 쉴게요.
  6. 2010.03.04 Reuent 포스트 연기.
  7. 2010.03.04 Algorithm #2. Search algorithm. - 2.5 Red-Black Tree (2).
  8. 2010.03.04 Algorithm #2. Search algorithm. - 2.5 Red-Black Tree (1).
  9. 2010.03.04 Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (2).
  10. 2010.03.04 Algorithm #2. Search algorithm. - 2.4 Binary Tree Search (1).
  11. 2010.03.04 12 / 26 Reuent 포스트 연기.
  12. 2010.03.04 Algorithm #2. Search algorithm. - 2.3 Binary Search.(1)
  13. 2010.03.04 Reuent 연기공지. -_-
  14. 2010.03.04 Algorithm #2. Search algorithm. - 2.2 Sequential Search.
  15. 2010.03.04 Algorithm #2. Search algorithm. - 2.1 검색 알고리즘의 종류. ( & Algorithm vs. Data Structure (??) )
  16. 2010.03.04 복귀신고 -_-
  17. 2010.03.04 Reuent 포스트 연기 공지.
  18. 2010.03.04 9 / 29.
  19. 2010.03.04 Algorithm #1. Sort algorithm. - 1.6 Radix Sort algorithm.
  20. 2010.03.04 Algorithm #1. Sort algorithm. - 1.5 Heap Sort algorithm.
  21. 2010.03.04 Algorithm #1. Sort algorithm. - 1.4 Quick Sort algorithm.(4)
  22. 2010.03.04 Algorithm #1. Sort algorithm. - 1.3 Bubble Sort algorithm.
  23. 2010.03.04 Algorithm #1. Sort algorithm. - 1.2 Insertion Sort algorithm.
  24. 2010.03.04 Algorithm #1. Sort algorithm. - 1.1 정렬 알고리즘의 필요성, 그리고 알려진 알고리즘의 종류와 일반적 특성.(1)
  25. 2010.03.04 Reuent - 포스팅 계획서.

저번 포스트의 내용까지 다 설정하셨다면, 기본적인 OpenCV 의 설정은 끝났습니다.

그럼 이제 실제로 프로젝트를 만든 뒤, 간단한 코딩을 해 보겠습니다.

사용자 삽입 이미지

우선 Win32 Console 프로젝트를 생성합니다.

사용자 삽입 이미지

VS 상에서 Alt + F7 을 눌러 Project Property 를 편집합니다.

저 위에 있는 Additional Dependencies 항목에 다음과 같이 입력합니다.

cv200.lib highgui200.lib cvaux200.lib cxcore200.lib


확인 버튼을 누릅니다.

다음엔 dll 파일들을 프로젝트에 실제로 복사해 넣어줘야 합니다.

복사할 dll 파일들은 다음과 같습니다.

cv200.dll

cvaux200.dll

cxcore200.dll

highgui200.dll


위 dll 파일들은 {OpenCV.sln directory}bin \ Release 디렉토리에 있습니다.

사용자 삽입 이미지

위 파일들을 해당 프로젝트 디렉토리에 복사하여 넣습니다.

사용자 삽입 이미지


복사가 끝났다면, 이제 실제 코딩을 해 봐야겠죠?

우선 코딩하기 전 간단한 이미지 파일 하나를 디렉토리 폴더에 복사한 후에 시작해 주세요.



이제 모든 준비가 끝났습니다!

다음과 같은 코드를 입력해 주세요.





<결과영상>
사용자 삽입 이미지


이것으로 모든 준비는 끝났습니다.

다음 포스트부터는 OpenCV 의 사용법에 대해 알아보죠.

posted by 비회원

이번 포스트는 OpenCV 를 세팅하는 방법에 대한 것입니다.

제 개발환경은 다음과 같습니다.


Windows7 Ultimate K, 32 bit.

OpenCV 2.0

Visual Studio 2008 sp1


우선 준비할 것들은 다음과 같습니다.



1. OpenCV 2.0

2. cmake-2.8.0-win32-x86

3. Visual Studio 2008. - Service Pack 은 없어도 무방합니다만, 인스톨 할 것을 추천합니다.



우선 아래 사이트로 이동하고 다운로드 해 주세요.

http://sourceforge.net/projects/opencvlibrary/

사용자 삽입 이미지

다운로드가 끝난 뒤 인스톨을 시작합니다.


사용자 삽입 이미지

저 부분만 체크하신 뒤에 설치를 진행해 주시면 됩니다.


OpenCV 의 설치가 끝났다면, 이젠 아래의 첨부파일을 다운로드 후 인스톨 해 주세요.



사용자 삽입 이미지
마찬가지로 저 부분을 체크해 줍니다.

설치가 끝났다면 cmake 를 실행해 주세요. 실행하신 뒤 다음과 같은 step 을 따라주시면 됩니다.


사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지

사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지
사용자 삽입 이미지

posted by 비회원

Computer Vision 이라는 학문은 개인적으로 '컴퓨터에 사람의 눈을 달아주는 것' 이라 생각합니다.

컴퓨터라는 기기는 스스로의 힘으로 현상계(Real World) 에 존재하는 사물을 인식할 수 없습니다.
왜냐구요?
컴퓨터가 가지는 입력장치는 일반적으로 2가지 - 키보드와 마우스 - 에 불과한데, 이들은 모두 현상계의
정보를 전달하기엔 미약하기 때문이죠.

따라서 우리들이 살아가는 세상의 정보를 '인식' 할 수 없고, 따라서 '인지' 할 수 없기에 컴퓨터는
스스로의 힘으로는 아무 것도 할 수 없는 단순한 '하이테크 고철덩어리' 가 됩니다.

아주 많은 일을 할 수 있지만, 혼자서는 어떤 것도 할 수 없는 '도구' 에 불과할 뿐입니다.

그래서 컴퓨터 과학자들은 생각했습니다.

컴퓨터에 '눈' 과 '뇌' 를 달아주자고.

따라서 Computer Vision 은 Artificial Intelligence - AI, 즉 인공지능. - 과 뗄레야 뗄 수 없는 학문입니다.

- 앞으로 남은 학부생활동안  제가 할, 그리고 하고 싶은 일은 Vison 을 통해 object 를 추출하고, 이 object 가
  무엇인지를 컴퓨터에게 효과적으로 학습시키는 일입니다. -

이에 관해서 수많은 과학자들이 연구해 왔고, 수많은 이론이 등장했습니다.

이 이론들을 C, C++ 언어 기반으로 구현한 라이브러리가 OpenCV 입니다.

꼴난 학부 3학년이 무슨 대단한 주제를 제시하고, 포스팅할 수 없습니다.
제가 무슨 희대의 천재도 아니고.

제가 이번 포스팅 주제로 할 부분은 크게 3가지 입니다.

1. OpenCV 사용법 익히기.
2. 기본 Image Processing 이론 소개.
3. Computer Vision 의 주요 주제 몇가지를 소개하는 것. 그리고 가능하다면 구현하는 것.

이들을 OpenCV 를 기반으로 해서 '소개' 하는 것이 목표입니다.

이번엔 공백기간 없이 잘 해보겠습니다.
- 전 항상 용두사미로 끝나는 경향이 있죠. 반성하겠습니다. -


그럼 다음엔 OpenCV 세팅에 대해 포스팅 해 보겠습니다.

posted by 비회원

이전 포스트 복구했습니다.

앞으로 차근차근 수정해 나가겠습니다.

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

2010. 3. 5  (0) 2010.03.05
죄송합니다. -_-;;;; 조금 더 쉴게요.  (0) 2010.03.04
Reuent 포스트 연기.  (0) 2010.03.04
12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
posted by 비회원

할 일이 더 생겨서 말입니다 -_-;;;

한 주만 더 쉴게요. 죄송합니다.

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

2010. 3. 5  (0) 2010.03.05
죄송합니다. -_-;;;; 조금 더 쉴게요.  (0) 2010.03.04
Reuent 포스트 연기.  (0) 2010.03.04
12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
posted by 비회원

2 / 6 에 친척분 뵈러 대구 내려갑니다. -_-;;

아마 월요일쯤에 포스팅 가능할 것 같네요.

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

2010. 3. 5  (0) 2010.03.05
죄송합니다. -_-;;;; 조금 더 쉴게요.  (0) 2010.03.04
Reuent 포스트 연기.  (0) 2010.03.04
12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
posted by 비회원

Red-Black Tree 두 번째 포스트입니다.
이번엔 Red-Black Tree 의 회전에 대해서 알아볼까요.

앞서 Red-Black Tree 의 유지조건에 대해 언급드렸을 겁니다.
Introduction to Algorithms 의 Red-Black Tree 절에 따르면 다음과 같은 정의가 성립해야 하죠.

1. Every node is either red or black.
     모든 node 는 적색 혹은 흑색이다.

2. The root is black.
     root 는 흑색이다.

3. Every leaf is black.
     모든 leaf 는 흑색이다.

4. If a node is red, then both its children are black.
     만약 한 node 가 적색이라면, 이 node 의 두 자식은 모두 흑색이다.

5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.
     각 node 로부터, node 에서 자손까지의 모든 경로들은 같은 갯수의 흑색 node 를 포함한다(가진다).


 
만약 한 레코드 셋에 새로운 값이 삽입된다고 가정해 봅시다.
그러면 Red-Black Tree 의 성질이 유지될 수 있을까요?

물론 유지될 수도 있습니다.
하지만, 모든 경우에 대한 것은 아니지요. 즉, 유지되지 않는 경우가 생긴다는 말입니다.

레코드 셋에 대한 검색 알고리즘들은 모두 이런 경우를 대비해 삽입 . 삭제 기능을 같이 갖추어야 합니다.
사용자가 레코드 셋을 언제 수정할 지 모르니까요.
그리고 이 알고리즘의 특성을 유지시키기 위한 방법 역시 요구합니다.
애써 구축해 놓은 레코드 셋의 구조가 엉켜버리면 곤란하겠죠.

즉, 아무리 빠르고 강력한 알고리즘이라 할지라도 그 알고리즘의 특성을 유지시키기 위한 프로시저는 반드시
존재해야 한다는 것이죠.

Red-Black Tree 는 사용자에 의해 레코드 셋이 수정될 때마다 rotation - 회전 - 을 수행합니다.
앞서 Red-Black Tree 는 Binary Search Tree 의 일종이라는 말씀을 드렸을 겁니다.
그럼 우선 Binary  Tree 의 rotation 연산을 살펴볼까요.

rotation 연산은 2개가 있습니다.
짐작하시다시피 Left Rotation, Right Rotation 이죠.

우선 Left  Rotation 부터 볼까요. 다음의 그림을 기준으로 하여 설명합니다.

사용자 삽입 이미지
Left Rotation.

1. y 의 왼쪽 sub tree 를 x 의 오른쪽 sub tree 로 옮긴 뒤, x 와 y 의 관계를 끊는다.
사용자 삽입 이미지
2. x tree 를 y 의 왼쪽 자손으로 삼는다.
사용자 삽입 이미지

Right Rotation 은 Left Rotation 의 역순으로 생각하시면 됩니다.

-사실, 위에서 설명드린 방식은 정석에서 살짝 벗어난 설명입니다.
하지만 개인적으로는 저렇게 이해하고 있고 -_- 이해도 편하기에 저렇게 설명드렸습니다.
특히 관계를 끊는다는 부분에서 말이죠. -_- -

rotaion 연산은 단지 추상화가 저렇게 될 뿐, 실제 코딩에서는 단순 포인터 연산으로 구현되므로 상수시간 안에
실행될 수 있습니다.
주로 Red - Black Tree 의 삽입 프로시저에서 Left Rotation, Right Rotation 을 실행하는 형식으로 실행되곤 하죠.




결국 오늘 다 못끝냈군요 -_-;;;
다음 포스트에서는 삽입, 삭제 연산을 다루고 Red-Black Tree 의 포스트를 마쳐보겠습니다.
posted by 비회원

이번에 소개할 Red-Black Tree 는 Binary search tree 의 일종입니다.
이전에 구현했던 Binary Search Tree 는 다음과 같은 node 구조체를 선언했었죠.




node 의 값을 저장할 변수와, 좌/우측 link node 의 값을 포함하는 구조체입니다.
하지만, Red-Black Tree 는 여기에서 '색깔' 을 저장할 추가 변수의 선언이 필요합니다.
다시말하면, 각 node 는 'Red' 혹은 'Black' 의 색깔을 갖는다는 것이죠.

그럼 이쯤에서 Red-Black Tree 의 필요성을 설명드려야 할 듯 합니다.

예전 포스트에서 Binary Tree 는 완벽하게 균형이 잡혀있을 경우엔 O ( log N ) 의 성능을 자랑한다는 말씀을 드렸을겁니다.
- Binary Tree 가 균형이 잡혀있다는 의미는 'Tree 의 level' 이 낮아진다는 것을 의미하니까요. -
하지만, Binary Tree 가 한쪽으로 치우친 Skewed Binary Tree 의 꼴을 취하면 취할수록 Tree 의 level 은 올라가고,
검색 시간도 그에 비례하여 증가합니다. 직관적으로 이해하실 수 있겠죠.

이런 단점들을 보완하기 위하여 여러 컴퓨터 과학자들이 연구를 거듭했습니다.
- 사실 Binary Tree 의 불균형 문제는 오랫동안 연구되어 온 주제 중 하나입니다. -
이들의 논제는 '어떻게 하면 주어진 자료집합으로 가장 효율적인 Balanced Binary Tree 를 조직할 수 있는가?' 였죠.

그에 대한 대표적인 이론이 바로 'AVL Tree' 와 'Red-Black Tree', 그리고 'Splay Tree' 였습니다.
그 중에서도 Red-Black Tree 는 자료집합의 연산에 대해서 최악의 경우 O ( log N ) 의 성능을 보장하게끔
균형을 잡아놓은 효율적인 검색 알고리즘 중 하나입니다.

- AVL Tree 란? : Adelson, Velskii, Landis 라는 세 연구가에 의해 소개된 알고리즘.
                        각 노드에 'Balance Factor' 를 주고, 이 값에 의거해 Tree 를 재조직하는 기법이다. -

다음은 Red-Black Tree 의 기본 구성방법입니다.
한국어로 된 책을 여러권 읽어봤지만, 내용이 너무 애매해서 -_-;;
'Introduction to Algorithms'
 의 원문을 싣습니다.

1. Every node is either red or black.
     모든 node 는 적색 혹은 흑색이다.

2. The root is black.
     root 는 흑색이다.

3. Every leaf is black.
     모든 leaf 는 흑색이다.

4. If a node is red, then both its children are black.
     만약 한 node 가 적색이라면, 이 node 의 두 자식은 모두 흑색이다.

5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.
     각 node 로부터, node 에서 자손까지의 모든 경로들은 같은 갯수의 흑색 node 를 포함한다(가진다).

- by Introduction to Algorithms, 2th,  MIT press.

저 중,

 '5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.'

에서부터 Black-height 라는 용어가 나옵니다.

즉, root node 에서부터 각 leaf node 까지의 경로에서, Black node 의 갯수는 모두 동일하다는 의미지요.
따라서, 한 개의 Red-Black Tree 에서 Black-height 는 단 하나로 정의할 수 있습니다.

그리고, n 개의 internal-node 로 구성된 Red-Black Tree 는 기껏해야 최대 2 log (n + 1) 의 탐색 level 을 갖습니다.
또한 Red-Black Tree 내에서 root 로부터 leaf 로 가는 가장 긴 경로의 길이는 가장 짧은 경로의 길이의 최대 2배라는 것이
알려져 있습니다.
최대 2배이상 길어질 수 없다는 의미죠. -_-a
따라서, 기존의 알고리즘보다 훨씬 효율적이라 할 수 있습니다.




Red-Black Tree 에 대해선 설명할 것이 꽤 됩니다.
따라서 포스트를 몇개로 끊어야 할 것 같네요.
다음은 Red-Black Tree 의 회전. 삽입. 그리고 가능하다면 삭제 방법까지 포스팅해보기로 하죠.

그리고 Red-Black Tree 의 포스트가 끝나면 AVL Tree, Splay Tree 순서로 포스팅을 합니다.
posted by 비회원



Binary tree search 의 구현입니다.

시간에 쫓기면서 구현했심다 ㄱ-... 오류가 있을지도 모르겠네요.



덧)
소스코드의 설명은 주석을 달아놨으니 이해하실 수 있으리라 봅니다.
다음 포스트는 Red-Black tree 에 관한 것입니다만 -_-...

알아야 할 것들이 너무 많더군요. 더군다나 요새도 시간에 쫓기는 지라 오늘 포스팅하긴 무리일 것 같습니다.
따라서 Red-Black tree 포스트는 내일 오전중으로 올라가게 될 것 같네요. 죄송합니다.
posted by 비회원

테슬라 군이 트리 자료구조에 대한 일반적인 설명을 해 주었군요. -_-a
- Dlbo 군이 그렇게나 강조하는 테슬라 군과의 자료구조 포스팅 첫번째 연동입니다. -

트리 구조에 대한 일반론은 테슬라군이 이미 설명을 해 놓았으니 생략하겠습니다.
Binary Tree 는 트리 자료구조 중에서도 각 부모 노드가 자식 노드를 2개씩 가지는 자료구조를 말합니다.
Binary Tree Search 기법은 일반적으로 Binary Tree 의 일반적 특징을 따릅니다만,여기에 한 가지 조건이 더 붙죠.

그것은 각 노드에 저장되는 레코드의 값 순서가 ' Left < Root < Right ' 여야 한다는 것입니다.
일반적으로 Binary Tree Search 는 동적인 자료집합에 대해서 가장 효율적입니다.
값을 그냥 넣기만 하고 수정이 필요없는 경우들 - Static programming - 엔 'Linear Search' 나 'Binary Search' 가
훨씬 나은 선택이지만, 자료집합이 유동적 - 삽입, 삭제가 빈번한 경우 - 엔 Binary Tree Search를 다들 사용하는 편이죠.

자. 그럼 알고리즘 소개를 해 볼까요.
우선 Binary Tree Search 는 ' Left < Root < Right ' 의 순서로 레코드들을 조직한다는 전제를 기억해 두시기 바랍니다.


1. 최상위 루트 노드부터 검색해 들어간다.

2 - 1. 만약 찾고자 하는 값이 현재 노드의 값과 같다면 Find it.

2 - 2. 만약 찾고자 하는 값이 현재 노드의 값보다 작다면 -> Left node 순회, 다시 2 - 1 부터 재귀.
2 - 3. 만약 찾고자 하는 값이 현재 노드의 값보다 크다면 -> Right node 순회, 다시 2 - 1 부터 재귀.
         - 전제조건에서 Left < Root < Right 이므로, inorder tree walk 를 하는 편이 효율적이다. -

2 - 4. 만약 현재 노드의 값이 NULL 이라면 Can't find it.
         - 현재 탐색 위치가 Binary Tree 의 leaf, 즉 레코드의 끝이므로. -



일반적으로, Binary Tree Search 알고리즘의 수행시간은 O( log N ) 입니다. 하지만, 만약 Binary Tree가
테슬라군의 포스트처럼 사향 트리의 꼴을 취할 경우, O( N ) 의 시간이 걸립니다.
- 즉 n 개의 선형 자료 집합의 경우겠죠. -

그렇지만, 일반적으로 이런 일이 생길 경우는 드물기에 O( log N ) 의 수행 효율을 가진다고들 말하죠.
특히 Balanced Binary Tree 에 대해서는 O( 2진로그 N ) 의 효율을 자랑합니다.
이런 수치가 나타나는 이유는 Tree 의 높이에 따라서 검색 시간이 좌우되기 때문이죠.

또 하나의 보너스.

앞서 알려드렸다시피 Binary Search Tree 는 동적 연산을 지원하는 Dynamic programming 기법입니다.
이 때문에 사전이나 priority queue 의 구현에 잘 사용되기도 하죠.

이제 구현차례군요.
구현에 관련된 부분은 따로 포스트를 올려보겠습니다... 시간이 너무 오래 걸릴 것 같네요.

다음주 중에 Binary Tree Search 구현과 Red - Black Tree 에 대한 포스트가 올라갑니다.


덧*)
계속 늦어서 죄송합니다. -_-...
그리고 매번 포스트가 빈약한 것 같네요. 고쳐야 할텐데 -_-

그리고 저번 Binary Search 포스트에 대한 Dlbo 군의 태클, 잘 봤습니다.
태클을 했으니 그에 대한 증명이 있어야 겠죠? -_-a 포스트, 기대하겠습니다.
posted by 비회원

갑자기 일이 마구마구 들어오는 바람에 -_- 오늘내로 올리기는 힘들 듯 합니다. 내일 중으로 올라갑니다.

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

죄송합니다. -_-;;;; 조금 더 쉴게요.  (0) 2010.03.04
Reuent 포스트 연기.  (0) 2010.03.04
12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
Reuent 포스트 연기 공지.  (0) 2010.03.04
posted by 비회원

이번 주제는 Binary Search. 즉, 이분 검색입니다.

왜 'Binary' 라는 표현이 나왔는지 궁금하실텐데요, 이는 검색 방식 때문입니다.

앞서 작성한 'Quick Sort' 알고리즘에서 'Divide and Conquer' 와 'Three of median' 기법을 설명 드렸을겁니다.
Binary Search 알고리즘은 이 기법들을 동시에 사용합니다.
단, 전제 조건은 '이미 정렬된 레코드' 에서 사용해야 한다는 전제조건이 붙죠.

그럼 알고리즘 소개를 해 볼까요.


1.  이 레코드의 중앙값을 찾는다. - 이미 정렬된 레코드라 가정한다. -

2. . 만약 찾을 key 값이 이미 찾아놓은 레코드의 중앙값과 같다면 Find it.

3. 먄약 찾지 못했다면
    3 - 1.              key 값보다 중앙값이 작은 경우, 탐색 범위의 최대치를 중앙값으로 선택.
    3 - 1 - 1.         반으로 줄어든 구간에 대한 중앙값을 찾는다.
    3 - 1 - 2 - 1.    만약 중앙값과 key 값이 같다면 Find it.
    3 - 1 - 2 - 2.    찾지 못했다면 3 으로 되돌아간다.

    3 - 2.              key 값보다 중앙값이 큰 경우, 탐색 범위의 최소치를 중앙값으로 선택.
    3 - 2 - 1.         반으로 줄어든 구간에 대한 중앙값을 찾는다.
    3 - 2 - 2 - 1.    만약 중앙값과 key 값이 같다면 Find it.
    3 - 2 - 2 - 2.    찾지 못했다면 3 으로 되돌아간다.

4. 탐색 범위가 0 이 된다면 Can't find it.

알고리즘을 수행할 수록 탐색 범위가 반으로 줄어들고, 줄어든 범위에 대해서 다시 같은 알고리즘을 재귀적으로
수행합니다. - 분할정복 -
그리고 중앙값을 찾기 위해 탐색 범위의 Min 값과 Max 값의 중간값을 선택합니다. - 중위법 -

-_-ㅋ 매우 간단한 알고리즘입니다.
하지만 굉장히 효율적이라 이미 라이브러리 함수로 내장되어 있기도 하죠.
O( N log N ) 의 효율을 자랑하는, 가장 대표적인 탐색법 중 하나입니다.
코드로 구현해 볼까요.



물론 미리 레코드를 정렬해야 한다는 번거로움이 있긴 합니다.
하지만 Quick Sort 후 Binary Search 를 하는 것은 매우 효율적인 코딩 기법 중 하나라고 생각합니다.

둘 모두 O( N log N ) 의 효을 보장해 주고, 코딩 역시 간단하므로 괜히 복잡하게 Tree 구조를 이용하는
다른 방법을 사용하기 보단 이런 방식을 사용하는 것이 훨씬 경제적이겠지요.
posted by 비회원

매번 연기하는 것 같군요. 크흠 ㅡ,.ㅡ 다음주에 전과목 시험이 모두 몰려있어서... 12/5일 포스팅과 12/12일 포스팅은 불가능할 것 같습니다.

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

Reuent 포스트 연기.  (0) 2010.03.04
12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
Reuent 포스트 연기 공지.  (0) 2010.03.04
9 / 29.  (0) 2010.03.04
posted by 비회원

쫌 많이 늦었군요... 죄송합니다 -_-a;
H 대학교 친구한테 C 언어 알려주느라 어제 늦게 들어왔습니다. 매번 공지도 없이 늦네요 orz.

여튼.. 각설하고.

이번 주제는 Sequential Search - 순차검색 - 입니다.
혹자는 Linear Search - 선형 검색 - 이라는 표현도 쓰기도 합니다. 이는 알고리즘의 특성때문에 나온 말이죠.
- 사실 알고리즘이라 하기 좀 민망하긴 합니다. -_-;;;;; -

Sequential Search 라는게 사실 별 것 아닙니다.
말 그대로 찾으려는 자료를 소스에서 처음부터 순차적으로 계속 검색해 나가는 거죠.
가령.

S T U D Y I N G T H E L O G I C A L W O R L D

로 초기화되어 있는 기준 배열 input 에서 W 라는 문자를 찾으려 한다고 칩시다.
그러면 input[0] 부터 배열의 끝까지 계속 indexing 을 합니다.
흠... input[18] 에 W 가 있군요.
그렇다면 18 번째 인덱스에 W 값이 있다고 생각할 수 있죠.



간단하게 코드로 구현했습니다. -_-
- 구현할 것 까지 있긴 했나 싶긴 합니다만. -

코드 보시면 아시겠지만 N 개의 레코드에 대해서 최악의 경우에 N 번 검색을 합니다.
따라서 시간복잡도 상한은 O( N ) 이겠죠.

그리고 모든 검색 알고리즘에는 Delete / Insert 기능이 구현되어아 합니다.
Sequential Search 는 삽입에 대해서는 별로 생각할 것이 없습니다.
뒤에다가 그냥 끼워 붙이면 끝이니까요. -_-

하지만 특정 레코드를 삭제할 경우, 굉장히 귀찮은 상황이 발생합니다.
레코드 자체가 배열이기에 -_- 한 값을 지우면 뒤에 있는 다른 값들을 앞으로 당겨 줘야 하죠.
이 작업만 해도 평균적으로 선형시간을 소요합니다.

그래서 선택할 수 있는 방법이 Lazy Deletion 입니다.
삭제한 값에다가 보초값을 삽입하는 거죠.
그러면 검색할 때 굳이 다른 값들을 밀고 당길 필요가 없습니다. 이 보초값만 무시해버리면 끝이니까요.



-_-a...
저는 보초값을 보통 # 으로 잡는 편입니다.
- 사용자가 가장 입력을 안 하는 값이니까요 =_= -




여튼.. 이것으로 Sequential Search 포스트는 마치죠.
다음주 주제는 Binary Search - 이분 검색 - 입니다.
posted by 비회원

이제부터 포스팅해 나갈 주제는 Search algorithm 입니다.

Sort algorithm과 마찬가지로 거의 모든 프로그램 - 사실상 전부 -_- 라고 해 두죠 - 에서 필수적인 알고리즘 중 하나입니다.

Database 와의 연동이 없는 프로그램은 거의 없다고 해도 무방하기 때문이죠.
작게는 간단한 인원 관리 프로그램부터, 크게는 게임, OS, 그리고 서버에 이르기까지.

이런 거대한 자료 뭉치 - Database - 에서 원하는 자료를 찾아야 한다고 가정해 봅시다.
여러분들은 어떻게 하실 건가요?

.
.
.

이런 물음에 대한 답은 이미 여러가지가 나와 있습니다. 정렬과 함께, 학계에서 가장 많이 연구되어 왔고 또한 필요성 역시
가장 높은 알고리즘 주제중 하나이기 때문이죠.
- 그리고 아마 세계 어딘가에서는 지금 이 순간에도 이를 연구하고, 개량하고 있을 컴퓨터과학자들이 존재할겁니다. -

우선 지금까지 나온 여러 알고리즘을 단순히 나열해 보겠습니다.
사실 이름만 들어도 대부분 어떤 방식으로 구동하는지 아실 수 있을거라 생각합니다.


1. Sequential search (순차검색)

2. Binary search (이분검색)

3. Binary tree search (이진트리 검색)

4. Hashing (해쉬)



'아까 분명 여러가지라 하셨는데, 왜 이것밖에 없나요???' 라고 물으실 분들이 계실 것 같습니다.

사실, 저 Binary tree Search는 여러 범주로 세분화됩니다.
- Binary radix tree search, AVL tree, Red - Black tree, etc.... -
저 중에서도 특히 AVL tree 나 Red-Black tree 는 또 Balanced tree 의 일종이기도 하죠. 이들은 꽤나 어렵습니다. -_-;;;
- 갑자기 막막해지는군요. -

또한 저 Hashing 이라는 기법은 차라리 하나의 자료구조로 생각하는 것이 편할 정도인 독특한 알고리즘입니다.
- 최근의 자료구조 관련 책들은 대부분 이를 검색 알고리즘 파트에서 떼어내 자료구조로 취급하고 있습니다. -
하지만, 개인적으로 Hashing 기법은 자료구조라기 보다는 검색 알고리즘으로 취급하는 것이 좋다고 생각됩니다.

알고리즘이란 '어떤 문제에 대한 해결 방법' 을 뜻하는 말이지요.
그러나 자료구조에 대한 평가는 꽤나 엇갈릴 수 있습니다. 저는 자료구조란 '알고리즘을 정형화한 개발론의 일환.' 이라고
정의하고 싶네요 -_-a...
- 개인적인 견해이니, 이견이 있으시면 댓글로 달아주세요. 제 생각이 틀렸다면 겸허히 수용하겠습니다. -

또한 저 자료구조를 한꺼번에 묶어서 C++ 언어의 라이브러리로 제공된 것이 STL 입니다. generic programming의 대명사죠.
개발자들이 훨씬 편하게 자료구조를 사용하기 편하게끔 자체적으로 구현하여 제공되고 있는 라이브러리 입니다.

하지만, STL 에도 Hashing 은 직접적으로 포함되어 있지 않습니다. - 간접적으로 구현 가능합니다. 정식 표준엔 없죠.-
왜일까요?

여러가지 이유가 있을 수 있겠습니다만... 저는 Hashing 은 바로 '검색 전략' 이기 때문이라 꼽고 싶습니다.

나중에 할 이야기이지만, 빠르고 충돌 없는 Hashing 을 위해서는 사실 구현자가 key 와 hash function 을 잘 선택해야 합니다.

'사용자가 function을 구현한다.' 라는 이야기는 곧 '사용자가 해결 전략을 직접 선택한다.' 라고 할 수 있겠죠.
즉, 상황에 따라 다르게 구현해야 하므로 'generic programming 이라 할 수 없습니다.'
- 이는 qsort 에서 function을 사용자가 구현한 것과는 다른 의미입니다. 사용자는 그저 '오름차순' 인가 '내림차순' 인가를
선택했을 뿐이죠. 논점이 약간 다릅니다. -

따라서, Hashing 을 정형화된 방법론, 자료구조라고 생각하기는 힘듭니다.

그러므로 전 Hashing 을 검색 알고리즘에 넣고 이에 대해 포스팅을 진행할까 합니다.




흠... 이야기가 꽤나 멀리 돌아갔군요 -_-;;; 여튼.

앞으로는 매주 빠지지 않고 포스팅할 것을 약속드리며... 이만 마치죠 -_-a

다음부터 'Sequential search (순차검색)' 부터 포스팅합니다.
posted by 비회원

크흠. 드디어 쌓이고 밀린 일들이 다 끝났군요 -_- 힘들었습니다.

예상보다 2일정도 더 늦어졌는데요... 쩝.

오늘부로 복귀 신고합니다.

아마 포스트는 오늘 오후쯤에 올라갈 것 같네요 -_-ㅋ

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
Reuent 포스트 연기 공지.  (0) 2010.03.04
9 / 29.  (0) 2010.03.04
Reuent - 포스팅 계획서.  (0) 2010.03.04
posted by 비회원

학교 행사 관계로 오늘 포스트 업데이트가 늦을 것 같습니다.

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
Reuent 포스트 연기 공지.  (0) 2010.03.04
9 / 29.  (0) 2010.03.04
Reuent - 포스팅 계획서.  (0) 2010.03.04
posted by 비회원

이제 기본적인 정렬 알고리즘에 대한 포스팅이 끝났군요.

아직 포스팅 하지 않은 정렬 알고리즘이 꽤 있긴 합니다.
-Selection Sort, Shell Sort, Merge Sort, Counting Sort, Bucket Sort, External Sort -

하지만, 저 중 Selection Sort 를 제외한 나머지는 그다지 잘 사용되지 않는 알고리즘들이라 제외했습니다.
그리고 Selection Sort 역시 다시 언급할 필요는 못 느꼈었구요.
하지만 역시 원하시는 분들이 있다면 - 그리고 제가 끌린다면 - 따로 포스팅하죠. -_-a

흠... 그리고 자료구조 포스팅은 아무래도 제가 하지 않는 것이 나을 것 같네요.

다른 분에게 양도하겠습니다 -_-ㅋ

원하시는 분은 댓글 다셔서 가져가시구요.

다음은 Search algorithm 들에 대해서 포스팅하겠습니다.

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
Reuent 포스트 연기 공지.  (0) 2010.03.04
9 / 29.  (0) 2010.03.04
Reuent - 포스팅 계획서.  (0) 2010.03.04
posted by 비회원

이번엔 기수 정렬, Radix Sort 대해 알아보죠.

 Radix Sort 는 기본적으로 비트열을 정렬 대상으로 삼는 알고리즘입니다.

그래서 숫자 배열에 대해서는 매우 효율적인 알고리즘 중 하나입니다만, 문자 배열에 대해서는 탐색해야 할 비트열이 많아지므로
그다지 효율적인 선택이 아닙니다. 이 경우엔 다른 Sort 알고리즘을 선택하는걸 추천하죠.

우선 Radix Sort 는 두 가지로 나뉘어 집니다.

1. Radix Exchange Sort(기수 교환정렬)

2. Straight Radix Sort(직접 기수정렬)

흠... 그 중 Radix Exchange Sort 는 가장 직관적인 방법이라 할 수 있겠군요. 일상생활에서 우리가 가장 즐겨쓰는 방법입니다.

보통 인간은 10진법 체계를 사용합니다.

따라서, 각 자리수 별로 가장 큰 수는 9 이며, 가장 작은 수는 0 입니다.

그리고 우리가 수를 비교하는 방법은 다음과 같죠.

1. 몇 자리 수인지 비교한다.
   
2. 자리 수가 같다면 -> 그 자리 수의 크기를 비교한다. 이 경우 9 가 가장 크며, 0 이 가장 작다.

3. 자리 수의 크기가 같다면 -> 다음 자리 수로 넘어간다.

4. 큰 수가 결정될 때 까지 2 -> 3 번 알고리즘을 반복 수행.

5. 1번째 자리 까지 자리 수가 같다면 -> 같은 수이다.

-_-a 가장 익숙한 방법이죠?

그리고, 모두 아시다시피 컴퓨터는 몇 진법 수를 쥐어주든 2진수로 변환해서 값을 사용합니다.
2진 비트열의 제일 왼쪽 비트는 가장 큰 자리 수를 의미하죠. 그러므로 우리가 일상에서 이용하는 알고리즘을 적용할 수 있습니다.

따라서, Radix Exchange Sort의 구현은 두 가지 방법으로 생각해 볼 수 있겠죠.

1. 모든 입력값을 비트화 해서 왼쪽부터 탐색해 들어간다.

2. 굳이 비트화 할 필요 없이 자리수만 왼쪽부터 비교해 들어간다.
   - 정수 배열에 한해서 사용 가능한 방법. -

사실 컴퓨터 내부 구조를 생각하면 그게 그겁니다만... 2번째 방법으로 코드를 작성하면 훨씬 더 직관적으로 작성가능하겠죠.

하지만 기본적으로는 비트화하는 방법을 이용합니다.



두 번째로, Straight Radix Sort 입니다.

우선 Radix Exchange Sort 와의 차이점부터 설명해야 할까요.

Radix Exchange Sort 는 왼쪽부터 탐색해 들어간다고 말씀드렸을 겁니다.

하지만 Straight Radix Sort 는 오른쪽, 즉 비트열의 제일 끝부터 탐색합니다.
- 제일 작은 자리죠. -

"그렇다면 어떻게 정렬이 가능하지? " 라고 생각하실지도 모르겠군요.

하지만 이 경우에 한해서 사용가능한 아주 재미있는 알고리즘이 있습니다.

바로 Distribution Counting. 분포수 세기라고 번역되는 알고리즘이죠.

Distribution counting 을 위해선 먼저 입력받은 배열의 레코드를 쭉 검색해서 나타나는 값들의 빈도를 구해야 합니다.
- 배열을 사용하는 편이 간단하죠. -

그 이후 각 값들의 빈도에 대한 누적 합계를 구하고, 이를 기준으로 삼아 레코드를 정렬합니다.
- 이 경우, 누적 합계를 계산하기 위한 배열 - 빈도를 계산한 배열 - 은 모두 오름차순으로 정렬되어 있어야 합니다.
예를 들자면, 1 에 대한 빈도 , 2 에 대한 빈도, 3 에 대한 빈도, 4 에 대한 빈도, ........ n 에 대한 빈도.
이런 식이겠죠. -

단, 이 알고리즘의 경우는 출현하는 값의 분포가 클 수록 너무나 비효율적이 됩니다.
따라서 일반화시켜 사용하기엔 힘든 알고리즘이죠.

... 단, 지금 우리가 논의하는 주제에는 아주 안성맞춤이라 할 수 있습니다.

비트열은 Binary. 즉 1 과 0 의 조합입니다. 값의 분포수는 2 밖에 되지 않죠.

따라서, 정렬할 레코드들을 세로로 쭉 나열해 놓고 오른쪽부터 비트열을 Distribution counting 을 사용해서 정렬해 가는 것이
Straight Radix Sort 의 기본적인 방법론입니다.

하지만, 이렇게 복잡하게 비트화 시켜서, 또 Distribution counting 이라는 알고리즘까지 복합시켜서 정렬할 바에야 차라리
다른 정렬 알고리즘을 선택하는 게 최선이겠죠.
- 역시 비트열을 이용하는지라, 정수 배열에만 효율적이라는 한계도 작용하구요. 그나마도 레코드 수가 크면 적용이 힘들죠. -

그러나, Straight Radix Sort 를 사용하는 이유가 있습니다.
바로, Distribution counting 을 응용하면 '복합' 비트열에 대해서 정렬 연산이 가능하다는 거죠.

즉, 오른쪽 부터 비트열을 검색하되, 2 개, 4 개, 8 개, 16 개, ......

복합 비트열에 대한 동시 정렬이 가능합니다. 곧, 20개의 레코드를 동시 4개 비트열 동시 검색을 이용한 Straight Radix Sort 라면
단 5회만에 정렬이 가능하다는 거죠.



그럼 이제까지의 Radix Sort 를 정리해 볼까요.

1. Radix Exchange Sort.

- 우리가 일상 생활에서 사용하는 알고리즘을 이용한다.
  즉, 가장 큰 자리의 비트열 부터 비교, 검색하는 알고리즘이다.

- 가장 왼쪽 비트 (or 자리수) 부터 정렬 시작한다.

- 기본적으로 비트화 해서 정렬하나, 정수 배열에 한해서는 자리별로 끊어서 구현하는 방법도 생각해 볼 수 있다.


2. Straight Radix Sort.

- 오른쪽 비트부터 정렬시도한다.

- 기본적으로 Distribution Counting 기법을 이용하여 정렬한다.
 
- 복합 비트열에 대해서 Distribution Counting 기법으로 동시 검색이 가능하므로, 빠른 정렬 결과를 얻을 수 있다.


3. 단점

- 레코드의 갯수가 매우 크다면 비효율적이다.  - 비트열 검색을 이용하므로. -

- 더욱이 만약 정렬할 레코드가 문자 배열이라면 매우 비효율적.

- Straight Radix Sort 의 경우, 복합 비트열 검색을 이용할 수 있긴 하나, 그 경우 희생되는 메모리의 양은 무시못할 수준이라는
   것이 알려져 있다. 주의할것.
posted by 비회원

이번 주제는 Heap Sort 알고리즘입니다.

Heap Sort 를 알기 위해선 Heap 이란 자료구조에 대한 설명이 필요하겠군요.

Heap 은 일반적으로 완전 이진트리(Complete Binary Tree) 로 추상화됩니다.
- 포화 이진트리와 완전 이진트리의 차이점은 알고 계시리라 생각하겠습니다. -

우선 Max - heap 을 봅시다.
각 자식 노드와 부모 노드의 값을 비교할 때, 부모 노드의 값이 자식 노드들 보다 크게끔 완전 이진트리를 구현합니다.

그리고 재귀적으로 모든 서브 트리에 대해 위와 같은 정의를 적용해 주고, 그 이후 이 완전 이진트리를 level 별로 순회해 가면서
배열에 넣어주면 Max - heap 이 완성됩니다.
- 즉, 각 서브 트리 별 루트 노드의 값이 서브 트리의 레코드 중에서 가장 큰 레코드 값이 되도록 만들어 주면 됩니다. -
Min - heap은 가장 작은 레코드값이 루트에 있는 것이구요.

이제 Heap Sort 를 해 볼까요.

Max - heap 의 정의에서 Max - heap은 그  서브 트리 중 루트 노드가 가장 큰 레코드 값을 가진다고 되어 있습니다.

Heap Sort 를 위해선 필요한 작업이 두 가지 있습니다.

1. 루트 노드의 값을 빼서 기존 배열에 넣어 두는 것.
- Max -heap 을 이용한 오름차순 정렬의 경우는 루트 노드의 값을 역순으로 배열합니다. -

2. 루트 노드를 빼고 나서도 Heap(Max - heap 이든 Min - heap 이든) 의 특성을 무너뜨리지 않는 것.

저 중 두 번째. Heap 의 특성을 무너뜨리지 않는 것이 가장 중요합니다.
저것 때문에 코드가 꽤 복잡하게 나오는 경향이 있죠 -_-;

흠... 아마 호기심 많은 분들이라면 이런 말을 하실 수도 있겠습니다.
" 왜 배열을 이용하나요? 트리 구조의 구현은 링크드 리스트를 이용하던데. "

네. 좋은 질문입니다. ㅇ_ㅇ
일반적으로 트리 구조를 구현해 보면 Unbalanced tree 가 나오는 경우 - 그것도 심하게 -, 배열로 구현하게 되면
인덱스의 낭비가 너무 심하죠.
따라서 보통 Linked List 를 이용해서 구현하도록 학교, 또는 학원에서 가르칠 겁니다.

하지만 Heap 의 경우는 그럴 걱정이 없습니다.

아까 Heap 의 추상화 과정에서 말씀드렸을 겁니다. '완전 이진트리' 를 사용한다구요.

아시다시피 완전 이진트리는 균형잡힌 Balanced tree 입니다. 따라서 인덱스의 낭비를 걱정할 이유가 없죠.
그러므로, 골치아프게 Linked List를 이용하지 않고도 충분히 배열로 구현할 수가 있는겁니다.

자... 그러면 알고리즘을 정리해 봅시다.
n 개 레코드의 오름차순 정렬 알고리즘입니다.

1. Heap 을 생성한다.
- 일반적으로 Max - heap 을 생성한다.-

2. Heap 을 무너뜨리자.
- Heap 의 루트 노드를 빼서 기존 배열 - Heap - 의 가장 마지막 인덱스(n - 1)에 삽입한다. -

3. 빠진 루트 노드를 채워넣으면서 Heap 의 특성을 유지한다.

4. 다시 Heap 을 무너뜨린다.
- 빼낸 루트 노드를 뒤에서부터 역순으로 넣는다. (n - k) 인덱스 -

5. 4 -> 3 으로 알고리즘을 계속 수행한다.

6. 만약 (n - k) 가 0 이라면 -> 정렬 종료.
- Heap 이 완전히 소멸되었으므로. -

또 다른 질문이 있을 수 있겠습니다.
"어라? 왜 기존 배열에다가 빼낸 노드값을 넣어두나요? 충돌 생기지 않습니까?"

네. 결론적으로 말씀드리면...'안생깁니다.'

Heap을 구현한 배열의 경우, 인덱스 갯수는 n 개입니다.

하지만 Heap Sort 를 하기 위해서 필요한 과정이 있죠. 바로 'Heap 을 소멸시켜라.' 입니다.
따라서 루트 노드의 값을 빼 가면서 Heap을 무너뜨려 가는 것이죠.

저 과정에서 만약 Heap 의 루트 노드를 빼면, Heap 을 이루는 노드들의 갯수는 (n-1) 개 입니다.
따라서 Heap 의 최 말단 노드 바로 뒤에다가 빼낸 루트 노드 값을 넣어줘도 충돌이 생기지 않습니다.
딱 배열의 인덱스 갯수는 n 개를 만족하죠.
이해가 가시나요?

즉, 다시 설명드리자면 Heap 배열을 미리 빼낸 루트 노드값들이 뒤에서부터 점령해 들어 가는 겁니다.
그리고 루트 노드값들로 모든 Heap 배열 이 채워지면 이젠 Heap 이 완전히 소멸되면서 기존의 배열은 정렬된 배열이 되는 거죠.

그럼.. 다음은 코드 구현 차례. 입니다만 -_-;

기존 계획서에서 언급드렸다 시피 생략하겠습니다.
Quick Sort 처럼 구현을 원하시는 분이 계시다면 구현해 드리도록 하죠.
posted by 비회원

네. 저번주에 포스팅 하는 걸 잊었습니다.

... 그래서 이제부터 일주일 내내 하나씩 포스팅하기로 약속했습니다.
- Matrix 때문에 지금 Dlbo 군에게 열심히 갈굼당하고 있습니다. -_- 이건 그것도 겸한거죠. -

큼... 각설하고.

이번 포스팅 주제는 Quick Sort 알고리즘입니다.

정렬 알고리즘 중 가장 효율적이고 사용 빈도가 높은 알고리즘 중 하나입니다.
- C 언어 라이브러리 함수로 qsort() 라는게 있습니다. Quick Sort 를 라이브러리화 해 놓은 거라
  쉽게 사용이 가능합니다. 이것도 이유가 될 수 있겠죠. 비교 함수만 하나 더 만들어 주면 끝이거든요. -

흠... 일단 Quick Sort 를 소개하려면 'Divide and conquer' 라는 알고리즘 기법부터 설명해야 할까요.

'재귀' 라는 말은 한번쯤 들어 보셨겠죠?

쉽게 말해 자기 자신과 같은 일을 몇 번이고 계속 하는 구조를 일컬어 '재귀 구조' 라 합니다.

보통 '재귀'라 하면 재귀 함수를 생각하시는 분들이 많을 겁니다.

하지만, 여기서 말하고자 하는 재귀 구조는 '재귀 함수' 가 아닙니다.
- 물론, 우리가 Quick Sort를 구현할 때 재귀 함수를 쓰긴 합니다. -

단지 방법론적인 측면의 이야기를 하고 있죠.

즉, 주어진 문제를 해결하기 위해 전체의 큰 틀을 상정하고, 전체와 유사한 구조를 가지는 작은 틀들로
이 문제를  쪼갭니다.

그 후 재귀 구조를 이용, 이 작은 틀들을 기준으로 문제를 풀고, 다시 재결합하는 것이죠.

이 작은 틀은 전체 구조와 거의 유사한 구조를 가지고 있으므로, 이들을 '해결한다.' 라는 의미는
'전체 문제를 해결한다.' 라는 말과 같은 뜻이 될 겁니다.

이것이 분할 정복 - Divide and conquer - 기법이죠.

Quick Sort 알고리즘은 이 Divide and conquer 기법의 대표적인 예입니다.

자, 이제 알고리즘 소개를 해 볼까요.

1. 배열의 기준치를 잡는다.

2. 기준치를 중심으로 기준치보다 작은 수들은 왼쪽 배열에 대입한다.

3. 기준치를 중심으로 기준치보다 큰 수들은 오른쪽 배열에 대입한다.

4. 왼쪽 배열에 대해 1. 2 . 3 번 알고리즘을 계속 반복한다.

5. 더이상 바꿀 수가 없다면 오른쪽 배열에 대해 탐색한다.

6. 오른쪽 배열에 대해 1. 2. 3번 알고리즘을 반복한다.

7. 더이상 바꿀 수가 없다면. -> 정렬 종료.


한 눈에 보기에도 재귀 구조가 존재한다는 것을 알 수 있으실 겁니다.

알고리즘의 소개가 끝났으니, 소스 코드를 써 볼까요.

직접 구현을 할 수도 있겠지만, 일단은 라이브러리 함수를 사용하겠습니다.
혹시 Quick Sort 의 구현을 보고 싶으시다면 알려주세요.



이제까지처럼 10개의 레코드를 정렬하는코드입니다.

qsort 함수의 호출을 위해서는 인자 4개를 넘겨줘야 합니다. 순서대로 나열하죠.

qsort 라이브러리 함수.

- 포함 헤더파일.

stdlib.h


- 호출인자.

1.정렬할 배열.

2. 정렬할 배열의 크기.

3. 정렬할 배열의 데이터 크기.
- sizeof 함수를 이용합시다. -

4. 비교함수 식별자.
-사용자가 만들어 줍니다. 만약 위 코드와 달리 내림차순 정렬을 하고 싶다면 다음과 같이 비교함수를 만들어 주시면 됩니다. -


이제 성능 분석입니다.

직접 구현을 해 보면 아시겠지만, Quick Sort 는 기준치를 어떻게 잡냐에 따라 성능이 차이가 납니다.

일반적으로 가장 최악의 성능을 가질 때는 기준치가 각 케이스별로 배열의 first index 이거나 last index 일 경우입니다.
이 경우 평균 O(N^2) 의 시간복잡도를 가지게 된다는 것이 알려져 있습니다.

물론 최악의 경우만 놓고 보면 앞서 언급했던 알고리즘들과 성능차가 크게 나지 않습니다.

하지만 라이브러리 함수는 세 값의 중위법 - Three of Median - 을 이용합니다.
- 세 값의 중위법이란 배열의 first index 와 last index, 그리고 이 값의 중간값인 (first + last) / 2 의 세 값을 이용한 기법이죠. -
이 경우엔 분할이 거의 중앙에서 이루어지므로 재귀의 깊이가 대폭 줄어들게 됩니다.
평균적으로 O(N * log N)  의 시간복잡도를 갖게 되죠.

그러므로, 일반적으로 Quick Sort, 특히 라이브러리 함수를 이용하게 되면 시간복잡도 상한 O(N * log N)의
시간 안에 효율적으로 정렬을 할 수 있다는 것을 알 수 있습니다.
posted by 비회원

이번은 거품정렬 . Bubble Sort에 대해서 알아보죠.

간단히 말해, 이런 이름이 붙은 이유는 정렬과정의 모양 때문입니다. 한 레코드와 인접한 index들을 비교해 가장 큰 레코드 값이
한 칸 한 칸씩 옆으로 밀려나가는 모습이 마치 거품모양과 같다 하여 이런 이름이 붙었다. .... 고 합니다. -_-;;;;;;;
- 전 그렇게 못 느끼겠습니다만. 제 상상력이 부족한 건가요????-

last index 가 n 인 문자열 배열 a 가 있다고 가정합시다.

이 문자열을 Alphabet order 로 Bubble Sort 를 써서 정렬하고자 한다면.


  1. 레코드 값을 비교하기 위해 레코드 쌍을 마련한다. -> 이 경우, 인접한 요소끼리 레코드 쌍을 만든다.

  2. 한 레코드 쌍의 첫번째와 두번째 요소를 비교한다. -> 만약 첫번째 레코드 값이 크다면, swap.

  3. 다음 레코드 쌍을 마련한다. -> 다음 레코드 쌍의 첫 번째 요소는 직전 레코드 쌍의 두번째 요소.

  4. 우선 n 개의 레코드 쌍을 검사하도록 하자.

  5. 모든 레코드 쌍의 비교가 끝나면, 오름차순 정렬의 경우에 가장 큰 레코드 값이 배열의 마지막에
    대입되어 있을 것이다. -> a[n-1] 이 최대값.

  6. n 이 1이 될 때 까지 위 알고리즘을 반복한다. -> 이 경우 마지막엔 단 1 개의 레코드 값만 남게 될 것이다.

  7. 정렬 종료.


아주 간단합니다 -_-;
- 대체 이게 왜 거품인가요. -

직관적으로 느끼셨겠지만, Insertion Sort 와 거의 유사한 특성을 지닌다고 할수 있겠죠.

즉, 변수의 비교 횟수가 교환 횟수보다 압도적으로 적습니다.

단, 차이점이라면 Insertion Sort 는 서로 멀리 떨어진 값들을 교환하는 것에 반해, Bubble Sort 는 인접한 값을 교환합니다.

따라서, Insertion Sort 보다 정렬의 안정성이 높다고 할수 있겠죠.

이까지가 알고리즘 설명입니다.

그럼 코드로 구현해 보죠.



10개의 레코드를 정렬하는 예제입니다.

Insertion Sort 의 구현과 마찬가지로 C 언어를 이용했고, XOR 연산을 이용해 변수를  swap 했습니다.

자. 이걸 더 개선할 수 있을까요?

- 가능합니다.

Bubble Sort 는 레코드들의 교환 횟수가 매우 많습니다.

따라서, 일반적으로 알고리즘 시간 복잡도 상한은 O(N^2) 입니다.

하지만, O(N) 의 시간안에 Bubble Sort 가 수행될 수 있는 경우가 있습니다. 언제일까요?

 바로 이미 정렬된 배열의 경우입니다.

- 이 경우, Bubble 'Sort' 라는 말을 쓰기가 굉장히 민망하죠? -_-; -

아무튼. 이미 정렬된 배열의 경우엔 굳이 swap 할 이유가 없겠죠?

그럼 이 경우를 체크해서 이 코드를 조금 더 개선해 보도록 할까요.






is_sorted 변수를 이용, 조건검사를 실행합니다.

따라서, 배열이 이미 정렬되어 있다면, 시간 복잡도의 상한은 O(N) 이 되겠죠.
- 당연히 내부 루프의 효율만을 따지게 될 테니까요. -



이것으로 Bubble Sort 알고리즘을 마치겠습니다. ㅇ_ㅇ
posted by 비회원

흠. 두 번째 포스트군요 ㅇ_ㅇ.

이번 포스트는 앞서 언급했던 정렬 알고리즘들을 세분화하고 그 특징. 그리고 구현법에 대해 알아보죠.

우선, 가장 간단한 것부터 알아보도록 할까요. 우선 삽입 정렬(Insertion Sort)입니다.

삽입 정렬 알고리즘은 보통 카드 게임에서 카드를 정렬하는 것으로 비유하고 있습니다.

카드 몇 장을 이미 받았다고 가정하고, 카드 덱(Card deck) 에서 카드 한 장을 뽑아 손에 쥐어 봅시다.
그리고 나서 무늬에 관계없이 카드를 정렬하려 한다고 가정합시다. 여러분들은 어떻게 하시나요?

일반적으로, 이미 카드 몇 장을 받은 시점에서 카드를 정렬할 겁니다. 우선 처음 두 장을 비교하고, 값 순서대로 배열하겠죠.
그리고 나서 아마 '이미 정렬된' 두 장의 값 범위를 비교하고 나서 - 좌, 우 카드값의 비교겠죠 -  다음 카드를 그 두 장 사이에
'삽입' 했을 겁니다.

이를 반복하면, 결국 손에 쥐고 있던 카드들은 모두 다 정렬되어 있겠죠. 자, 이제 카드 덱에서 뽑은 카드를 어떻게 정렬할까요?
마찬가지겠죠. 이 카드는 '이미 정렬된' 카드 뭉치들의 좌, 우 값들을 비교하고, 그 사이에 '삽입' 할 겁니다.

이제 왜 삽입 정렬(Insertion Sort) 인지 아시겠나요?

이 Insertion Sort 알고리즘은 이런 '이미 정렬된' 부분에 '새로운 키(key) 값'을 삽입합니다. 그러고 나면, 결국 모든 부분은
완벽히 정렬이 되어 있겠죠.

즉, Insertion Sort 알고리즘은 값의 비교는 그렇게 많게는 하지 않습니다. - 좌 , 우 값 비교 뿐이죠. -
단, 새로운 값이 이미 정렬된 부분 사이에 삽입되므로 값의 교환 횟수는 증가하겠죠.

따라서, 입력된 자료의 정렬도에 따라서 효율이 달라질 수 있다고 할 수 있겠습니다.

만약 완벽히 정렬된 배열이라면 교환은 한 회도 발생하지 않습니다. 값의 비교에만 시간이 소요되겠죠.
일부만 정렬되어 있더라도 Inserton Sort 는 좋은 효과를 기대할 수 있습니다. 교환 횟수가 줄어드니까요.
하지만, 역순 정렬의 경우에는 최악의 경우가 발생합니다. 비교 보다 교환이 월등히 많기 때문이죠. 모든 값들을 교환해야 한다는
부담이 존재합니다.
더욱이 큰 레코드의, 거의 정렬되지 않은 자료형에 Insertion Sort를 시도할 경우, 교환 횟수가 매우 커지게 될 겁니다.

- 이런 경우엔 일반적으로 Quick Sort 가 해법입니다. -_-; 물론 다른 방식을 시도하면 훨씬 시간을 단축시킬 수 있긴 하죠. -

자, 이제  Insertion Sort 알고리즘의 특징을 정리해 볼까요.



    1. 자료의 정렬 정도에 민감하다 .
        -> 일부 정렬된 작은 레코드의 자료형에 대해서는 최적의 선택일 수 있다.
            그러나, 역순 정렬된 레코드에 대해서는 교환 횟수가 증가하므로, 최악의 선택이다.
            반드시 다른 정렬 알고리즘을 선택할 것.

    2. 레코드의 크기에도 영향을 크게 받는다.
        -> 물론 모든 정렬 알고리즘은 레코드의 크기에 영향을 받는다.
           그러나, Insertion Sort 처럼 교환 횟수가 큰 정렬 알고리즘의 경우에 이 영향력은 매우 커질 수 있다.




다음으로, Insertion Sort의 코드를 작성해 보았습니다. 간단한 알고리즘이니, C 코드로 구현했죠.



10개의 레코드를 받아서 정렬하는 코드입니다.

교환부는... 물론 temp 변수를 하나 만들어서 swap 형식으로 해도 됩니다만, 저런 방식으로 XOR 연산자를
이용하시면 조금이나마 더 빠른 정렬 결과를 얻을 수 있지요. -_-a

코드를 보시면 아시겠지만, for 문이 중첩되어 있습니다. 따라서, 일반적으로 O(N^2) 의 성능을 가집니다.

도움이 되셨나요? ㅇ_ㅇ;
posted by 비회원

흠... 자료구조 포스팅을 먼저 한다는걸 잊고 알고리즘부터 준비했군요 -_-;;;; 정렬 알고리즘들의 포스팅이 끝난 다음엔
기초 자료구조부터 시작하죠.
- ... 포스트 제목을 정말 거창하게 지어버렸네요 -_-;; -

여튼. 이번 포스팅 주제는, Sort algorithm. 즉 정렬 알고리즘입니다.

어떤 작업을 하든지 우린 '정렬작업' 이라는걸 해야하는 경우가 많습니다.

사실 우리 주위엔 정보를 정렬하는 것이 필수적인 분야들이 많습니다. 가장 대표적인 예를 들자면 고객 관리 프로그램이겠죠.
특히 중, 고등학생들의 정보를 관리하는 학생 정보 관리 시스템이라던가.

자. 물론 자료 입력시 정렬을 해서 넣는 경우도 있겠죠. 하지만 우리가 프로그래밍을 할 땐, 우리의 고객이나 서버 채점기는
'정렬을 하지 않고 자료를 입력한다.' 는 가정 하에 시작해야 합니다. 만약 그렇지 않다면... 큰 사단이 나겠죠? -_-;;;

생각을 해 봅시다. 대한민국의 수많은 중. 고등학생들의 학생정보가 정렬 없이 너저분하게 널려있는 모습을. 그리고 그 안에서
우리의 선생님이 내 이름을 찾으려 낑낑대는 모습을.

눈물나겠죠? -_-;;;
- 사실 가장 좋은 방법은 위에서 이미 언급했듯이 정렬을 하면서 모든 자료를 넣는 겁니다만... -_- 쉽지 않겠죠. -

여튼. 이쯤 하면 정렬 알고리즘의 필요성은 충분히 아시리라 생각합니다.  물론 사족이었을지도 모르겠지만, 어쨌든 현대사회에서
정보 정렬의 필요성은 충분히 숙지하고 있어야 한다고 생각해 한번 더 다들 아실 내용을 이야기 해 봤습니다.

그럼 본격적으로 시작할까요.

기본적으로 정렬 알고리즘은 앞서 언급한 대로 정보 정렬의 필요성이 크게 심화됨에 따라 오랫동안 연구되어 왔고, 그에 따라
많은 종류의 알고리즘들이 등장했습니다.

한 알고리즘 A 가 소개되면 이를 더 빠르고 안정성있게 정렬하는 B가 등장하고, 또 이를 개선한 C가 등장하고. ....

그럼 지금까지 소개된 정렬 알고리즘의 종류들은 어떤 것들이 있을까요?  일단 간단한 것 부터 단순히 나열해 보죠.



  1. 선택 정렬 (Selection Sort)

  2. 삽입 정렬(Insertion Sort)

  3. 거품 정렬(Bubble Sort)

  4. 쉘 정렬(Shell Sort)

  5. 퀵 정렬(Quick Sort)

  6. 병합 정렬(Merge Sort)

  7. 기수 정렬(Radix Sort)

  8. 힙 정렬(Heap Sort)




가장 간단히 나열하자면 8개 정도로 줄일 수 있겠죠.

물론 이 중 가장 보편적인 상황에서 쓰이는 알고리즘은 Quick Sort 입니다. 일반적으로 속도도 빠르고, 구현도 간편하니까요.
- C언어 레퍼런스 함수로 qsort() 라는 것이 있습니다. 직접 구현할 필요가 없죠. -

하지만, 모든 상황에서 Quick Sort가 가장 빠르고, 정확한 대안이 되는 것은 아닙니다.

차후에 더 언급하겠지만, 메모리를 희생할 수만 있다면 Radix Sort 알고리즘 중에서도 '직접 기수 정렬(Straight Radix Sort)' 을
이용해 자료를 정렬하는 것이 더 빠른 경우가 있습니다.
- Radix Sort는 스택에 입력된 자료들을 비트열로 쪼갠 뒤에 비트를 가지고 정렬을 하므로, 입력 자료에 무관하게 같은 개수의
  자료라면 매우 빠른 정렬 결과를 산출할 수 있다고 알려져 있습니다. -

이처럼 상황에 따라서 선택해야 하는 알고리즘이 바뀔 수 있습니다.

프로그래밍 언어와 컴파일러는 프로그래머의 실수로 인해 빚어진 상황에 대해서는 전혀 책임을 지지 않습니다.

모든 상황에 대한 책임은 자료구조와 알고리즘을 선택한 프로그래머에게 있습니다.

잘못된 알고리즘을 사용해서 피본 경우는 모두 한번씩 있겠죠. 물론 저도 마찬가지구요.

프로그래밍을 할 땐 자료구조와 알고리즘의 이해도, 그리고 상황에 맞는 선택이 프로그램의 성능을 좌우합니다.

모두들 제 포스트를 통해서 - 그리고 다른 분들의 포스트를 통해서 - 함께 알고리즘들에 대해 고찰해보고, 한번 더 생각하는
계기를 갖게 되었으면 하면서 일단 이번 포스트를 마칩니다.

다음엔 위에서 언급한 - 그리고 아직 언급하지 않은 - 알고리즘들을 자세히 분석해 보고, 그 구현법에 대해 논하도록 하죠.

지금까지 읽어주셔서 대단히 감사합니다 -ㅁ-.

posted by 비회원

흠... 안녕하십니까. Reuent 라고 합니다.

독음이 궁금하시면 '로이엔트'라 읽어주세요 -_-. 독일어의 독음을 따르시면 됩니다.
- 아이디에 얽힌 비화는 제 블로그를 참조해 주시길... -

일단 이 팀의 팀블로그 관리자 -_- 를 맡고 있구요, 건의사항 등등이 있으시면 연락주시면 빠른 시간 내에
조치를 취하겠습니다.

소개는 이정도로 하고... 본론으로 들어가지요.

앞으로 제가 포스팅 할 부분은 자료구조와 알고리즘 분야입니다.

우선 기본적인 자료구조의 정의와 그 구현법을 중심으로 전개해 나갑니다. 그러나 큰 비중을 두진 않고,
단지 한번 더 기본기를 다진다는 느낌으로 합니다.

그 이후는 알고리즘을 각 카테고리별로 묶어서 포스팅합니다. 물론 그 구현법도 씁니다.

단지, 자료구조나 알고리즘이나... C언어로 구현하기엔 꽤나 까다롭습니다. 코드 리딩만 해도 시간이 꽤
걸릴테구요 -_-a

그리고 문제풀이 및 실무에서 C++의 STL 등을 쓰지 않고 몇백 줄이나 되는 자료구조들을
일일히 코딩하시는 분은 아마 드물겠죠. - 없다고 확신합니다. -

따라서, 코드를 직접 제공하진 않습니다. 단지 'C언어로 이러저러하게 구현할 수 있다.' 정도로만 소개합니다.

아마도 복잡한 알고리즘과 자료구조의 구현은 C++의 STL 을, 비교적 간단한 것들은 C언어를 사용하게 될 것
같네요. 물론 C언어로 구현하는 경우에도 C언어 자체 제공 레퍼런스가 있다면 그 사용법을 씁니다.

그리고, 여력이 된다면 컴퓨터 내부 구조론에 대해서도 어셈블리 다시 공부해 가면서 포스팅할 계획도
갖고 있습니다만... 아마 두고 봐야 알겠지요? -_-a...

참. 추가적으로 PKU나 UVa 주당 1회정도 문제 번역작업도 개시하구요.



뭐... 일단 제가 맡은 부분은 여기까집니다.

앞으로 열심히, 잘 해봅시다 -_-!

'(탈퇴) Reuent's Post > Notice' 카테고리의 다른 글

12 / 26 Reuent 포스트 연기.  (0) 2010.03.04
Reuent 연기공지. -_-  (0) 2010.03.04
복귀신고 -_-  (0) 2010.03.04
Reuent 포스트 연기 공지.  (0) 2010.03.04
9 / 29.  (0) 2010.03.04
Reuent - 포스팅 계획서.  (0) 2010.03.04
posted by 비회원
prev 1 next