TIL 45일차

시작하며

오늘은 자주 사용하는 알고리즘과 시간복잡도에 대해 학습하였다. 코딩 테스트의 문제를 풀 때 제한 사항에 시간 복잡도가 자주 등장했지만 알지 못했는데 이번 챕터를 통해서 개념을 이해할 수 있었다.

Algorithm

Time Complexity

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 이 중에서 Big-O 표기법이 가장 자주 사용되는데, 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다. "최소한 특정 시간 이상이 걸린다" 혹은 "이 정도 시간이 걸린다"를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능하다.

O(1)
O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

function O_1_algorithm(arr, index) {
	return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O(log n)
O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
자료구조에서 배웠던 BST(Binary Search Tree)가 O(log n)의 대표적인 예이다.
BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다. 이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있습니다.

1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정).
50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
25보다 크므로 up을 외친다.
경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.
매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 된다.
BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)입니다.

O(n^2)
O(n^2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}
function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

O(2^n)
O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

Greedy Algorithm

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 다음과 같이 단계적으로 구분할 수 있다.

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

탐욕 알고리즘 사례
김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였다.

이때 김코딩은 어떻게 거슬러 주어야 할까? 탐욕 알고리즘으로 동전의 개수를 헤아리는 일은, 우리가 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다. 거스름돈 960원을 채우기 위해서 먼저, 500원짜리 동전을 한 개 선택한다. 그다음은 100원짜리 동전을 네 개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택한다. 김코딩의 입장에 탐욕 알고리즘의 문제 해결 과정을 적용하면 다음과 같이 문제를 단계적으로 구분할 수 있다.

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한 후, 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사하고 액수가 부족하면 1번 과정부터 다시 반복한다.

탐욕 알고리즘은 아래 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다. 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야 한다.

- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

마치며

오늘 Section 3에서 첫 페어 프로그래밍을 진행하였는데, 오랜만에 페어와 상의하면서 코플릿을 함께 풀면서 학습한 알고리즘을 설계하고 이해할 수 있어서 도움이 되었다. 또 단순히 답을 도출하는 것 뿐만 아니라 시간복잡도를 고려해서 코드를 수정하고 어떤 알고리즘을 사용해서 문제를 푸는 것이 효율적일지를 생각하면서 문제를 풀면서 오늘 배운 내용을 확실하게 이해할 수 있었다.