시간 복잡도

효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다는 것

시간 복잡도는 주로 Big-O(빅-오) 표기법을 사용

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

• Big-O(빅-오) - 최악 고려

• Big-Ω(빅-오메가) - 최선만 고려

• Big-θ(빅-세타) - 중간(평균)

빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 가장 자주 사용됨

빅오 시간 복잡도의 x축은 데이터량 / y축은 연산 시간

빅오 표기법 종류

1. O(1)

O(1)은 constant complexity라고 하며 입력값이 증가하더라도 시간이 늘어나지 않는다. 다시 말해 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다는 의미

ex) arr[idx] 값

2. O(N)

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

입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기

ex) 1중 반복문

3. O(log n)

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도

O(log n)인 BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.

4. O(n의 2승)

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

2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n의 3승과 n의 5승도 모두 O(n의 2승)로 표기한다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기

ex) n중 반복문

5. O(2의 n승)

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

재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘

데이터 크기에 따른 시간 복잡도

데이터 크기 범위	예상되는 시간 복잡도
n ≤ 1,000,000	O(n) or O (logn)
n ≤ 10,000	O(n2)
n ≤ 500	O(n3)

알고리즘 종류

1. Greedy Algorithm

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

탐욕 알고리즘의 문제 해결 과정

1.선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택

2.적절성 검사(Feasibility Check): 선택된 해답이 문제의 조건을 만족하는지 검사

3.해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

탐욕 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 그래프나 정렬, 다익스트라(Dijkstra) 알고리즘까지 폭넓은 영역에서 사용됨

최소비용 신장 트리 : 그래프 내의 모든 정점을 최소 비용으로 연결하는 트리

Kruskal 알고리즘 : 최소비용 신장 트리를 만드는 알고리즘 중 탐욕 알고리즘을 이용한 풀이

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식
=> 항상 최적의 결과를 보장하지는 못한다는 점을 명심

탐욕 알고리즘 적용 조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점
=> 탐욕 알고리즘은 근사 알고리즘으로 사용 가능

2. Implementation

알고리즘 문제를 푼다는 것은, 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것

본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 함

구현 능력을 보는 대표적 사례

1.완전 탐색
완전 탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식

모든 문제는 완전 탐색으로 풀 수 있습니다. 이 방법은 굉장히 단순하고 무식하지만 "답이 무조건 있다"는 강력함있음

문제를 풀 수 있는 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 전부 탐색할 수밖에 없다고 판단될 때 적용

ex) brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등이 있음

2.시뮬레이션
시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형

3. Dynamic Programming(DP: 동적 계획법)

탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식

다이나믹 프로그래밍 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. (Overlapping Sub-problems)

2. 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)

다이나믹 프로그래밍 사용한 해결 방법

1.Recursion + Memoization

다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용
이때 결과를 저장하는 방법인 Memoization은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
		// 없다면 재귀로 결괏값을 도출하여 res 에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    memo[n] = res;
    return res;
}

ex) 피보나치
n이 커질수록 계산해야 할 과정은 선형으로 늘어나기 때문에 시간 복잡도는 O(N)
Memorization을 사용하지 않고 재귀 함수로만 문제를 풀 경우, n이 커질수록 계산해야 할 과정이 두 배씩 늘어나 시간 복잡도가 O(2^N)

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식은 Top-down 방식

2.Iteration + Tabulation
반복문을 이용하여 다이내믹 프로그래밍을 구현하는 방법

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 방식)

크롬 개발자 도구에서 함수 실행 시간 측정 방법

var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')

Algorithm with Math

1. 순열

n 개 중에서 일부만을 선택하여 나열하는 것을 순열
=> 순열은 순서를 지키며 나열

순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현

일반식 : nPr = n! / (n - r)!

ex) 숫자는 순서에 의해 전혀 다른 값이 되므로 순열로 처리한다.

2. 조합

조합은 순열과 달리 순서를 고려하지 않는다.
중복되는 같은 요소의 경우의 수는 하나로 친다.

조합은 일반화 과정을 거쳐, Combination의 약자 C로 표현

일반식: nCr = n! / (r! * (n - r)!)

ex) 사물이나 사람 등을 순서를 생각하지 않고(중복 제거) 고르는 것은 조합

• 조합: n개의 요소 중 p개롤 뽑는 경우의 수

• 순열: n개의 요소 중 p개롤 뽑는 경우의 수(순서가 있는 경우의 수)

• 중복순열: n개의 요소 중 p개롤 뽑는 경우의 수(순서, 요소가 중복이 가능한 경우의 수)

3. GCD/LCM

• 약수: 어떤 수를 나누어떨어지게 하는 수

• 배수: 어떤 수의 1, 2, 3, ...n 배하여 얻는 수

• 공약수: 둘 이상의 수의 공통인 약수

• 공배수: 둘 이상의 수의 공통인 배수

• 최대 공약수(GCD: Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수

• 최소 공배수(LCM: Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

4. 멱집합

어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합

부분집합을 나열하는 방법에서 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지에 따라 단계를 나누는 기준을 결정

원소가 있는지, 없는지 2가지 경우를 고려하기 때문에 집합의 요소가 n 개일 때 모든 부분집합의 개수는 2n개

멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠는 것을 확인 가능
순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법
문제를 작은 단위로 줄여나가는 재귀를 응용
문제가 가장 작은 단위로 줄어들고, 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있다.