데이터 검색 하기 - 코딩수업#10
정렬과 검색
대용량 자료를 순서대로 놓고(정렬), 이 중 특정 자료를 찾는(검색)것은 컴퓨터가 처리하는 가장 중요한 두 가지 일이다.
앞서 6개의 로또 숫자를 순서대로 놓는 법을 배웠고, 이를 기반으로 수천, 수만 개의 자료를 순서대로 정렬하는 것도 가능하다는 것을 배웠다.
이번에는 이렇게 순서대로 놓인 자료들 중 특정 자료가 어느 위치에 있는지를 찾는 방법, 즉 검색에 대해 이야기해 보겠다.
컴퓨터 전공자들이 문제를 푸는 방법 즉 알고리즘에 대하여 배울 때 가장 중요한 과목이 바로 "자료 구조론"(Data Structure)이고, 그 과목에서 주로 다루는 이야기는 자료들을 어떻게 늘어놓을 것인가에 대한 것들이다. 자료를 잘 늘어놓아야 찾아보기 쉽기 때문이다.
그러니까 앞서 공부한 정렬은 검색을 위한 수단이 된다.
물론 순서대로 자료를 늘어놓는 것만이 검색의 최선이 아니지만, 아직은 그냥 머릿속으로 그림을 그려가기 쉬운 방법으로 문제를 풀어보자.
사전의 검색
그렇다면 가장 쉽게 볼 수 있는 정렬된 자료는 과연 무엇이 있을까?
바로 사전이다.
영문 사전이라면 "a"에서 "z"까지의 인덱스에 따라 단어들이 정렬되어 있을 것이고,
국어사전이라면 "ㄱ"부터 "ㅎ"까지의 인덱스에 따라 단어들이 정렬되어 있을 것이다.
학교에서 배웠던 사전 찾는 방법을 되새겨 보자.
예를 들어 "save"라는 단어를 찾아 보자. (페이지에 표시된 인덱스 마크는 무시한다.)
1. 처음 사전의 중간 부분을 열었더니
"node"
라는 단어가 나왔다. "save"는 "node"보다 뒤에 나오는 단어이므로 "node" 이후의 중간쯤 페이지를 열어서 찾아야 한다.
2. 이번에는
"that"
이 나왔다. "save"는 그 앞이다. 이제는 "node"와 "that" 중간쯤을 열어보자.
3. 이번에는
"rode"
가 나왔다. "save"는 그 뒤쪽이므로 "rode"와 "that" 사이를 열어보자.
4. 이번에는
"sea"
가 나왔다. "rode"와 "sea" 사이를 열어보자
5. 이번에는
"safe"
가 나왔다.
동일한 요령으로 "sauce" -> "scale" ------------등등의 과정을 거쳐서.
6. 마지막으로
"save"
를 찾게 된다.
물론 사전 책에서 데이터를 찾을 때는 한 개의 단어만을 만나는 것이 아니고 전체 페이지를 만나지만, 이론상 내가 찾는 단어가 현재 페이지보다 앞인지 뒤이은 지를 따져서 조금씩 그 검색 범위를 좁히는 것이다.
이런 방법으로 검색에 관한 코딩을 해보자.
검색 코딩
15개의 단어가 아래와 같이 사전 순서로 놓여있다고 하자.
abc, and, date, end, month, node, orange, rode, safe, save, sea, that, this, ultra, zoo
여기서 save를 찾는 프로그램을 만들어 보자.
var srch_word = "save";
var dic=["abc", "and", "date", "end", "month",
"node", "orange", "rode", "safe", "save",
"sea", "that", "this", "ultra", "zoo"];
function search(st_no, en_no, srch_word){
document.writeln(st_no+"-"+ en_no) // 검색을 시작하는 부분과 끝나는 부분의 번호를 보여준다.
if (st_no>en_no) return -1; //만일 단어를 못 찾게 되면 단어가 없음을 알린다.
var sno=Math.round((st_no+en_no)/2); // 검색의 시작과 끝의 중간 부분 단어의 번호를 찾는다.
if (dic[sno]==srch_word) return sno; // 원하는 단어를 찾은 경우
else if (dic[sno]>srch_word) return search(st_no, sno-1, srch_word); // 검색의 시작을 지금 찾은 단어 (번호-1)부터로 조정하여 다시 찾는다.
else if (dic[sno]<srch_word) return search(sno+1, en_no, srch_word);// 검색의 끝을 지금 찾은 단어 (번호 + 1) 로 조정하여 다시 찾는다.
}
var found_no = search(0, 14, srch_word); // 0부터 14까지 15개 단어에서 찾는다.
if (found_no==-1) document.write("단어가 없습니다.");
else document.write(found_no+"-"+dic[found_no]); // 검색하려는 단어는 "save"이다.
사실 위의 검색 내용은 Function 에 대한 기본 지식과 재귀 호출이라고 하는 기법을 사용하여 만들어져서 기본 과정을 배우는 분들에게는 어려운 부분이겠지만, 생각의 방법에 대해서만 관심을 가지고 이해해 주길 바란다.
컴퓨터 프로그램이 수행하는 데이터 처리 중 가장 중요한 기능인 정렬과 검색에 대해 설명하기 위한 어쩔 수 없는 선택이었다.
저작 도구를 통하여 결과를 보자.
save가 9번째 자리에 놓여 있음을 보여준다.
save를 "sove"라고 수정하여 검색해 본 결과
"단어가 없습니다."라고 검색이 실패했음 을 보여준다.
이해가 어려운 분들께는 자세한 설명이 없었음에 미안하지만, 이러한 코딩의 기법을 소개하는 이유는 이렇게 간단한 프로그램 만으로 웬만한 자료를 검색하는데 문제가 없음을 알려주기 위함이었다.
10여 년 전 아이폰과 갤럭시폰이 나오기 시작했던 시절 발매되었던 모 출판사 전자사전 어플의 검색 부분을 내가 직접 만들었을 당시의 경험을 기반으로 이야기하는 것이고, 위의 코드와 별 차이 없는 코드로 수십만 표제어를 소비자가 느낄 수 없을 만큼의 시간에 검색해 냈었다.
물론 추가된 코드도 있었고, 검색에 도움이 되도록 데이터에 손을 대기도 하였지만, 기본 방식은 동일하다.
