코딩 테스트 개요 및 문제 풀이를 위한 자바스크립트 문법 05

이 글은 네이버 블로그에 2024년 2월 4일에 올렸던 것을 그대로 옮겨온 것입니다.

투포인터 알고리즘 (Two Pointer Algorithm)

투포인터 알고리즘은 주로 배열이나 리스트에서 두 개의 포인터를 이용하여 문제를 해결하는 방법입니다. 이 알고리즘은 주로 정렬된 배열에서 두 수의 합, 최대 부분합, 연속된 데이터의 특징을 찾을 때 유용합니다.

기본 개념: 배열이 정렬되어 있다고 가정할 때, 시작점과 끝점 두 포인터를 이용해 범위를 조정하면서 문제를 해결합니다.

예제: 주어진 배열에서 합이 특정 값에 해당하는 두 요소의 인덱스를 찾는 문제

function twoPointer(arr, target) {
  let start = 0;
  let end = arr.length - 1;

  while (start < end) {
    let sum = arr[start] + arr[end];

    if (sum === target) {
      return [start, end];
    } else if (sum < target) {
      start++;
    } else {
      end--;
    }
  }

  return [-1, -1]; // 찾지 못했을 때
}

다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍은 복잡한 문제를 여러 개의 작은 문제로 나누어 해결하는 방법입니다. 각 작은 문제의 결과를 저장해두고, 이를 이용하여 큰 문제를 해결합니다. 이 방법은 중복된 계산을 줄이기 때문에 많은 문제를 더 빠르게 해결할 수 있게 해줍니다.

기본 개념: 큰 문제를 작은 문제로 나누고, 작은 문제의 해답을 저장해 두었다가 재사용합니다.

예제: 피보나치 수열

function fibonacci(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 2) return 1;

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

누적합 알고리즘 (Prefix Sum Algorithm)

누적합 알고리즘은 배열의 특정 구간의 합을 빠르게 구할 수 있는 방법입니다. 이를 위해 배열의 시작부터 각 위치까지의 합을 저장하는 새로운 배열을 만듭니다. 이후 구간의 합은 이 배열을 이용하여 쉽게 구할 수 있습니다.

기본 개념: 배열의 각 위치까지의 합을 미리 계산해두고, 이를 이용하여 구간의 합을 빠르게 구합니다.

예제: 배열에서 구간 [i, j]의 합을 구하는 문제

function prefixSum(arr) {
  let prefixSumArray = Array(arr.length).fill(0);
  prefixSumArray[0] = arr[0];

  for (let i = 1; i < arr.length; i++) {
    prefixSumArray[i] = prefixSumArray[i - 1] + arr[i];
  }

  return prefixSumArray;
}

function rangeSum(prefixSumArray, i, j) {
  if (i === 0) return prefixSumArray[j];
  return prefixSumArray[j] - prefixSumArray[i - 1];
}