알고리즘 기본(시간 복잡도, 경우의 수, 순열, 조합, 점화식)

알고리즘 복잡도

• 알고리즘 성능 평가 지표

  • 정확성
  • 작업성
  • 메모리 사용량
  • 최적성
  • 효율성
    • 시간 복잡도
    • 공간 복잡도

• 시간 복잡도

  • 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법
  • 3가지 점근적 표현법
    • 빅오 : 최악의 상황을 고려하여 성능 측정 결과 표현
    • 세타 : 평균적인 경우에서의 성능 측정 결과 표현
    • 오메가 : 최선의 상황일 때의 성능 측정 결과 표현
  • 빅오 복잡도 차트를 보면 log일 때 퍼포먼스가 좋음

• 빅오 표기법의 경우 for문 하나의 경우 n회로 따지고 수행 하나는 1회로 침

• 이 때 1+1+1 = 3이어도 O(1)임 n이 있다면 1+n+1 = n+2인데 O(n)임

• 참고자료

경우의 수

• 어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현
• 일상 생활에서의 경우의 수
  • 주사위 : 던지는 결과, 1 ~ 6 사이의 숫자이므로 경우의 수는 6
  • 윷 : 던지는 결과, 도,개,걸,윷,모 이므로 경우의 수는 5
  • 가위바위보 : 게임 결과, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 3
  • 동전 : 던지는 결과, 앞면 혹은 뒷면이므로 경우의 수는 2
• 완전탐색으로 경우의 수를 푸는 알고리즘
  • 순열 : 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 nPr
  • 조합 : 서로 다른 n개의 원소 중에서 r를 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수 nCr
  • 중복 순열 : 서로 다른 n개의 원소 중에서 r개를 중복 있게 골라 순서에 상관 있게 나열하는 경우의 수 nHr

// 순열 예제
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) continue;
        if (j == k) continue;

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

permutation(input);

// 순열 예제(재귀 활용)
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]];
    permutation(arr, s + 1, r);
    [arr[s], arr[i]] = [arr[i], arr[s]];
  }
}

permutation(input, 0, 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);

// 조합 예제(재귀 활용)
let input = [1, 2, 3, 4];
let output = [];
let count = 0;

function combination(arr, data, s, idx, r) {
  if (s == r) {
    count++;
    console.log(data);
    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);

점화식

• 점화식(재귀식)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식
• 대표적인 점화식
  • 등차수열 : F(n) = F(n - 1) + a
  • 등비수열 : F(n) = F(n - 1) * a
  • 팩토리얼 : F(n) = F(n - 1) * n
  • 피보나치 수열 : F(n) = F(n - 1) + F(n - 2)
• 등차수열 예제

let result;

function forloop(s, t, number) {
  let acc = 0;

  for (let i = 1; i <= number; i++) {
    if (i == 1)
      acc += s;
    else
      acc += t;

    console.log(i, acc);
  }

  return acc;
}

result = forloop(3, 2, 5);
console.log(result);

let result;

function recursive(s, t, number) {
  if (number == 1) {
    return s;
  }

  return recursive(s, t, number - 1) + t;
}

result = recursive(3, 2, 5);
console.log(result);

• 등비수열 예제

let result;

function forloop(s, t, number) {
  let acc = 0;

  for (let i = 1; i <= number; i++) {
    if (i == 1)
      acc *= s;
    else
      acc *= t;

    console.log(i, acc);
  }

  return acc;
}

result = forloop(3, 2, 5);
console.log(result);

let result;

function recursive(s, t, number) {
  if (number == 1) {
    return s;
  }

  return recursive(s, t, number - 1) * t;
}

result = recursive(3, 2, 5);
console.log(result);

• 팩토리얼 예제

let result;

function recursive(number) {
  if (number == 1) {
    return number;
  }

  return recursive(number - 1) * number;
}

result = recursive(5);
console.log(result);

• 피보나치 수열 예제

let result;

function recursive(number) {
  if (number == 1 || number == 0) {
    return number;
  }

  return recursive(number - 1) + recursive(number - 2);
}

result = recursive(5);
console.log(result);