[강의노트] 사전ADT를 이용한 선형탐색과 이진탐색 - 1

사전ADT를 이용한 선형탐색과 이진탐색 - 1

먼저 이전시간까지 다룬 정렬알고리즘들을 복습할 겸 정리해보고, 새로 배울 내용인 사전 ADT를 공부해보자.

 

비교정렬 알고리즘의 비교

정렬의 안정성

키-원소 항목들을 정렬할 때, 중요한 이슈는 동일 키를 어떻게 처리되느냐는 것.

동일키의 원래 순서를 보존해주는 것을 안정적인 알고리즘이라고 부른다.

 

쉽게 예시를 들면 학교에서 운동장으로 나와 한 줄로 서있으라고 방송을 한다면, 나온 순서에 맞게 줄에 서있을 것이다.

이때 키가 큰 순서대로 다시 줄을 서라고 했을때, 키가 같은 친구들은 원래의 순서에 맞게 줄을 서는것

 

  

그럼 지금까지 배운 정렬 알고리즘들 중에 안정성을 보장하는 알고리즘은 어떤 것이 있을까?

답은 선택정렬, 삽입정렬, 합병정렬이 안정적인 알고리즘이다

 

퀵 정렬은 분할과정에서 힙 정렬은 heapify 과정에서 안정성을 보장하지 않으므로 비 안정적인 알고리즘이다.

( 그 이유에 대해서 자세히 생각해보자 )

 

사전 ADT

이번에 공부할 내용은 사전 ADT 이다. 알고리즘을 공부하기전에 탐색에 대해서 매우 많이 접했었는데

사전 ADT를 사용해서 탐색작업을 하는거 같다.

중요한 내용이니 확실하게 공부하자 

사전 ADT 메소드

사전은 연락처 목록, 신용카드 사용승인, 인터넷주소 매핑 등에 활용될 수 있고

간접적으로는 알고리즘 수행을 위한 보조 데이터구조로 많이 활용된다.( 탐색 기능이 있으므로)

 

탐색

비공식적으로 탐색이란 데이터 집단으로부터 특정한 정보를 추출함을 말한다.

 

공식적으로는 (사전에 한정돼서는)탐색이란 사전으로 구현된 데이터집단으로부터 지정된 키와 연관된 데이터 원소를 반환하는 것을 말한다.

 

사전 구현에 따른 탐색기법인데 우리는 리스트를 이용한 무순사전 ADT와 순서사전 ADT에 대해서 다루게 될 것이다.

 

아직 트리와 해시테이블은 공부하지 않았기때문에 선형 탐색과 이진탐색 먼저 다뤄보자

 

무순사전 ADT : 기록파일

무순사전 ADT 는 기존 리스트에 새로운 원소가 삽입될 때, 맨 앞 또는 맨뒤에 삽입하면 되기때문에 O(1)의 시간이다.

리스트에 원소가 저장되는 기준이 없으므로, 탐색이나 삭제에서는 최악의 경우 O(n) 시간이 걸린다. ( 모든 항목을 다 순회해야하므로)

 

이런 무순사전 ADT가 효율적인 경우는 소규모의 사전이나, 서버의 로그인기록이 되겠다.

 

무순사전 ADT에서 어떤 원소를 탐색하려면 모든 원소를 탐색해야하는데, 이것을 선형탐색이라고 한다

알고리즘은 단순하다. 그냥 리스트를 순회하면서 key값을 확인하는 것

 

방금 말했듯이, 무순사전ADT에서의 선형탐색의 경우 찾으려는 데이터가 리스트에 없다면

모든 n개의 항목을 다 순회해야한다 .따라서 데이터가 리스트에없는경우가 최악의 경우가 되고 그때 시간은 O(n)

 

 

 

순서 사전 ADT : 일람표

이번엔 순서리스트를 사용해서 구현된 사전이다. 즉 무순사전ADT와 다르게 리스트에 존재하는 원소들이

key 를 기준으로 정렬되어 있는데 이 경우 탐색에 있어서 용이하다.

 

하지만 삽입하는 경우에 정렬기준에 맞는 위치에 삽입해야하므로 무순사전 ADT 에서는 O(1)이었지만 순서사전 ADT에서는 최악의 경우 O(n)시간이 필요하다.

삭제하는 경우도 마찬가지로, 항목이 삭제된 공간을 메꾸기 위해 최악의 경우 n개의 기존 항목들을 이동해야하므로

O(n)시간이 필요하다.

 

즉 순서사전은 탐색을 자주하는 경우에 사용하면 좋다. ( 신용카드 사용승인, 전화번호부 등)

 

순서사전에서의 탐색을 말한다. elseif 절이 추가되었는데 코드만 보아서는 바로 와닿지가 않는다.

도서관에서 책들이 번호로 라벨링 되어있다고 생각해보자. 1번에서 1000번까지 총 1000권의 책이 있는데

내가 찾고자하는 책이 150번이다. 이 경우 순서사전에서는 탐색을 하다가 151번이 되었다면, 더 이상 탐색을 할 필요가 없다. 다른 누군가가 150번 책을 대출해서 원하는 책이 리스트에 없기때문에 (뒤로 가도 실패가 예정되어있는 경우이기 때문이다.)

 

하지만 이렇게 탐색을 보완하더라도 O(n)시간인 것은 여전하다. ( 즉 elseif문을 추가해도 .. 정렬알고리즘 적인 면에서 효과가 미비하다.)

그래서 좀 더 효율적인 탐색 알고리즘을 생각하다가 나온것이 이진탐색

 

이진탐색

 

이진탐색의 알고리즘은 어떠한 배열이 있다고 할때, 그 배열의 가운데를 기준으로 크다 작다를 나누는 것이다.

 

즉 위에서 예로 든 1~1000권의 책이 있을때 내가 150번을 찾는다고 할 때,

절반에 해당하는 500번을 기준으로 150번은 더 작기때문에, 왼쪽 구간인 1~500 권만 보겠다는 것이다.

 

좀 더 쉽게 이해하려면, up down 게임을 생각해보면 된다. 우리가 보통 업다운 게임을 해서 숫자를 맞출때 무의식적으로 이진탐색 알고리즘을 사용하고 있다. 최대 숫자가 50일때 공격자는 처음 숫자로 25를 말한다. 절반을 기준으로 나누어야 가장 효과적으로 정답에 근접할 수 있는 것을 알기때문이다.

 

이진탐색은 이러한 과정을 재귀적으로 호출해서 구현하고 base case 즉 a~ b까지에 해당하는 범위가 엇갈린다면

탐색이 끝날때까지 원소가 리스트에 존재하지 않은것이기때문에 재귀가 종료된다.

 

수행예시를 통해 좀 더 확실하게 이해해보자.

 

 

순서가 있는 리스트에서 우리가 원하는 것은 7을 찾는것이다. (현재 5번 인덱스에 위치해있다.)

첫번째 시도에서 가운데 값인 8을 기준으로 잡고, 7이 가운데 값보다 작으므로 왼쪽 리스트들에 대해서만 탐색합니다.

 

두번째 시도에서 가운데 값인 3을 기준으로 잡고, 7이 3보다 크기때문에 오른쪽 리스트에 대해서만 탐색합니다.

 

. 

.

이러한 과정을 거쳐서 원하는 element와 L[mid] 가 같으면 종료합니다.

 

배열의 경우 한번에 반씩 쪼개기때문에 가장 최악의 경우 O(logn)이다.

근데 연결리스트의 경우는 가운데 위치로 접근하려하면 이미 O(n)시간이 필요하기때문에 이진탐색은 배열에서 자주 사용한다