알고리즘

알고리즘은 사전적 의미로, 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다. 결국, 문제를 어떤 식으로 푸는 것이 최선인가로 정의될 수 있다.

1. 시간 복잡도

시간 복잡도 정의

프로젝트 코드를 리팩토링 하는 과정에서, 팀원 분과 가장 많이 고민했던 부분이 바로 조금 더 간단하게 짤 수 없을까? 였다. 조금 더 간단하게, 더 효율적인 방법을 고민하는 것은, 시간 복잡도를 고민하는 것과 같다.시간 복잡도를 고민하는 것은 한 마디로, "입력값의 증가/감소함에 따라 시간이 얼마나 비례하여 증가/감소하는가?"와 같다.

시간 복잡도 종류

시간 복잡도를 표기하는 방법은

• Big-O
• Big-Ω
• Big-θ

등이 있다. 순서대로 각각 최악, 최선, 평균의 경우 입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기하는 방법이다. 이중, 가장 흔히 사용 되는 것이 Big-O 표기법이다. 최선이나 평균을 고려하여 작업을 하였을 때, 예상보다 안좋은 결과가 나온 경우 문제가 어디서 발생했는지를 찾아내는 과정이 필요하게 되기 때문이다.

Big-O 표기법

1) O(1)

• Constant Complexity
• 입력값이 증가해도 시간이 늘어나지 않는다.
• Ex) 특정 배열의 인덱스로 값을 찾는 알고리즘

2) O(n)

• Linear Complexity
• 입력값이 증가와 같은 비율로 증가한다.
• Ex) 다음과 같은 반복분

for(let i = 0; i < n; i++){
	...
    }

여기서 n이 아니라 2n이어도 결과는 같다. 계수가 몇이든, Linear Complexity라면 모두 O(n)으로 계산한다.

3) O(log n)

• Logarithmic Complexity
• O(1) 다음으로 빠른 시간 복잡도
• 코드가 진행될 수록 경우의 수가 절반으로 줄어든다.

4) O(n^2)

• Quadratic Complexity
• 입력값이 증가함에 따라 시간이 제곱의 비율로 증가한다.
• Ex)

for(let i = 0; i < n; i++){
	for(let j = 0; j < n; j++){
    	...
        }
    }

O(n)과 마찬가지로, n^3이나 n^7 모두 Big-O 표기법에서는 O(n^2)로 표현한다.

5) O(2^n)

• Exponential complexity
• 가장 느린 시간 복잡도
• Ex) 재귀로 구현하는 피보나치 수열

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

2. 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘 정의

탐욕 알고리즘이란, 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘의 단계는 총 3가지로,

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

탐욕 알고리즘 한계

탐욕 알고리즘은, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식이다. 하지만 이러한 방법은 항상 최적의 결과를 보장하지 못한다는 단점이 있다. 따라서 탐욕 알고리즘을 사용할 때 성립해야하는 두 가지 조건이 있다.

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

최적의 결과를 보장받지는 못하지만, 어느 정도 최적해에 근사한 값을 빠르게 도출할 수 있다는 장점이 있기 때문에 근사 알고리즘으로 사용 가능하다.

3. 동적 계획법(Dynamic Programming)

동적 계획법 정의

동적 계획법은, 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식이다. 하위 문제를 계산하고 그 해결책을 저장하여, 후에 같은 하위 문제가 나왔을 경우 저장된 해결책을 이용하여 계산 횟수를 줄임으로써 비효율적인 알고리즘을 개선하는 방법이다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 것이 핵심이다.

동적 계획법은 두 가지 가정이 만족해야 사용할 수 있다.

• (1) 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다.
• (2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다.

동적 계획법에서는 하위 문제의 저장된 해결책을 이용하여 계산 횟수를 줄인다고 하였다. 이를 메모이제이션(Memoizaion)이라고 부른다.

function fibMemo(n, memo = []) {
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    memo[n] = res;
    return res;
}

위 코드에서는 memo 배열에 기존에 계산해뒀던 값이 있다면 꺼내 사용한다. 없다면, 새롭게 그 값을 계산하고 memo 배열에 추가한다.
이러한 방식으로 메모이제이션을 사용할 경우 시간 복잡도가 줄어든다.
기존의 재귀함수로 구현한 피보나치 수열의 경우 O(2^n)의 시간 복잡도가 나오지만, 메모이제이션을 사용한 피보나치 수열의 경우, fib(n)은 fib(0)부터 fib(n-1)까지의 값을 한 번씩만 연산하면 나머지는 O(n)으로 시간 복잡도가 줄어든다.