[Algorithm] 기초(1)
알고리즘
시간 복잡도
시간 복잡도는 알고리즘을 구현할 때 입력 값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마만큼 걸리는지에 대한 값을 말한다. 일반적으로 빅오 표기법을 사용해 나타낸다.
빅오 표기법
시간 복잡도를 표기하는 여러 방법들 중 빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정한다. 최대 이정도 시간까지 걸릴 수 있다를 고려해야 그에 맞는 대응을 하기 때문에 주로 사용된다.
O(1)
O(1)은 입력 값의 크기와 관계없이 즉시 출력값을 얻어낸다. 이를 상수 시간이라고 부른다. 예를 들면 배열에 있는 항ㅂ목을 인덱스로 사용해 접근하는 경우가 있다.
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); // 2O(n)
O(n)은 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 말한다. 일반적으로 입력값 n이 1일때 2n의 시간이 걸린다고 해서 O(2n)이라 부르지 않고 같은 비율로 증가한다면 2배가 아닌 5배, 10배가 증가하더라도 O(n)으로 표기한다.
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) 은 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다. 대표적으로 이진 검색 트리(BST)가 있다.
O(n^2)
O(n^2)은 입력값이 증가함에 따라 시간이 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 } } } }2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n3과 n5 도 모두 O(n2)로 표기한다.
O(2^n)
O(2^n)은 빅오 표기법 중 가장 느린 시간 복잡도를 가진다. 가장 대표적인 예로 재귀로 구현한 피보나치 수열이 있다.
function fibonacci(n) { if (n <= 1) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); }
참고 링크
Greedy Algorithm
일명 탐욕 알고리즘이라 불리는 Greedy Algorithm은 현재 시점에서 최적의 답을 찾기 위한 선택을 하는 방법을 말한다. 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다. 그러나 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 한다.
탐욕 알고리즘으로 문제를 해결하는 방식은 다음과 같이 단계적으로 구분할 수 있다.
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.
탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 한다.
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.
구현(Implementation)
문제를 보고 스스로 문제를 푸는 과정을 생각하여 소스코드로 바꾸는 것(Problem - thinking - solution) 을 말한다. 코딩 테스트에는 시간제한과 메모리를 제한할 수가 있기 때문에 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭할 수 있습니다.
구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있다. 완전 탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식을 뜻하고, 시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습을 그려내는 것을 말한다.
-
완전 탐색(brute force)
-
시뮬레이션(simulation)
동적 프로그래밍(Dynamic Programming)
동적 프로그래밍은 문제를 그 문제보다 더 작은 부분 문제들로 쪼개 최적의 부분 문제들을 해결한 다음 이에 대한 결과를 메모리에 저장해 동일한 문제를 해결해야 하는 경우에 이미 해결된 문제의 결과에 접근하는 방식을 말한다. 이를 통해 알고리즘의 복잡도는 크게 줄어들게 된다. 다음 피보나치 수열 예제를 참고해보자.
function fibonacci(n) {
if(n <= 1) {// 0번째, 1번째 피보나치 수
return n;
} else {
return fibonacci(n-1)+fibonacci(n-2);
}
}
위 예제의 시간복잡도는 O(2^n)이다. 따라서 n이 커짐에 따라 실행 시간이 기하급수적으로 증가하게 된다. 이를 개선해보자
let cache = {}
function newFibonacci(n) {
if (n <= 1) return n;
if(cache[n]) return cache[n];
return (cache[n] = newFibonacci(n-1) + newFibonacci(n-2));
}
위 방식의 시간복잡도는 O(N)이다. 6에 대한 피보나치 수열을 계산하기 위해 5와 4에 대한 피보나치 수열을 계산해야 하고, 5와 4에 대한 피보나치 수열을 계산하기 위해 3과 2 피보나치 수열을 계산하고… 이렇게 1의 피보나치를 구할때까지 반복된다. 이렇게 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 Top-down방식이라 부른다.
다른 방법도 살펴보자.
function fibTab(n) {
if(n <= 2) return 1;
let fibNum = [0, 1, 1];
// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
}
return fibNum[n];
}
하위 문제의 결과값을 배열에 저장하고 필요할 때 조회해 사용하는 것은 재귀 함수를 이용한 방법과 동일하다. 하지만 반복문을 이용해 작은 문제에서부터 시작해 큰 문제를 해결해 나가는 방법으로도 계산이 가능하다. 이러한 방식을 bottom-up방식이라 한다.
두 가지 방법 중 어느것이 더 나은것이냐는 질문에 대한 답변은 “알 수 없다”이다. Top-down 방식은 점화식을 이해하기 쉽다는 장점이 있고, Bottom-up 방식은 함수를 재귀 호출하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다. 각각의 상황에 맞는 방식을 채택해야 한다.