[알고리즘과 자료구조] 다양한 알고리즘의 시간 복잡도를 알아보자

📖 '누구나 자료구조와 알고리즘'책을 공부한 내용을 담고 있습니다.

7장. 일상적인 코드 속 빅 오

프로젝트에서 중요한 부분이 성능 최적화이다. 최적화하기 위해선 현재 코드가 얼마나 효율적인지 알아야 한다. 그래야 최적화가 필요한지를 알 수 있다. 이번 장에서는 최적화의 첫 단계, 코드 효율성을 측정하는 방식에 대해서 알아보자.

7-1. 짝수의 평균

다음 예제는 수 배열을 받아 모든 짝수의 평균을 반환한다. 빅 오 관점에서 어떻게 효율성을 나타낼까?
코드를 살펴보면, 여러 단계를 거쳐 최악의 상황에서 3N + 3 단계정도 걸린다. 하지만, 빅 오는 상수를 무시하기 때문에 O(N)이라고 부른다.

function average_of_even_numbers (array) {
	let sum = 0;
  	let count = 0;
  
  array.forEach(number => {
  	if (number % 2 === 0) {
    	sum += number;
      	count += 1
    }
  });
  
  return sum / count;
}

7-2. 단어 생성기

다음 예제는 문자 배열로부터 두 글자짜리 모든 문자열 조합을 모으는 알고리즘이다.
이중 for 문을 사용해서 배열 array의 길이만큼 반복한다. 각 원소를 N번의 루프를 돌기 때문에 N * N, 즉 O(N²)의 시간 복잡도를 갖는다.

만약 삼중 for 문이라면, N N N 단계가 걸리기 때문에 O(N³)이라고 표기한다.

function wordBuilder(array) {
	let collection = [];
  	
  	for(let i = 0; i<array.length; i++) {
    	for(let j = 0; j<array.length; j++) {
        	if (i !==j) {
            	collection.push(array[i] + array[j]);
            }
        }
    }
	return collection;
}

O(N³)와 O(N²)를 그래프로 비교해보면 O(N²)가 훨씬 빠르다는 것을 알 수 있다. O(N³)의 알고리즘을 O(N²)으로 바꾼다면 코드 최적화에서 큰 성과인 것이다.

7-3. 배열 예제

이번 예제에서는 배열에서 소규모 샘플을 취하는 함수를 생성한다. 다음 함수의 빅 오를 알아보자.

배열 array의 길이에 상관없이 항상 동일한 단계 수를 갖는다. 이 알고리즘은 O(1)이다.

function sample(array) {
	let first = array[0];
  	let middle = array[array.length / 2]
    let last = array[array.length - 1]
    
    return [first, middle, last]
}

7-4. 평균 섭씨 온도 구하기

다음 예제는 화씨 온도를 섭씨로 변환한 후 온도의 평균을 계산한다.
아래 코드에서 2개의 for문을 실행한다. 원소 개수 N만틈 순회하기 때문에 N + N, 2N단계 걸린다. 하지만 빅 오는 상수를 무시하므로 O(N)이라고 표기한다.

function average_celsius(fahrenheit_readings) {
  
  	// 섭씨 온도를 모으는 배열
	let celsisus_numbers = []
    
    // 읽은 값을 섭씨로 변환해 배열에 추가한다.
    fahrenheit_readings.forEach(value => {
    	let celsisus_conversion = (fahrenheit_reading - 32) / 1.8;
     	celsisus_numbers.push(celsisus_conversion)
      	
    })
   	// 섭씨 온도의 합을 구한다.
  	let sum = 0;
  	
  	celsisus_numbers.forEach(number => {
    	sum += number
    })
  	
  	// 평균을 반환한다.
  return sum / celsisus_numbers.length
}

7-5. 의류 상표

다음 예제는 의류 품목 배열을 받아 상표에 넣어야 할 텍스트를 생성한다. 이 알고리즘은 이중 for 문을 사용하긴 하지만, 2번째 for 문이 항상 5번 실행된다. 그렇기 때문에 총 5N 단계 실행돼서 O(N)이라고 표기한다.

function mark_inventory (clothing_items) {
	let clothing_options = []
    
    for (let item in clothing_items) {
    	for (let i = 1; i<6; i++) {
        	clothing_options.push(item + "Size:" + String(size))
        }
    }
  
  return clothing_options
}

7-6. 1세기

다음 함수는 중첩 배열에서 0과 1로 이뤄진 배열에서 1의 개수를 반환한다. 중첩 for 문을 사용해서 성급히 O(N²)이라고 판단할 수 있지만, 두 for 문은 각각 루프 횟수가 다르다. 내부 for 문에서 배열의 실제 N개의 수를 순회하기 때문에 O(N)의 시간 복잡도를 갖는다.

function count_ones(outer_array) {
	count = 0
  	
  	for (let inner_array of outer_array) {
    	for (let number of inner_array) {
        	if (number === 1) {
            	count += 1
            }
        }
    }
  
  return count
}

7-7. 팰린드롬 검사기

다음은 어떤 문자열이 팰린드롬인지 판단하는 함수다. 팰린드롬(palindrome)은 앞으로 읽으나 뒤로 읽으나 똑같은 단어 혹은 구절이다. 예를 들어, "racecar", "kayak", "deified" 같은 단어가 있다.

코드에서 while문이 문자열 중간에 도달할 때까지 실행되기 때문에 루프다 N / 2 단계 실행한다. 빅 오는 상수를 표기하지 않아 O(N)이다.

function isPalindrome(string) {
	// leftIndex를 인덱스 0에서 시작한다.
  	let leftIndex = 0
    // rightIndex를 배열의 마지막 인덱스에서 시작한다.
    let rightIndex = string.length - 1
    
    // leftIndex가 배열 중간에 도달할 때까지 순회한다.
    while (leftIndex < string.length / 2) {
    	// 왼쪽 문자와 오른쪽 문자가 일치하지 않으면 팰린드롬이 아니다.
      	if (string[leftIndex] !== string[rightIndex]) {
        	return false
        }
      
      // leftIndex를 오른쪽으로 한 칸 옮긴다.
      leftIndex += 1
      rightIndex -= 1
    }
  
  // 불일치하는 문자 없이 전체 루프를 통과했으면 팰린드롬이다. 
  return true
}

7-8. 모든 곱 구하기

다음 예제는 배열의 모든 수를 두 숫자의 곱을 반환하는 알고리즘이다. 아래 코드에서 이중 for 문을 사용하는데, 첫 번째 for 문은 배열의 모든 수만큼 루프를 실행하고, 두 번째 for 문은 (N - 1) + (N - 2) +∙∙∙+ 1번 실행한다. 총 N + (N - 1) + (N - 2) +∙∙∙+ 1 번 루프가 발생한다.

function twoNumberProducts(array) {
	let products = []
    
    for (let i = 0; i < array.length - 1; i++) {
    	for (let j = i + 1; j < array.length; j++) {
        	products.push(array[i] * array[j])
        }
    }
  
  return products
}

이건 N² / 2 단계 발생한다고 볼 수 있다. 빅 오로 O(N²)으로 표기한다.

• 8²의 칸에서 8² / 2 단계가 실행된다.

o	o	o	o	o	o	o	o
o	o	o	o	o	o	o
o	o	o	o	o	o
o	o	o	o	o
o	o	o	o
o	o	o
o	o
o

여러 데이터 세트 다루기

만약 한 개의 배열의 모든 두 수의 곱을 계산하는 대신 한 배열의 모든 수와 다른 한 배열의 모든 수의 곱을 계산하면 어떻게 될까

두 배열의 길이가 같다면, O(N²)이지만, 길이가 다르다면, O(N)이 된다. O(N * M)을 O(N)과 O(N²) 사이의 시간 복잡도를 갖는다고 이해할 수 있다.

function twoNumberProducts(array1, array2) {
	let products = []
    
    for (let i = 0; i < array1.length; i++) {
    	for (let j = 0; j< array2.length; j++) {
        	products.push(array1[i] * array2[j])
        }
    }
  
  return products
}

7-9. 암호 크래커

다음 예제는 브루트 포스(brute force) 방식으로 주어진 길이의 모든 문자열 조합을 생성하는 코드를 작성한다. a부터 z까지의 알파벳으로 가능한, 길이가 n인 문자열을 생성한다.

• 루비로 구현한 코드

def every_password(n)
  ('a' * n..'z' * n).each do |str|
    puts str
  end
end

알파벳으로 조합해서 길이 n인 문자를 만들면 다음 표와 같다. 문자의 길이가 n일 때, 총 조합 수는 26ⁿ이다. 따라서 빅 오 표기법으로는 O(26ⁿ)이다.

암호 크래커 예제에서 문자 길이가 1씩 늘어날 때마다 단계 수가 26배씩 늘어난다. 브루트 포스로 암호를 해독하는 방법은 매우 비효율적이다.

길이	조합
1	26
2	26²
3	26³
4	26⁴