알고리즘 풀기 전 알아두면 좋은 것들

1. 시간 복잡도란?

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 데이터 크기와 관련하여 수학적으로 표현한 것이다. 이를 통해 코드가 얼마나 효율적으로 작동하는지 예측할 수 있다. 시간 복잡도는 일반적으로 데이터 크기(n)에 따라 알고리즘이 수행해야 하는 연산의 횟수를 나타낸다.

2. 빅오 표기법

시간 복잡도를 표현할 때 주로 사용하는 방법이다. 최악의 경우 실행 시간을 표현하며, 특정 알고리즘이 대규모 데이터에서도 얼마나 잘 작동하는지 평가하는 데 사용된다.

 

O(1) - 상수 시간

O(1)은 입력 데이터 크기와 관계없이 항상 일정한 시간 내에 실행된다. 즉, 몇 개의 데이터가 들어오든지 간에 같은 실행 시간이 걸린다. 상수 시간 복잡도를 가지는 알고리즘은 일반적으로 데이터에 접근하거나 단일 계산을 수행하는 경우에 발생한다.

function constantTime(arr) {
  return arr[0];
}

배열의 첫 번째 요소에 접근하거나 변수에 값을 할당할 때 등등 O(1)의 시간이 걸린다.

 

O(log n) - 로그 시간

O(log n)은 입력 데이터가 증가할 때, 증가율이 매우 완만한 알고리즘이다. 입력 데이터 크기가 2배가 되면 실행 시간이 1회만 더 증가하는 패턴이다. 로그 시간 복잡도는 주로 데이터를 절반씩 분할하여 처리하는 알고리즘에서 나타난다.

ex) 이진탐색

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

이진탐색은 정렬된 배열에서 중간 값을 선택하고, 찾고자 하는 값이 더 작으면 왼쪽 부분만, 더 크면 오른쪽 부분만 탐색하는 방식이다. 매번 데이터의 절반을 버리기 때문에 O(log n)의 시간이 걸린다.

 

O(n) - 선형 시간

O(n)은 입력 데이터의 크기에 비례하여 실행 시간이 증가한다. 입력이 2배가 되면 실행 시간도 2배로 늘어난다. 선형 시간은 일반적으로 데이터를 처음부터 끝까지 한 번씩 순차적으로 처리하는 경우에 나타난다.

ex) 순차탐색

function sequentialSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

순차탐색은 배열에서 값을 찾기 위해 처음부터 끝까지 하나씩 탐색하는 방법이다. 데이터가 n개일 경우, 최악의 경우에는 n번의 탐색이 필요하므로 O(n)의 시간이 걸린다.

 

O(n log n) - 로그 선형 시간

O(n log n)은 n개의 데이터를 처리하면서 각 단계에서 로그 시간만큼의 작업을 추가로 수행할 때 발생한다. 이 복잡도는 보통 효율적인 정렬 알고리즘에서 나타난다.

ex) 병합 정렬

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

병합 정렬은 배열을 반으로 나눈 후, 각각을 재귀적으로 정렬한 다음 다시 병합하는 방식이다. 데이터를 분할하는 데 O(log n)의 시간이 걸리고, 분할된 데이터를 병합하는 데 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n log n)가 된다.

 

O(n^2) - 이차 시간

O(n^2)은 데이터가 많아질수록 시간이 제곱으로 증가한다. 즉, 입력 크기가 2배가 되면 실행 시간이 4배가 되고, 3배가 되면 9배가 된다. 이차 시간 복잡도는 일반적으로 중첩된 루프에서 발생한다.

ex) 버블 정렬

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

버블 정렬은 배열에서 인접한 두 요소를 비교하고, 잘못된 순서일 경우 서로 교환하는 방식으로 배열을 정렬한다. 배열의 모든 요소를 여러번 반복하여 비교해야 하므로 O(n^2)의 시간이 소요된다.

이 외에도 선택 정렬, 삽입 정렬과 같은 기본적인 정렬 알고리즘은 O(n^2)의 시간 복잡도를 가진다.

 

O(2^n) - 지수 시간

O(2^n)은 데이터가 늘어날 때 실행 시간이 매우 빠르게 증가한다. 데이터가 하나 추가될 때마다 실행 시간이 2배로 증가하는 방식이다. 데이터가 늘어날수록 비효율적이기 때문에 대규모 데이터를 처리하는 데 적합하지 않다.\

ex) 피보나치수열

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

재귀적으로 피보나치 수열을 계산할 때, 동일한 값이 여러 번 계산되기 때문에 시간이 지수적으로 증가한다. 이처럼 재귀적으로 문제를 해결하는 경우, 최적화하기 위해 메모이제이션과 같은 방법을 사용해야 한다.

 

O(n!) - 팩토리얼 시간

O(n!)은 데이터가 늘어날 때, 실행 시간이 매우 빠르게 증가하는 알고리즘이다.

ex) 순열, 조합

function generatePermutations(arr) {
  const result = [];

  function permute(currArr, m = []) {
    if (currArr.length === 0) {
      result.push(m);
    } else {
      for (let i = 0; i < currArr.length; i++) {
        let current = currArr.slice();
        let next = current.splice(i, 1);
        permute(current, m.concat(next));
      }
    }
  }

  permute(arr);
  return result;
}

n개의 요소를 나열하는 모든 순열을 계산하려면 O(n!)의 시간이 소요된다. 이는 n!이 매우 빠르게 증가하기 때문에, 데이터가 조금만 많아져도 성능이 급격히 저하된다.

3. 공간 복잡도란?

공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타낸다. 공간 복잡도 역시 빅오 표기법을 통해 표현되며, 추가적인 데이터 구조나 변수 사용이 메모리 요구량에 영향을 미친다.

// O(1) 공간 복잡도: 추가 메모리를 거의 사용하지 않음
function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

// O(n) 공간 복잡도: 입력 배열을 복사하여 새로운 배열을 만듦
function doubleArray(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

4. 자료 구조

자료 구조는 데이터의 저장 방식과 처리 방식을 정의한다. 각 자료 구조는 특정한 장점과 단점을 가지고 있으며, 적절한 자료 구조를 선택하는 것은 알고리즘 성능 최적화에 매우 중요하다.

 

배열(Array)

배열은 고정된 크기의 연속된 메모리 공간에 데이터를 저장하며 인덱스를 통해 요소에 빠르게 접근할 수 있다.

배열은 데이터 접근이 빠르지만(인덱스를 사용해 O(1) 시간 안에 원하는 요소를 찾기 등) 크기가 고정되어 있어 크기 조정이 필요하거나 배열 중간에 삽입/삭제가 있을 때는 O(n)의 시간이 걸린다는 단점이 있다.

const arr = [1, 2, 3, 4, 5];

// 배열에서의 요소 접근: O(1)
console.log(arr[2]); // 3

// 배열에 요소 삽입 (중간 삽입): O(n)
arr.splice(2, 0, 10); // [1, 2, 10, 3, 4, 5]

연결 리스트(Linked List)

연결 리스트는 각 요소가 다음 요소를 가리키는 노드로 연결된 자료 구조이다. 노드는 값과 포인터로 구성된다.

연결 리스트는 중간에 삽입/삭제가 빠르고(O(1)) 배열과 달리 크기가 동적이므로 크기 제한이 없다. 하지만 첫 번째 노드부터 순차적으로 탐색해야 하기 때문에 임의의 요소에 접근하는 데 시간이 많이 걸린다(O(n)).

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  // 리스트의 맨 앞에 요소 삽입: O(1)
  insertFirst(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }

  // 리스트의 요소 탐색: O(n)
  find(value) {
    let current = this.head;
    while (current !== null) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }
}

const list = new LinkedList();
list.insertFirst(1); // [1]
list.insertFirst(2); // [2, 1]
console.log(list.find(1)); // Node { value: 1, next: null }

스택(Stack)과 큐(Queue)

스택은 LIFO(Last In First Out) 원칙을 따르는 자료 구조로, 마지막에 들어간 요소가 먼저 나온다.

큐는 FIFO(First In First Out) 원칙을 따르는 자료 구조로, 먼저 들어간 요소가 먼저 나온다.

둘 다 삽입과 삭제는 O(1) 시간에 이루어진다.

class Stack {
  constructor() {
    this.items = [];
  }

  // 스택에 요소 추가: O(1)
  push(element) {
    this.items.push(element);
  }

  // 스택에서 요소 제거: O(1)
  pop() {
    return this.items.pop();
  }
}

const stack = new Stack();
stack.push(10); // [10]
stack.push(20); // [10, 20]
stack.pop();    // 20 (LIFO 방식)

// 큐 예시
class Queue {
  constructor() {
    this.items = [];
  }

  // 큐에 요소 추가: O(1)
  enqueue(element) {
    this.items.push(element);
  }

  // 큐에서 요소 제거: O(1)
  dequeue() {
    return this.items.shift();
  }
}

const queue = new Queue();
queue.enqueue(10); // [10]
queue.enqueue(20); // [10, 20]
queue.dequeue();   // 10 (FIFO 방식)

트리 (Tree)

트리는 계층 구조를 이루며, 부모-자식 관계로 노드들이 연결된다. 이진 탐색 트리(BST)와 같은 트리 구조는 정렬된 데이터를 빠르게 찾을 수 있다.

트리는 검색, 삽입, 삭제가 평균적으로 O(log n)이 걸리지만, 트리가 균형을 이루지 못할 경우, 시간 복잡도가 O(n)이 될 수도 있다.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // 트리에 값 삽입: O(log n)
  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);

해시 테이블(Hash Table)

해시 테이블은 데이터를 키-값 쌍으로 저장하며, 해시 함수를 이용해 인덱스를 계산하여 빠르게 데이터를 찾는다.

평균적으로 O(1)의 시간 복잡도로 삽입, 삭제, 검색이 가능하지만, 충돌이 발생하면 성능이 저하될 수 있으며, 최악의 경우 시간 복잡도가 O(n)이 될 수 있다.

class HashTable {
  constructor(size) {
    this.table = new Array(size);
  }

  // 간단한 해시 함수
  hash(key) {
    return key % this.table.length;
  }

  // 데이터 삽입: O(1)
  set(key, value) {
    const index = this.hash(key);
    this.table[index] = value;
  }

  // 데이터 검색: O(1)
  get(key) {
    const index = this.hash(key);
    return this.table[index];
  }
}

const hashTable = new HashTable(50);
hashTable.set(5, 'Hello');
console.log(hashTable.get(5)); // "Hello"

그래프(Graph)

그래프는 정점과 간선으로 이루어진 자료 구조로, 네트워크를 표현하는 데 유용하다. DFS(깊이 우선 탐색), BFS(너비 우선 탐색)와 같은 탐색 알고리즘이 적용된다.

복잡한 관계를 표현하는 데 적합하지만 그래프의 밀도에 따라 탐색이 느려질 수 있다.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  // 깊이 우선 탐색: O(V + E)
  DFS(start) {
    const stack = [start];
    const result = [];
    const visited = {};
    visited[start] = true;

    while (stack.length) {
      const vertex = stack.pop();
      result.push(vertex);

      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }

    return result;
  }
}

const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
console.log(graph.DFS('A')); // ["A", "C", "B"]

5. 성능 최적화

캐싱(Caching), 메모이제이션(Memoization)

캐싱은 동일한 계산을 반복하는 대신, 이전에 계산한 결과를 저장해두고 필요할 때 재사용하는 방법이다.

// 함수의 결과를 캐싱하는 객체
const cache = {};

// 캐싱을 활용한 피보나치 수열
function fibonacci(n) {
  if (n <= 1) return n;

  // 캐시에 저장된 값이 있으면 그것을 반환
  if (cache[n]) return cache[n];

  // 값을 계산하고 캐시에 저장
  const result = fibonacci(n - 1) + fibonacci(n - 2);
  cache[n] = result;

  return result;
}

console.log(fibonacci(10)); // 55 (캐싱을 통해 성능 최적화)

메모이제이션은 재귀적 알고리즘에서 중복된 하위 문제를 다시 계산하는 것을 피하기 위해 결과를 저장해 두는 방식이다.

function memoizedFibonacci() {
  const memo = {};

  function fib(n) {
    if (n <= 1) return n;

    // 메모된 값이 있으면 반환
    if (memo[n]) return memo[n];

    // 값을 계산하고 메모에 저장
    const result = fib(n - 1) + fib(n - 2);
    memo[n] = result;

    return result;
  }

  return fib;
}

const fib = memoizedFibonacci();
console.log(fib(10)); // 55 (메모이제이션으로 성능 최적화)

동적 계획법(Dynamic Programming)

동적 계획법은 중복된 계산을 피하기 위한 최적화 기법으로, 하위 문제의 결과를 저장하여 이후에 재사용하는 방식이다.

• 탑다운 방식 - 큰 문제를 작은 문제로 나누어 해결하며, 각 하위 문제의 결과를 저장하여 중복 계산을 피한다.  

function fibTopDown(n, memo = {}) {
  if (n <= 1) return n;

  if (memo[n]) return memo[n]; // 메모된 결과 사용

  memo[n] = fibTopDown(n - 1, memo) + fibTopDown(n - 2, memo); // 결과 메모
  return memo[n];
}

console.log(fibTopDown(10)); // 55

• 바텀업 방식 - 작은 문제부터 해결하여 그 결과를 차곡차곡 쌓아 큰 문제를 해결한다. 재귀를 사용하지 않고, 반복문을 통해 문제를 풀기 때문에 메모리 및 성능에서 유리한 경우가 많다.

function fibBottomUp(n) {
  if (n <= 1) return n;

  let prev1 = 0, prev2 = 1;

  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev1 = prev2;
    prev2 = current;
  }

  return prev2;
}

console.log(fibBottomUp(10)); // 55 (동적 계획법으로 성능 최적화)

병렬 처리(Parallel Processing)

큰 데이터나 복잡한 연산을 처리할 때는 여러 작업을 병렬로 처리하는 것이 효율적이다. Javascript에서는 Web Worker나 Promise를 사용해 비동기적으로 여러 작업을 병렬로 처리할 수 있다.

const promise1 = fetch('/data1');
const promise2 = fetch('/data2');

Promise.all([promise1, promise2]).then((responses) => {
  // 두 작업을 병렬로 처리한 후 결과를 사용
});