본문 바로가기

(탈퇴) Reuent's Post/Algorithms

Algorithm #2. Search algorithm. - 2.2 Sequential Search.


쫌 많이 늦었군요... 죄송합니다 -_-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 - 이분 검색 - 입니다.