2장. 알고리즘이 중요한 까닭

Deah (김준희)·2024년 1월 26일

개발서적 알고리즘 자료구조

누구나 자료구조와 알고리즘 (개정2판)

목록 보기

2/15

들어가기 전에

알고리즘(Algorithm)이란?
알고리즘이란 단순히 어떤 과제를 완수하는 명령어의 집합일 뿐이다.

만약 우리가 시리얼을 먹는다면? 아래와 같은 순서로 시리얼을 먹게될 것이다.

그릇을 집는다.
그릇에 시리얼을 따른다.
그릇에 우유를 붓는다.
그릇에 숟가락을 넣는다.

👩🏻‍💻 그렇다면 컴퓨팅 관점에서 알고리즘이란 무엇일까?

컴퓨팅 관점에서 알고리즘은 특정 과제를 달성하기 위해 컴퓨터에 제공되는 명령어의 집합이다.
즉 어떤 코드를 작성하든 컴퓨터가 따르고 실행할 명령어들을 만드는 것이다.

2.1 정렬된 배열

정렬된 배열(Ordered Array)이란?
값이 항상 순서대로 정렬된 배열

정렬된 배열에 값을 삽입해야 할 때에는 '정렬'이라는 특성을 살리기 위해 새로운 값이 들어갈 적절한 위치를 찾는 것이 중요한 포인트다.

1️⃣ 새로운 값이 들어갈 위치를 찾는다.
2️⃣ 해당 위치 이후의 값들을 한 자리씩 이동시킨다.
3️⃣ 새로운 값을 삽입한다.

만약 아래와 같이 정렬된 배열에서 새로운 값 19 를 추가해야 할 때,

(1) 위치 찾기
0번째 인덱스부터 값을 확인하여 새로운 값과 비교해 올바른 위치를 찾는다. 19는 3보다 크기 때문에 0번째 인덱스 이후에 위치해야 하므로, 다음 인덱스인 1번째 인덱스 값을 확인하여 새로운 값과 비교한다. (반복)

3	12	21	34	55
0	1	2	3	4

(2) 자리 만들기
1번 과정을 통해 새로운 값 19는 12와 21 사이에 위치해야 한다는 것을 알았다. 그러므로 21부터 마지막 요소까지 한 자리씩 이동하여 12와 21 사이에 새로운 값이 들어갈 공간을 만들어 준다.

3	12		21	34	55
0	1	2	3	4	5

(3)새로운 값을 삽입한다.
2번 과정을 거쳐 만들어진 자리에 새로운 값 19를 삽입한다.

3	12	19	21	34	55
0	1	2	3	4	5

정렬된 배열에서 값을 삽입할 때에는 실제 삽입 전 검색을 먼저 수행하여 올바른 위치를 찾아야 한다. 이 과정에서 일반 배열과 성능 차이가 발생한다.

배열의 맨 앞에 데이터를 추가하고 싶은 경우에는 배열 내 모든 값을 전부 한 셀씩 이동해야 하므로, $N$ 개의 데이터를 가지고 있는 배열이 있다면 최대 $N$ 번의 단계가 필요하다.

정렬된 배열에서는 검색을 먼저 수행하므로 $N$ 개의 데이터를 가졌다는 가정 하에 $N + 2$ 단계가 소요된다. 만약 정렬된 배열의 가장 끝에 데이터를 추가하게 될 경우에는 $N + 1$ 단계가 소요된다.

2.2 정렬된 배열의 검색

원하는 값을 찾을 때까지 한 번에 하나의 셀을 확인하는 선형 검색(Linear Search)에서도 일반 배열과 정렬된 배열의 차이가 발생한다.

const arr = [54, 17, 3, 22, 202, 96];
const ordered_arr = [3, 17, 22, 54, 96, 202];

만약 위 코드와 같이 일반 배열과 정렬된 배열이 있을 때, 두 배열에서 각각 20라는 (존재하지 않는) 데이터를 찾고싶다면 arr 에서는 처음부터 끝까지 순회하며 값을 찾아야하는 반면에 ordered_arr 에서는 3번째 인덱스인 22에 도달했을 때 이후로는 더이상 20을 찾을 수 없으므로 순회를 중단할 수 있다.

이러한 관점에서 선형 검색은 일반 배열보다 정렬된 배열에서 검색했을 때 더 적은 실행 단계수를 가지지만, 만약 찾으려는 값이 가장 마지막 값이거나 그것보다 클 경우에는 일반 배열과 마찬가지로 모든 셀을 검색해야 한다.

그러나 정렬된 배열에서는 선형 검색뿐 아니라 다른 검색 알고리즘인 이진 검색(Binary Search)을 사용할 수 있고, 이 방법이 훨씬 빠르다.

2.3 이진 검색

이진 검색(Binary Search)란?
정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘
중간 값을 임의의 값으로 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교하는 검색 방법

조금 더 쉽게 풀어보면, 두 사람이 아래와 같이 게임을 한다고 생각해볼 수 있다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

👧🏻 : 1부터 10까지 수 중에 내가 생각하고 있는 수를 맞춰봐
👦🏻 : 5
👧🏻 : 그것보다는 커

[6, 7, 8, 9, 10]

👦🏻 : 8
👧🏻 : 그것보다는 작아

[6, 7]

👦🏻 : 6
👧🏻 : 그것보다는 커

[7]

👦🏻 : 7
👧🏻 : 딩동댕!

즉, 이진 검색이란 계속해서 중간 지점을 골라 남은 데이터 중 절반을 제거해 나가면서 요소를 찾는 검색 방법이다.

만약 아래와 같이 정렬된 배열에서 34를 찾으려고 할 때,

?	?	?	?	?	?	?	?	?
0	1	2	3	4	5	6	7	8

(1) 배열의 길이를 2로 나누어 가운데 셀의 인덱스에 접근하여 값을 확인한다.

?	?	?	?	21	?	?	?	?
0	1	2	3	4	5	6	7	8

(2) 찾으려는 값 34은 9보다 인덱스 크므로 인덱스 4를 기준으로 오른쪽 영역에 있다. (왼쪽 영역 제거)

X	X	X	X	21	?	?	?	?
0	1	2	3	4	5	6	7	8

(3) 9보다 오른쪽에 있는 값들 중 가운데 값을 확인한다. 찾은 값이 55이므로 34는 왼쪽에 위치하기 때문에 오른쪽 영역을 제거한다.

X	X	X	X	21	?	55	X	X
0	1	2	3	4	5	6	7	8

(4) 21과 55 사이에 남은 셀을 확인한다.
이 과정에서 남은 셀이 여러개라면 다시 중간 값을 확인한다.

X	X	X	X	21	34	55	X	X
0	1	2	3	4	5	6	7	8

코드로 구현한다면

찾으려는 값의 위치(index)를 찾는 이진 탐색 알고리즘을 자바스크립트 코드로 구현하면 다음과 같다.

function binarySearch(array, target) {
	let start = 0;
  	let end = array.length - 1;
  	let mid;
  
  	while (start <= end) {
      	// start, end의 가운데 지점
    	mid = parseInt((start + end) / 2);
      
      	// 가운데 값이 찾는 값이라면 반환
      	if (array[mid] === target) return mid;
      
      	// 가운데 값이 타겟보다 크면 타겟이 왼쪽 영역에 있으므로 end 범위 조정
      	// 가운데 값이 타켓보다 작으면 타겟이 오른쪽 영역에 있으므로 start 범위 조정
      	if (array[mid] > target) end = mid - 1;
      	else if (array[mid] < target) start = mid + 1
    }
  
  	// 찾으려는 값이 없을 경우 false 리턴 (경우에 따라 -1 리턴)
  	return false;
}

테스트

const arr = [54, 17, 3, 22, 202, 96];

// 배열을 오름차순으로 정렬
// [3, 17, 22, 54, 96, 202]
const ordered_arr = [...arr].sort((a, b) => a - b);

binarySearch(ordered_arr, 22);    // 2
binarySearch(ordered_arr, 202);   // 5
binarySearch(ordered_arr, 0);     // false

2.4 이진 검색 vs 선형 검색

만약 100개의 값을 가지고 있는 배열에서 각 검색에 필요한 최대 단계수는 다음과 같다.

선형 검색 : 100단계
이진 검색 : 7단계

👀 이진 검색은 어떤 패턴을 가지고 있는 건데?

배열의 크기가 3일 때, 이진 검색에 필요한 최대 단계 수는 2단계이다.

중간 값인 index 1 확인
target과 비교하여 최종 위치 확인 (index 0 or index 2)

?	?	?
0	1	2

배열의 크기가 7일 때에는, 이진 검색에 필요한 최대 단계 수는 3단계이다.

중간값 index 3 확인
target이 오른쪽 경우, index 4~6 사이 중간 값 index 5 확인
target과 비교하여 최종 위치 확인 (index 4 or index 6)
(왼쪽 영역이어도 단계 수는 동일)

?	?	?	?	?	?	?
0	1	2	3	4	5	6

이처럼 정렬된 배열의 크기가 2배로 늘어날 때마다, 이진 검색에 필요한 단계 수는 1단계씩 증가한다.

X축 : 배열 내 원소의 개수
Y축 : 알고리즘에 걸리는 단계 수

그래프만 확인해도 선형 검색과 이진 검색의 차이점이 드러난다. 선형 검색의 경우 원소가 많아질수록 검색에 걸리는 시간(단계)도 비례하여 늘어나지만, 이진 검색의 경우 원소의 개수가 많아질수록 검색에 걸리는 시간이 조금씩만 늘어난다. 즉! 이진 검색은 많은 원소를 가진 배열, 큰 배열에서 유리한 결과를 가진다.