Programming Algorithm

그리디 알고리즘

현재 상황에서 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘이다. 최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많다. 일반적으로 다음과 같은 과정을 거칠 수 있다.

1. 방법 고안: 현재 상황에서 어떤 것을 선택할지 알고리즘 고안
2. 정당성 확인: 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 확인

DFS 알고리즘

그래프나 트리에서 모든 노드를 한번씩 탐색하기 위한 기본적인 방법이다. 완전 탐색을 수행하고자 할 때 가장 간단한 방법 중 하나다. 주로 스택 혹은 재귀함수를 이용한다.

1. 그래프를 인접 리스트 형태로 표현
2. 시작 노드를 스택에 넣고 방문처리
3. 루프를 돌면서 해당 노드에 방문하지 않은 인접 노드가 있는지 확인
4. 있다면 방문하지 않은 재귀함수 호출, 없다면 종료

다이나믹 프로그래밍

통상적으로 메모리를 더 사용하여 시간 복잡도를 계산할 때 많이 사용된다. 시간복잡도가 비효율적인 알고리즘이 있을 때 부분 문제의 반복이 발생하는 경우 적용하면 효과적이다.

피보나치 수열을 재귀함수로 다음과 같이 구현할 수 있다. 하지만 재귀함수를 두번씩 호출하는 형태로 시간 복잡도가 상당히 좋지 않다. (2^n)

function fibo(x) {
  if(x == 1 || x == 2) {
    return 1;
  }
  return fibo(x-1) + fibo(x-2);
}

메모제이션 기법으로 다음과 같이 구현하게 되면 시간 복잡도가 n으로 줄어든다.

let d = new Array(100).fill(0);

function fibo(x) {
  // 1. 종료 조건
  if(x == 1 || x == 2) {
    return 1;
  }
  // 2. 이미 해결한 문제라면 정답을 그대로 반환
  if(d[x] != 0) {
    return d[x];
  }
  // 점화식에 따라 정답 계산
  d[x] = fibo[x-1] + fibo[x-2];
  return d[x];
}

다이나믹 프로그래밍은 점화식을 찾는 것이 핵심이다. 다음과 같은 해결 순서로 접근한다.

1. 문제 이해하기
2. 점화식 찾아내기 -> 가장 핵심 부분
3. 구현 방식(상향식/하향식) 결정하기
4. 점화식을 실제 코드로 구현하기

상향식: 반복문을 이용해 초기 항부터 계산한다.

let d = new Array(100).fill(0);

function fibo(x) {
  if(x == 1 || x == 2) {
    return 1;
  }
  if(d[x] != 0) {
    return d[x];
  }
  d[x] = fibo[x-1] + fibo[x-2];
  return d[x];
}

하향식: 재귀함수로 큰 항을 구하기 위해 작은(이전) 항을 호출하는 방식이다. (이미 구한 함수 값을 담는 테이블을 흔히 DP 테이블이라고 한다.)

let d = new Array(100).fill(0);

d[1] = 1;
d[2] = 1;
n = 99;

for(let i=3; i<=n; i++){
  d[i] = d[i-1] + d[i-2];
}

순열 & 조합

순열(Permutation)은 노드를 순서에 따라 배열하는 경우의 수이다. 5개의 문자를 순서를 고려하여 3개를 선택할 경우 총 60(5x4x3)가지 경우의 수가 나온다.

조합(Combination)은 순열과 다르게 순서와 상관 없이 배열하는 경우의 수이다. 5개의 문자를 순서를 고려하지 않고 3개를 선택하는 경우 총 10가지이다. 전체 경우의 수(순열)가 60이고 중복되는 노드를 선택하는 경우가 6(3x2x1)가지이기 때문이다.

기호로 표시하면 다음과 같다.

• 순열: 5P3 = 5 x 4 x 3 = 60
• 조합: 5C3 = 5P3 / 3! = 60 / 6 = 10