CS)쉬운 알고리즘으로 알아보는 빅 오 시나리오

먼저 아래의 간단한 알고리즘을 이해하고 빅오표기법을 산출할 수 있어야 한다.

팰린드롬 검사기

팰린드롬(pallindrome)은 앞으로 읽으나 뒤로 읽으나 똑같은 단어 혹은 구절이다.
'racecar','kayak','deified'등이 팰린드롬이다.

다음은 어떤 문자열이 팰린드롬인지 판단하는 자바스크립트 함수다

function isPallindrom(word) {

  let firstIndex = 0;
  let lastIndex = word.length - 1;
  let flag = lastIndex / 2
  
  while(firstIndex <= flag) {
  	if(word[firstIndex] !== word[lastIndex]) {
    	return false
    }
    firstIndex++
    lastIndex--
  }
  return true
}
}

모든 수를 순회하지 않고 firstIndex가 중앙에 위치할 경우 while문이 종료된다.
flag로 인해 위 알고리즘의 Big O는 O(n / 2)이고 상수를 제외하면 O(n)이다.

모든 수 곱하기

넘버로 된 배열을 받아 두 숫자 조합의 곱을 반환하는 알고리즘이다
만약 [1,2,3,4,5]라는 배열을 받는다면 반환값으로 [2,3,4,5,6,8,10,12,15,20]을 반환해야한다.

function allNumberMultiply(numArr) {
  let result = []
  
	for(let i = 0; i < numArr.length; i++) {
    for(let j = i + 1; j < numArr.length; j++) {
      result.push(numArr[i] * numArr[j]);
    }
  }
  return result;
}

allNumberMultiply([1,2,3,4,5])

위 알고리즘의 시간복잡도는 O(N² / N)이다. j는 i보다 항상 앞서있다.
N이 5라면, j는 N - 1, N - 2, N - 3 ,N - 4 ... + 1 패턴으로 움직인다.
하지만 마찬가지로 상수는 무시되기에 빅오 표기법으로는 O(N²)이다.

서로 다른 배열 내 모든 수 곱하기

위 예제의 응용이다.
예를 들어 [1,2,3] [10,100,1000] 배열이 있다면 [10,100,1000,20,200,2000,30,300,3000] 을 반환해야 한다.

function allArraymultiply(arr,arr2) {
  let answer = [];
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr2.length; j++) {
      answer.push(arr[i] * arr2[j]);
    }
  }
  return answer
}

console.log(allArraymultiply([1,2,3],[10,100,1000]));

시간복잡도 O(N * M)

위 함수의 시간복잡도를 분석하려 한다.
먼저 지금까지와는 다른 형태의 N이다. 늘 1개의 데이터세트였지만 지금은 두 개의 배열을 N으로 받는다.

두 배열을 합쳐 단순히 N이라고 하고 싶지만 걸리는 부분이 있다.

두 가지 시나리오가 있다.

1. 크기가 5인 배열 두 개가 있다.
2. 크기가 9인 배열과 크기가 1인 배열이 있다.

5 + 5는 10이고, 9 + 1 = 10이기에 N은 10이다.

하지만 두 시나리오의 효율성은 완전히 다르다.

시나리오1에서는 25단계가 걸리지만 N이 10이므로 (N / 2)²단게와 동일하다.
시나리오2에서는 9단계(9 * 1)가 걸리며 시나리오 1보다 엄청 빠르다.

시나리오에 따라 달라지기 때문에 빅 오 표기법으로 효율성을 정확하게 정의할 수 없으므로 N을 두 배열의 총 합으로 볼 수 없다.

이런 경우 한 배열의 크기를 N , 나머지 배열의 크기를 M으로 시간복잡도를 표현하는 수밖에 없다.

새로운 개념의 등장이다.

별개의 두 데이터 세트를 서로 곱해야 할 때 두 데이터 세트를 별개로 구분해야만 빅오 관점에서 효율성을 나타낼 수 있다.

다른 빅오 표기법보다는 유용성이 조금 떨어진다고 볼 수 있다.

O(N * M) 알고리즘을 N만 있는 알고리즘과 비교하는 것은 넌센스다.

하지만 O(N * M)이 속하는 특정 범위가 있음을 알 수 있다.

N과 M이 동등하면 O(N²)이며 두 데이터 중 하나의 데이터가 1만큼이라도 더 작은수라면 M에 할당함으로서 O(N)이 된다.
따라서 어떤 의미에서는 O(N * M)은 O(N)과 O(N²)의 사이 정도로 이해할 수 있다.

---

암호 크래커

당신은 누군가의 암호를 풀려는 해커다.
부르트 포스(brute force)방식으로 풀기로 하고 주어진 길이의 모든 문자열 조합을 생성하는 코드를 작성했다.

Brute Force (재귀함수)

function bruteForce(n) {
  const result = [];
  const characters = 'abcdefghijklmnopqrstuvwxyz';

  function generateStringHelper(currentString, length) {
    if (length === 0) {
      result.push(currentString);
    } else {
      for (let i = 0; i < characters.length; i++) {
        generateStringHelper(currentString + characters[i], length - 1);
      }
    }
  }

  generateStringHelper('', n);
  return result;
}

// 예시: n = 3인 경우
const strings = bruteForce(3);
console.log(strings); // ['aaa', 'aab', 'aac', ..., 'zzx', 'zzy', 'zzz']

generateStringHelper함수를 통해 result배열에는
['aaa', 'aab', 'aac', ..., aaz, aba, ..., 'zzx', 'zzy', 'zzz']의 순서로 문자열이 쌓인다.

for 문 내 재귀함수는 실행컨텍스트를 어느정도 이해하고 있어야 이해가 됩니다.

위 부르트포스를 빅 오 관점에서는 어떻게 나타낼까?

단순히 알파벳을 하나씩 출력하면 26단계가 걸린다.
두 글자짜리 조합을 전부 출력하면 문자 26개에 문자 26을 곱한 만큼 걸린다.
3글자의 조합은 26 * 26 * 26이다.

즉 위 알파벳을 모두 배열로 푸시하는 부르트포스의 방식은 O(26ᴺ)이다.

O(N²)조차 느린데, 정말 무시무시한 알고리즘이다.

심지어 O(2ᴺ)도 어느 시점부터는 O(N³)보다 느려지기 시작진다.
어떻게 보면 O(2ᴺ)은 O(logN)의 반대다. (이진 검색처럼) O(logN)인 알고리즘에서는 데이터가 두배로 늘어날 때 알고리즘에 한 단계씩 더 걸린다.
O(2ᴺ)알고리즘에서는 데이터가 한개 늘어날 때 알고리즘에 필요한 단계가 두 배로 늘어난다.

암호 크래커 예제에서 N이 1씩 늘어날 때마다 단계수는 26배씩 늘어나는 어마어마한 비효율이 일어난다. 그래서 브루트 포스로 암호를 해독하는 방법이 그토록 비효율적인 것이다.

---