[Algorithm] 알고리즘이란, Big-O

Algorithm

알고리즘 - '문제를 어떤 식으로 푸는 것이 최선인가'

1. 문제 이해하기

• 제한사항 및 주의사항 꼼꼼히 읽기.

2. 문제에 대한 전략 세우기

• suedo code 짜기
• 그림 그리기

3. 코드 작성하기

• 전략을 코드로 옮기기
• 최적화 해보기

Time Complexity

입력값의 증가/감소에 따라 시간이 얼마만큼 비례하여 증가/감소하는가?
효율적인 알고리즘 - 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘

Big-O

시간 복잡도를 표현하는 방법
Big-O (최악)
Big-Ω (최선)
Big-θ (평균)

Big-O가 자주 사용되는 이유는 항상 최악의 경우를 대비하여 알고리즘을 설계해야 문제가 발생할 경우 쉽게 찾을 수 있다.

Big-O 표기의 종류

Fast -> Slow

O(1)

Constant complexity.
입력값이 증가해도 시간이 늘어나지 않음.

O(n)

Linear complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가.

입력값이 커지면 커질수록 계수의 영향력이 줄어들기 때문에 $O(2n)$, $O(10n)$ 등은 $O(n)$ 으로 표기.

O(log n)

Logarithmic complexity

Binary Search Tree 는 노드를 이동할 때 마다 경우의 수가 절반으로 줄어든다.
Binary Search 또한 중간값을 찾을 때 마다 범위가 반으로 줄어든다.

O(n^2)

Quadratic complexity

입력값이 증가함에 따라 시간이 그 제곱수의 비율로 증가

$O(n^3)$, $O(n^5)$ 등을 모두 $O(n^2)$ 으로 표기.

예시)

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

O(2^n)

Exponential complexity

Big-O 표기법 중 가장 느리다.

입력값이 증가할 때 마다 시간이 두배로 증가한다.
지수 복잡도를 가진 알고리즘은 다시 생각해봐야 한다.

예시) 재귀로 구현한 피보나치 수열

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

Advanced

코딩테스트는 정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성해야 한다.
데이터가 클 때는 O(n) 혹은 O(log n) 정도로 예측해서 문제를 풀어보고, 주어진 데이터가 작을 때는 시간복잡도가 크더라도 문제 풀이에 집중하는 것이 좋다.

데이터 크기 제한	예상 시간 복잡도
n ≤ 1,000,000	O(n), O(log n)
n ≤ 10,000	O(n^2)
n ≤ 500	O(n^3)

Tips

N^2 에서 줄일 때 -> BS, DP (Memo), 정렬

기본: 완전탐색 (exhaustive search)

• DFS/BFS, 순열/조합(부분집합) => coding test 70% 이상 cover

그래프류, 최단거리(다익스트라, 벨만포드, 플로이드 와샬)
sort 류 (sort 는 요즘 잘 안나옴)

공간복잡도

JS 에서 데이터 1천만개는 8MB

그래프류

N 이 1000개 -> 1000 x 1000 < 1천만
N 이 10000개 -> 이차원 행렬 쓰면 안됨. 10000^2 > 1천만

문제가 풀리기만 하면 최적화는 필요없다 -> over engineering, overkill

책

누워서 읽는 알고리즘, 누워서 읽는 퍼즐북, 즐거운 논리, Nine altorithms taht changed the future