홈으로

소프트웨어 기술(스타트업 위주)

알고리즘

자료구조, 알고리즘이 단기적으로 봤을 때는 안중요하다고 생각될 수도 있어요. 그리고 api 자체가 대부분 성능 최적화가 되어있는 third-party library 를 사용하는 경우가 많으니깐요.

근데 알고 있어야 문제가 생겼을 때 문제의 원인을 파악할 수 있어요. 모르고 그냥 써버리면 문제가 발생했을 때 문제의 원인이 어디서 발생했는지 알 수가 없어요.

또한 사용자 수가 많아지고 시스템 규모가 커질수록 알고리즘을 어떻게 설계했는가에 의해서 유지보수비용, 성능, 실제 매출과 직결되는 부분이 크다고 봐요.

사업을 장기적인 관점에서 봤을 때는 본질은 제품의 퀄리티인 것이에요. 영업, 마케팅도 굉장히 중요한데요. 제품의 품질이 받쳐주지 않으면 장기적으로 사업을 지속할 수 없다고 봐요. 제품의 퀄리티가 좋으면 타사대비 차별화가 생겨서 업계에 입소문이 나서 영업, 마케팅은 부산물로 따라올 테니깐요.

예를들어 1에서 100 까지 자연수의 합을 for 반복문을 통해서 출력값을 도출 할 수 있겠지만 n(n+1)/2 라는 공식을 사용하면 훨씬 성능적인 부분, 메모리 측면에서도 우수한 소스코드라고 평가할 수 있어요.

이런 것들이 누적이 되고 사용자 수가 많아질수록 엄청난 차이가 발생하겠죠? 1에서 100까지의 사용자의 합이 아니라 1에서 100만명 유저의 합을 구한다면 CPU가 100만번 일하고 있어야 되니깐요.

그리고 제조업의 물류시스템 같은 경우 관련 부품은 기본 몇천만건, 수억건이 DB에 저장되어 있는 경우가 대부분이에요. 그래서 기본 TB 이상의 저장소가 필요한데 돈으로 환산하면 수억원이 필요한 경우도 많아요. 여기서 알고리즘 최적화가 안되어 있으면 다달이 원인도 모르고 몇천만원이 밑빠진 독에 물붓는거 마냥 줄줄 세는거에요.

서버를 증설한다는게 메모리를 더 필요로 한다는 것이니 클라우드 서버에 돈을 더 지불해야 하는거구요, 해당 작업 위한 인건비 등등.. 무수히 많은 변수들이 있습니다.

근데 뭐 알고리즘이고 나발이고 일정이 급해서 그냥 빨리 만드는데 초점을 맞추는 경우도 많긴 합니다. 점진적으로 보완해 나가도 되긴 하고요. 결론적으로 전반적인 회사 상황에 잘 맞는 맞춤형 인재가 됩시다!

알고리즘 정리

1. Sorting (정렬)

1.1 Bubble Sort

물리적 정의

인접한 두 요소를 비교하여 크기 순서대로 정렬하는 방식으로, 가장 큰 요소가 오른쪽으로 점점 이동하는 방식이다.

특징

  • O(n²) 시간 복잡도 (최악, 평균)
  • 안정적인 정렬 방식
  • 작은 데이터셋에 적합
function bubbleSort(arr) {
  let n = arr.length
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

1.2 Selection Sort

물리적 정의

배열에서 가장 작은 요소를 찾아 첫 번째 위치에 놓고, 반복하여 정렬하는 방식이다.

특징

  • O(n²) 시간 복잡도
  • 불안정한 정렬 방식
  • 교환 횟수가 적음
function selectionSort(arr) {
  let n = arr.length
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  return arr
}

1.3 Insertion Sort

물리적 정의

Insertion Sort는 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 요소를 하나씩 적절한 위치에 삽입하여 정렬하는 알고리즘이다.

특징

  • 시간 복잡도: O(n^2) (최악 및 평균), O(n) (최선)
  • 공간 복잡도: O(1) (제자리 정렬, in-place)
  • 안정 정렬(Stable Sort)
  • 작은 데이터셋에서 효과적
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i]
    let j = i - 1
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = key
  }
  return arr
}
console.log(insertionSort([5, 3, 8, 4, 2]))

1.4 Heap Sort

물리적 정의

Heap Sort는 힙(Heap) 자료구조를 이용하여 정렬하는 알고리즘으로, 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성하여 요소를 정렬한다.

특징

  • 시간 복잡도: O(n log n) (최악, 평균, 최선)
  • 공간 복잡도: O(1) (제자리 정렬, in-place)
  • 불안정 정렬(Unstable Sort)
  • 비교 기반 정렬 알고리즘
function heapify(arr, n, i) {
  let largest = i
  let left = 2 * i + 1
  let right = 2 * i + 2
  if (left < n && arr[left] > arr[largest]) largest = left
  if (right < n && arr[right] > arr[largest]) largest = right
  if (largest !== i) {
    ;[arr[i], arr[largest]] = [arr[largest], arr[i]]
    heapify(arr, n, largest)
  }
}

function heapSort(arr) {
  let n = arr.length
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i)
  for (let i = n - 1; i > 0; i--) {
    ;[arr[0], arr[i]] = [arr[i], arr[0]]
    heapify(arr, i, 0)
  }
  return arr
}
console.log(heapSort([5, 3, 8, 4, 2]))

1.5. Quick Sort

물리적 정의

Quick Sort는 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘으로, 피벗(Pivot)을 선택하고 이를 기준으로 작은 값과 큰 값으로 분할하여 정렬한다.

특징

  • 시간 복잡도: O(n log n) (평균), O(n^2) (최악)
  • 공간 복잡도: O(log n) (재귀 호출 스택)
  • 불안정 정렬(Unstable Sort)
  • 실전에서 가장 빠른 정렬 중 하나
function quickSort(arr) {
  if (arr.length <= 1) return arr
  let pivot = arr[arr.length - 1]
  let left = arr.filter((el) => el < pivot)
  let right = arr.filter((el) => el > pivot)
  let middle = arr.filter((el) => el === pivot)
  return [...quickSort(left), ...middle, ...quickSort(right)]
}
console.log(quickSort([5, 3, 8, 4, 2]))

1.6. Merge Sort

물리적 정의

Merge Sort는 분할 정복 방식의 정렬 알고리즘으로, 배열을 반으로 나누고 각각 정렬한 후 병합(Merge)하여 최종 정렬된 배열을 만든다.

특징

  • 시간 복잡도: O(n log n) (최악, 평균, 최선)
  • 공간 복잡도: O(n) (추가 배열 필요)
  • 안정 정렬(Stable Sort)
  • 큰 데이터셋에서도 우수한 성능
function merge(left, right) {
  let sortedArr = []
  while (left.length && right.length) {
    if (left[0] < right[0]) sortedArr.push(left.shift())
    else sortedArr.push(right.shift())
  }
  return [...sortedArr, ...left, ...right]
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))
  return merge(left, right)
}
console.log(mergeSort([5, 3, 8, 4, 2]))

2. Recursion (재귀)

2.1 Tail Recursion (꼬리 재귀)

물리적 정의: 재귀 호출이 함수의 마지막 동작으로 이루어지는 경우를 의미하며, 컴파일러가 최적화할 수 있다.
특징:

  • 스택 메모리를 적게 사용
  • 반복문과 유사한 성능으로 동작 가능
function tailRecursiveFactorial(n, acc = 1) {
  if (n === 0) return acc
  return tailRecursiveFactorial(n - 1, acc * n)
}
console.log(tailRecursiveFactorial(5)) // 120

2.2 Non-Tail Recursion (비꼬리 재귀)

물리적 정의: 재귀 호출 후 추가적인 연산이 남아있는 경우를 의미하며, 최적화가 어렵다.
특징:

  • 깊은 재귀 호출 시 스택 오버플로우 발생 가능
  • 구현이 직관적이지만 성능 문제를 유발할 수 있음
function nonTailRecursiveFactorial(n) {
  if (n === 0) return 1
  return n * nonTailRecursiveFactorial(n - 1)
}
console.log(nonTailRecursiveFactorial(5)) // 120

3. Searching (검색)

물리적 정의: 배열의 요소를 처음부터 하나씩 확인하면서 값을 찾는 방법.
특징:

  • O(n) 시간 복잡도 (최악, 평균)
  • 정렬이 필요 없음
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i
  }
  return -1
}

물리적 정의: 정렬된 배열에서 중간 값을 기준으로 값을 비교하여 탐색하는 방법.
특징:

  • O(log n) 시간 복잡도
  • 정렬된 배열에서만 사용 가능
function binarySearch(arr, target) {
  let left = 0,
    right = arr.length - 1
  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) return mid
    else if (arr[mid] < target) left = mid + 1
    else right = mid - 1
  }
  return -1
}

4. Tree (트리)

4.1 Pre-Order Traversal (전위 순회)

물리적 정의: 노드를 방문할 때, 부모 노드를 먼저 방문한 후 왼쪽 자식, 그다음 오른쪽 자식을 방문하는 방식.
특징:

재귀 호출에서 부모 노드를 먼저 출력. 트리 구조를 복사하는 데 유용함. 깊이 우선 탐색(DFS) 방식의 한 종류.

function preOrder(node) {
  if (!node) return
  console.log(node.value)
  preOrder(node.left)
  preOrder(node.right)
}

4.2 In-Order Traversal (중위 순회)

물리적 정의: 왼쪽 자식을 먼저 방문하고, 부모 노드를 방문한 후, 오른쪽 자식을 방문하는 방식.
특징:

이진 탐색 트리(BST)에서 중위 순회를 수행하면 오름차순으로 정렬된 값을 얻을 수 있음. 탐색을 최적화하는 데 사용될 수 있음.

function inOrder(node) {
  if (!node) return
  inOrder(node.left)
  console.log(node.value)
  inOrder(node.right)
}

4.3 Post-Order Traversal (후위 순회)

물리적 정의: 트리 순회 방식 중 하나로, 왼쪽 자식 → 오른쪽 자식 → 부모 노드 순서로 방문하는 방식이다.

특징:

부모 노드를 방문하기 전에 모든 자식 노드를 먼저 방문한다. 트리의 구조를 제거하거나 정리하는 경우(예: 파일 시스템 삭제) 유용하다. 재귀적으로 구현할 경우 스택 오버플로우 가능성이 있으므로, 반복문을 활용한 구현도 고려할 수 있다.

function postOrder(node) {
  if (!node) return
  postOrder(node.left)
  postOrder(node.right)
  console.log(node.value)
}

5. 우선탐색

5.1 BFS (너비 우선 탐색)

물리적 정의: 그래프에서 시작 노드에서 가까운 노드부터 차례로 탐색하는 방법. 큐(Queue)를 이용하여 구현된다.
특징:

최단 경로 탐색에 유용하다. 방문한 노드를 다시 방문하지 않도록 관리해야 한다. 노드의 이웃을 모두 확인한 후 다음 깊이로 진행한다.

function bfs(graph, start) {
  let queue = [start]
  let visited = new Set()
  while (queue.length > 0) {
    let node = queue.shift()
    if (!visited.has(node)) {
      console.log(node)
      visited.add(node)
      queue.push(...graph[node])
    }
  }
}

5.2 DFS (깊이 우선 탐색)

물리적 정의: 그래프에서 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방식. 스택(Stack) 또는 재귀(Recursion)를 이용하여 구현된다.
특징:

백트래킹(Backtracking) 기법에서 자주 사용된다. 경로 탐색이나 순열, 조합 문제 해결에 유용하다. 그래프가 크면 스택 오버플로우 위험이 있다.

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return
  console.log(node)
  visited.add(node)
  for (let neighbor of graph[node]) {
    dfs(graph, neighbor, visited)
  }
}

6. Dijkstra's Algorithm (다익스트라 알고리즘)

물리적 정의
다익스트라 알고리즘은 가중 그래프에서 한 정점으로부터 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 우선순위 큐를 사용하여 가장 비용이 적은 정점부터 탐색하는 방식으로 동작한다.

특징
음수 가중치가 없는 그래프에서만 동작한다. (벨만-포드 알고리즘과 차이점) 우선순위 큐를 활용하면 O((V + E) log V) 의 시간 복잡도를 갖는다. 네트워크 라우팅, 지도 서비스 등에서 사용된다.

function dijkstra(graph, start) {
  let distances = {}
  let pq = new PriorityQueue()
  distances[start] = 0
  pq.enqueue([start, 0])
  while (!pq.isEmpty()) {
    let [node, distance] = pq.dequeue()
    for (let neighbor in graph[node]) {
      let newDist = distance + graph[node][neighbor]
      if (newDist < (distances[neighbor] || Infinity)) {
        distances[neighbor] = newDist
        pq.enqueue([neighbor, newDist])
      }
    }
  }
  return distances
}

7. Dynamic Programming (동적 프로그래밍)

물리적 정의
동적 프로그래밍(DP)은 큰 문제를 작은 하위 문제들로 나누고, 그 결과를 저장하여 반복 계산을 줄이는 기법이다. 재귀(Recursion)와 분할 정복(Divide & Conquer) 방식과 유사하지만, 중복된 계산을 줄이기 위해 메모이제이션(Memoization) 또는 테뷸레이션(Tabulation)을 활용한다.

특징
Overlapping Subproblems (중복 부분 문제): 동일한 부분 문제가 여러 번 계산됨.
Optimal Substructure (최적 부분 구조): 전체 최적해가 부분 문제의 최적해를 통해 구성됨.
메모이제이션(Memoization): 재귀 호출 결과를 저장하여 중복 연산을 방지함.
테뷸레이션(Tabulation): 하위 문제를 미리 계산하고 저장하여 문제를 해결함.
시간 복잡도 개선: 일반적인 재귀보다 빠르며, 보통 O(n) 또는 O(n²) 정도의 성능을 보장.

7.1 피보나치 수열 (메모이제이션)

function fib(n, memo = {}) {
  if (n <= 1) return n
  if (memo[n]) return memo[n]
  return (memo[n] = fib(n - 1, memo) + fib(n - 2, memo))
}

7.2 배낭 문제 (0/1 Knapsack)

function knapsack(weights, values, capacity) {
  let dp = Array(weights.length + 1)
    .fill(0)
    .map(() => Array(capacity + 1).fill(0))
  for (let i = 1; i <= weights.length; i++) {
    for (let w = 1; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1],
        )
      } else {
        dp[i][w] = dp[i - 1][w]
      }
    }
  }
  return dp[weights.length][capacity]
}
Previous
자료구조
Next
알고리즘(실습)