Algorithm #2. Search algorithm. - 2.1 검색 알고리즘의 종류. ( & Algorithm vs. Data Structure (??) )

이제부터 포스팅해 나갈 주제는 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 (순차검색)' 부터 포스팅합니다.