누구나 자료 구조와 알고리즘 #2

안광의·2022년 5월 12일

알고리즘 자료구조

자료구조와 알고리즘

목록 보기

2/7

5장 빅 오를 사용하거나 사용하 않는 코드 최적화

선택정렬

0번째 인덱스에 있는 값과 그 다음 값들을 비교하여 가장 작은 값과 0번째 인덱스의 값과 자리를 바꾼다.

1번 과정을 1번째, 2번째 ... n-1번째 인덱스(길이가 n인 배열)까지 반복한다.

// 선택 정렬 예시
function selectionSort(array) {
  for(let i = 0; i < array.length - 1; i++) {
      let lowestNumberIndex = i;
      for(let j = i + 1; j < array.length; j++) {
          if(array[j] < array[lowestNumberIndex]) { 
              lowestNumberIndex = j;
          } 
      }

      if(lowestNumberIndex != i) {
          let temp = array[i];
          array[i] = array[lowestNumberIndex]; 
          array[lowestNumberIndex] = temp;
      } 
  }
  return array;  
}

원소 N개가 있을 때 (N - 1) + (N - 2) + (N - 3) … + 1번의 비교가 일어나고 패스스루 당 최대 1번의 교환이 발생한다.

빅 오는 데이터가 늘어날때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하기 때문에 상수는 무시한다.
버블 정렬과 선택 정렬 모두 O(N2)이지만 버블 정렬은 선택 정렬보다 두 배 느리다. 같은 시간복잡도(Big O)를 가진 알고리즘이라도 어떤 알고리즘이 더 빠른지 분석해야 한다.

6장 긍정적인 시나리오 최적화

삽입 정렬
1. 1번째 인덱스의 값을 삭제하고 임시 변수에 저장한 후 0번째 인덱스(이전 인덱스)값과 비교하여 임시 변수에 있는 값이 더 작을 경우 0번째 인덱스 값을 비어있는 오른쪽으로 시프트하고 임시 변수의 값을 0번째 인덱스로 옮긴다.
2. 그 다음으로 2번째 인덱스의 값을 삭제하여 임시 변수에 저장하고 1번째 인덱스와 비교하여 임시 변수의 값이 더 작을 경우 1번째 값을 오른쪽으로 시프트, 이후 0번째 값(맨 앞의 인덱스)까지 비교하여 시프트 한다.
3. 위 패스스루 과정을 마지막 인덱스의 값까지 반복한다. 만약 마지막 인덱스의 값이 가장 작다면 마지막 패스스루에서 이전 값들이 한 칸씩 오른쪽으로 시프트하는 과정을 거치며 해당 값이 맨 앞으로 이동하게 된다.
```
//부트 캠프에서 풀었던 삽입 정렬 문제
//책의 설명과 다르게 기존 배열이 아니라 새로운 sorted 배열에 값을 추가하는 방식으로 구현
const insertionSort = function (arr) {
let sorted = [arr[0]];
for (let i = 1; i < arr.length; i++) {
  if (arr[i] >= sorted[i - 1]) {
    sorted.push(arr[i]);
  } else {
    for (let j = 0; j < i; j++) {
      if ((arr[i] <= sorted[j]) {
        const left = sorted.slice(0, j);
        const right = sorted.slice(j);
        sorted = left.concat(arr[i], right);
        break;
      }
    }
  }
}

return sorted;
};
```
- 삽입 정렬은 삭제, 비교 시프트 삽입 네 종류 단계의 연산으로 이루어진다
  - 비교 : N2/2(1 + 2 + 3 + ... + N-1)
  - 시프트 : N2/2(역순으로 정렬되어 있는 최악의 경우)
  - 삽입 : N-1번(패스스루 당 1번)
  - 삭제 : N-1번(패스스루 당 1번)
  - 총 : N2 + 2N - 2단계 => O(N2)
평균 비교
- 최악의 시나리오의 경우 선택 정렬이 삽입 정렬보다 빠르지만 여러 시나리오를 비교했을때는 결과가 달라진다. 최선의 시나리오(정렬된 배열), 평균 시나리오(절반이 정렬된 배열), 최악의 시나리오(역순)를 비교하면
  
  최선의 시나리오 평균 시나리오 최악의 시나리오
  선택 정렬 N2 / 2 N2 / 2 N2 / 2
  삽입 정렬 N N2 / 2 N2
  
  결과가 다르게 나오기 때문에 어느 정도 정렬된 데이터를 다룰 수 있는지 예상할 수 있다면 각각의 시나리오를 고려하여 정렬 알고리즘을 선택해야 한다.

	최선의 시나리오	평균 시나리오	최악의 시나리오
선택 정렬	N2 / 2	N2 / 2	N2 / 2
삽입 정렬	N	N2 / 2	N2

알고리즘 향상

// 두 배열의 교집합을 구하는 함수
function intersection(firstArray, secondArray){
  let result = [];

  for (let i = 0; i < firstArray.length; i++) {
      for (let j = 0; j < secondArray.length; j++) {
          if (firstArray[i] == secondArray[j]) {
              result.push(firstArray[i]);
          }
      }
  }
  return result;            
}
//break로 필요없는 비교 단계를 생략하여 개선
function intersection(firstArray, secondArray){
  let result = [];

  for (let i = 0; i < firstArray.length; i++) {
      for (let j = 0; j < secondArray.length; j++) {
          if (firstArray[i] == secondArray[j]) {
              result.push(firstArray[i]);
              break;
          }
      }
  }
  return result;            
}

두 배열의 교집합을 찾아내는 N2 단계의 함수에서 이미 같은 값을 찾아낸 경우에는 비교가 불필요하므로 break를 추가하여 단계를 줄였다.

7장 일상적인 코드 속 빅 오

짝수의 평균

//배열 내 짝수들의 평균을 구하는 함수
function averageOfEvenNumbers(array) {
  let sum = 0;
  let countOfEvenNumbers = 0
  array.forEach((number) => {
    if (number % 2 === 0) {
      sum += number;
      countOfEvenNumbers ++;
    }
  })
  return sum / countOfEvenNumbers
}

N번의 루프를 돌며 짝수의 경우 루프 당 세 단계, 홀수의 경우 루프당 한 단계, 루프 이전에 두 단계 이후에 한 단계로 최악의 경우(모두 짝수) 총 3N + 3 => 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;
}
//세 글자 짜리 모든 문자열 조합을 리턴하는 함수
function wordBuilder(array) {
  let collection = [];

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

중첩 루프를 사용하여 구현된 함수로 두 글자의 경우 O(N2), 세 글자의 경우 O(N3)의 시간복잡도를 가진다.

평균 섭씨 온도 구하기

//화씨 온도가 담긴 배열을 섭씨 온도로 변환하여 평균을 구하는 함수
function averageCelsius(fahrenheitReadings) {
  const celsiusNumbers = []
  fahrenheitReadings.forEach((fahrenheitReading) => {
    const celsiusConversion = (fahrenheitReading - 32) / 1.8
    celsiusNumbers.push(celsiusConversion)
  })

  let sum = 0
  celsiusNumbers.forEach((celsiusNumber) => {
   	sum += celsiusNumber
  })
 return sum / celsiuNumbers.length
}

섭씨 온도로 변환하는 루프 N과 합계를 구하는 루프 N단계 총 2N => O(N)의 시간복잡도를 가지는 함수이다.

의류 상표

//의류 품목의 사이즈를 리턴하는 함수
  function markInventory(clothingItems){
    const clothingOptions = []
    for (const item of clothingItems) {
      for (let size=1; size<6; size++;) {
        clothingOptions.push(item + " Size: " + String(size))
      }
    }
    return clothingOptions
  }

중첩 루프이지만 안쪽 루프는 5번만 고정적으로 실행되어 N2이 아닌 5N => O(N)의 시간복잡도를 가진다.

1 세기
```
function countOnes(outerArray) {
  let count = 0;
  for(const innerArray of outerArray) {
    for(const number of innerArray) {
      if (number === 1) count ++;
    }
  }
  return count
}
```
- 0과 1로 이루어진 이차원 배열을 입력받아 1의 개수를 반환하는 함수로 중첩 루프를 사용하여 1의 개수를 세지만 루프가 반복되는 횟수는 안쪽 배열들의 길이의 합으로 시간복잡도는 O(N)이다.

팰린드롬 검사기

function isPalindrome(string) {
  let leftIndex = 0;
  let rightIndex = string.length - 1;
  while (leftIndex < string.length / 2) {
    if (string[leftIndex] !== string[rightIndex]) {
      return false;
    }
    leftIndex++;
    rightIndex--;
  }
  return true;
}

팰린드롬(앞으로 읽으나 뒤로 읽으나 똑같은 단어 혹은 구절) 여부를 리턴하는 함수로 앞글자부터 중간에 도달할 때까지 맨 뒷자리 글자부터 그 앞글자 순서대로 비교하는 함수로 최악의 경우 N/2단계 => O(N)의 시간복잡도를 가진다.

모든 곱 구하기

//수 배열을 받아 몯느 두 숫자 조합의 곱을 반환하는 함수
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;
}

배열 내의 두 수의 모든 곱을 리턴하는 함수로 동일한 곱셈을 피하기 위해 내부 루프에서 j는 항상 i + 1부터 시작한다.
안쪽 루프는 N + (N -1) + (N -2) + ... + 1번 실행되며 총 N2 / 2 => O(N2)의 시간복잡도를 가진다.

//두 개의 배열을 받아 한 배열의 모든 수와 다른 한 배열의 모든 수의 곱을 리턴하는 함수
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;
}

이중 루프를 돌지만 각 배열의 길이에 따라 단계가 달라지기 때문에 O(N * M)으로 표현한다.

암호 크래커
```
def every_password(n)
  (("a" * n)..("z" * n)).each do |str|
    puts str
  end
end
```
- 변수 n으로 쓰일 수를 전달하면 해당 길이의 모든 알파벳의 조합을 리턴하는 함수로 n이 3이라면 'aaa', 'aab', 'aac' ... 'zzy', 'zzz'를 출력한다.
- N의 관점에서 보면 총 조합의 수는 26N으로 N이 1씩 늘어날때 마다 단계수는 26배씩 늘어나는 비효율적인 알고리즘이다.

마치며

이번에 정리한 내용은 알고리즘 예제를 바탕으로 시간복잡도를 분석하고 같은 시간복잡도라고 하더라도 시나리오에 따라 효율성이 달라질 수 있다는 것을 확인하였다. 이중 중첩 루프를 사용했다고 해서 반드시 N2이 아니고 입력되는 데이터에 따라 단계가 어떻게 변화하는지 파악해야 정확한 분석이 가능하다.

안광의

개발자로 성장하기

이전 포스트

누구나 자료 구조와 알고리즘 #1

다음 포스트