알고리즘, 시간 복잡도와 경우의 수 기본 개념

시간 복잡도

입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘 수행 시간을 평가하는 방법이다.
3가지 표현법으로 빅오, 세타, 오메가가 있다.
- 빅오 : 최악의 상황을 고려하여 성능 측정 결과 표현
- 세타 : 평균적인 경우에서의 성능 측정 결과 표현
- 오메가 : 최선의 상황일 때의 성능 측정 결과 표현

알고리즘 성능 평가 지표로는 정확성, 작업량, 메모리 사용량, 최적성, 효율성(시간 복잡도와 공간복잡도)가 있다. 코딩 테스트에서는 메모리 사용량과 효율성 내 시간 복잡도를 중점적으로 봐야 한다.

빅오 표기법 예제를 몇 가지 살펴보자.

function big_o(n){
	let sum = 0;
    
    sum = n * 2;
    
    return sum;
}

위 코드는 총 3회 실행이 되고 반복되는 코드가 없이 한 줄 한 줄의 코드가실행됨으로 빅오 표기는 '3 -> O(1)'이 된다.

그러면 반복문의 경우를 살펴보자.

function big_o(arr,n){
	let sum = 0;
    
    for (let i = 0; i < n; i++){
    	sum += arr[i]
    }
    
    return sum
}

위 코드는 선언에서 1회, 반복문에서 n회, 반환하는데 1회로 'n+2 -> O(N)'으로 표기된다.

for문이 2개일 때는 어떻게 되는지도 살펴보자.

function big_o(arr, n){
  let sum = 0;
  
  for(let i=0; i<n; i++){
    for(let j=0; j<n; j++){
      sum += arr[i][j]
    }
  }
  
  return sum
}

선언과 반환은 각각 1회며 for문에서 n * n회가 된다. 따라서 'n^2 + 2 -> O(N^2)'로 표기가 된다.

경우의 수

어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현한 것이 경우의 수다. 학창시절 수학 시간에 배운 내용들이며 이를 활용한 알고리즘 문제가 나올 수 있다.

일상생활에서 경우의 수는 주사위, 윷, 가위바위보, 동전 등이 되겠다. 알고리즘에서 완전 탐색으로 경우의 수를 푸는 알고리즘이 있는데 순열과 조합, 중복 순열에 대한 개념을 알 필요가 있다.

순열 : 서로 다른 n개 원소에서 r을 중복 없이 골라 순서로 나열하는 경우의 수
조합 : 서로 다른 n개 원소에서 r을 중복 없이 골라 순서와 관련 없이 나열하는 경우의 수
중복 순열 : 서로 다른 n개 원소에서 r개를 중복 있게 골라 순서로 나열하는 경우의 수

순열

순열의 예제로 a, b, c를 가지고 만들 수 있는 단어의 경우의 수를 코드로 확인해보자.

let input = ["a", "b", "c"];
let count = 0;

function permutation(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i === j) continue;
      for (let k = 0; k < arr.length; k++) {
        if (i === k || j === k) continue;

        console.log(arr[i] + arr[j] + arr[k]);
        count++;
      }
    }
  }
}

permutation(input);
/*'abc'
'acb'
'bac'
'bca'
'cab'
'cba' */

console.log(count); //6

배열의 요소가 3개로 for 반복문이 세 번 반복되는데 그 요소가 많아지면 반복문이 늘어나는 문제가 있다. 그래서 재귀 함수를 사용하는 것이 좋다.

let input = ["a", "b", "c"];
let count = 0;

function permutation(arr, s, r) {
  // 재귀 함수 멈춰야할 조건
  if (s === r) {
    count++;
    console.log(arr.join(""));
    return;
  }

  // 재귀를 돌면서 변경되어야 될 로직
  for (let i = s; i < arr.length; i++) {
    [arr[s], arr[i]] = [arr[i], arr[s]]; // swap
    permutation(arr, s + 1, r);
    [arr[s], arr[i]] = [arr[i], arr[s]]; // 원상복귀
    /*
    s = 0, r = 2 i = 0["a", ]
    s = 1, r = 2 i = 1["a", "b", ]
    s = 2, r = 2 ["a", "b", "c"]
    ...
    s = 1, r = 2, i = 2 ["a", "c", ]
    s = 2, r = 2 ["a", "c", "b"]
    s = 2, r = 2, i = 2 ["a", "b", ]
    ...
    s = 0, r = 2, i = 1 ["b", "a", "c"]
    
    ...
    s = 0, r = 2, i = 2 ["c",
    */
  }
}

permutation(input, 0, 2);
console.log(count);

조합

조합의 예시로는 4개의 숫자 카드에서 2개를 뽑는 경우의 수, 순서가 상관이 없다.

let input = [1, 2, 3, 4];
let count = 0;

function combination(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      count++;
      console.log(arr[i], arr[j]);
    }
  }
}

combination(input);
/*
1 2
1 3
1 4
2 3
2 4
3 4
*/

console.log(count);
// 6

조합도 반복문을 사용할 수 있으나 요소가 많아지면 많아질 수록 순열처럼 반복문이 늘어날 수 있기에 재귀 함수로 푸는 것이 좋다.

let input = [1, 2, 3, 4];
let output = [];
let count = 0;

function combination(arr, data, s, idx, r) {
  if (s === r) {
    count++;
    console.log(output);
    return;
  }

  for (let i = idx; arr.length - i >= r - s; i++) {
    data[s] = arr[i];
    combination(arr, data, s + 1, i + 1, r);
  }
}

combination(input, output, 0, 0, 2);
console.log(count);