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

알고리즘 : 어떤 과제를 완수하는 명령어 집합

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

2-1 정렬된 배열

정렬된 배열은 값이 항상 순서대로 있어야 한는 배열이다. 즉, 값을 추가 할 때마다 적절한 셀에 넣어 배열의 값을 정렬된 상태로 유지한다.

정렬된 배열에 삽입할 때는 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 오바른 위치를 정해야 된다. 전형적인 배열과 정렬된 배열의 성능 차이 중 하나.

전형적인 배열보다는 덜 효율적이지만, 정렬된 배열의 강력함은 검색 연산에서 드러난다.

2-2 정렬된 배열의 검색

정렬된 배열에서는 값이 배열에 들어있지 않을 때 검색을 더 빨리 멈출 수 있다.

• [3, 17, 75, 80, 202]에서 22를 찾는다고 하면 75에 도달하면 더 이상 22가 오른족에 있을 수 없으므로 바로 검색을 중단한다

const linerSearch = (array, serachValue) => {
	// 배열의 모든 원소를 순회한다
	for(let i = 0; i < array.length; i++) {
		if(array[i] === searchValue){
		// 원하는 값을 찾으면 그 인덱스를 반환
		return i;
		}
		else if(array[i] > searchValue){
			// 찾고 있던 값보다 큰 원소에 도달하면 루프를 일찍 종료한다
			break;
		}
	}
	// 배열에서 값을 찾지 못하면 null을 반환
	return null;
}

linearSearch([3, 17, 75, 80, 202], 22 )

선형 검색은 특정 상황에서 전형적인 배열보다 정렬된 배열에서 단계 수가 더 적게 걸린다. 하지만 찾으려는 값이 배열의 마지막 값이거나 마지막 값보다 크면 마찬가지로 모든 셀을 검색해야 끝난다.

하지만 정렬된 배열이 전형적인 배열보다 다른 검색 알고리즘을 쓸 수 있다.

이러한 알고리즘을 이진 검색이라 부르며 선형 검색보다 훨씬 빠르다.

2-3 이진 검색

이진 검색은 계속해서 가운데 셀을 골라 남은 수 중 반을 제거해 나가는 방법이다.

이진 검색은 정렬된 배열에만 쓸 수 있다. 전형적인 배열은 값의 순서가 뒤죽박죽이어서 주어진 값의 왼족에서 찾을지 오른쪽에서 찾을지 절대 알 수 없다.

2-3-1 코드 구현: 이진 검색

const binarySearch = (array, searchValue) => {
	// 먼저 찾으려는 값이 있을 수 있는 상한선과 하한선을 정한다
	// 최초의 상한선은 배열의 첫 번째 값, 하한선은 마지막 값이다.
	let lowerBound = 0;
	let upperBound = array.length - 1;
	
	// 상한선과 하한선 사이의 가운데 값을 계속해서 확인하는 루프를 시작한다
	while(lowerBound <= upperBound){
		// 상한선과 하한선 사이에 중간 지점을 찾는다
		// 책의 코드는 루비에서 결과값이 정수가 아닐 때 가장 가까운 정수로 올림한다고 했으므로 결과값을 가장 가까운 정수로 올림한다.
		const midPoint = Math.ceil((upperBound + lowerBound) / 2);
		
		// 중간 지점의 값을 확인한다
		const valueAtMidPoint = array[midPoint]
	
		// 중간 지점의 값이 찾고 있던 값이면 검색을 끝낸다
		// 아니면 더 클지 작을지 추측한 바에 따라 상한선 혹은 하한선을 바꾼다
		if(searchValue === valueAtMidPint){
			return midPoint;
		} else if (searchValue < valueAtMidPoint)[
			upperBound = midPoint - 1;
		} else if (searchValue > valueAtMidPoint){
			lowerBound = midPoint + 1;
		}
	}
	// 상한선과 하한선이 같아질 때까지 경계값을 줄였다면 찾고 있는 이 배열에 없다는 의미
	return null;
};
binarySearch([3, 17, 75, 80, 202], 22);

만일 searchValue가 valueAtMidPoint보다 작다면, searchValue를 중간 인덱스 이전에서만 찾을 수 있다는 뜻이다. upperBound에 midPoint의 바로 왼쪽 인덱스를 할당해 검색 범위를 좁힐 수 있다.

반대로 searchValue가 valueAtMidPoint보다 크다면 searchValue를 midPoint의 오른편에서만 찾을 수 있다는 뜻이니 lowerBound에 midPoint의 바로 오른쪽 인덱스를 할당한다

범위가 원소 0개로 좁혀지면 null을 반환한다. searchValue가 배열에 없는 것이 확실하기 때문이다.

2-4 이진 검색 대 선형 검색

작은 크기의 정렬된 배열이라면 이진 검색 알고리즘이 선형 검색 알고리즘보다 크게 나은 점이 없지만 배열이 100개의 값을 갖는다고 생각하면 선형 검색은 100단계가 되는 반면 이진 검색은 7단계로 크게 차이난다.

선형 검색에서는 찾고 있는 값이 마지막 셀에 있거나 마지막 셀의 값보다 크면 모든 원소를 조사해야 한다.

선형 검색은 배열의 원소 수를 두 배로 늘릴 때 마다 검색에 필요한 단계 수도 두 배로 늘어난다. 하지만 이진 검색에서는 데이터를 두 배로 늘릴 때 마다 최대 한 단계만 더 추가된다.

예를 들어 크기가 10,000 혹은 1,000,000개인 배열에서 선형 검색은 최대 10,000 / 1,000,000 단계가 걸리지만 이진 검색은 최대 13 / 20단계면 된다

2-4-1 깜짝 퀴즈

• 문제 : 원소가 100개인 정렬된 배열에서 이진 검색은 7단계가 걸렸다. 원소가 200개인 정렬된 배열에서 이진 검색은 몇 단계각 걸릴까?
• 정답 : 8단계

이진 검색의 묘미는 검사할 때 마다 남은 원소의 반을 제거하는 데 있다. 그러니 데이터 크기를 두 배로 늘릴 때 마다 1단계만 늘어난다고 보면 된다.

2-5 마무리

모든 상황에 완벽하게 들어맞는 단 하나의 자료 구조나 알고리즘은 거의 없다. 정렬 배열에 이진 검색을 쓸 수 있다고 해서 항상 정렬된 배열을 써야 하는 것은 아니다.