JavaScript 알고리즘 & 자료구조 마스터클래스 2

애너그램

애너그램은 두 문자열이 서로 다른 문자의 순서는 다르지만 같은 문자로 이루어져 있는 것을 의미한다.

애너그램의 조건

두 문자열의 길이가 같아야 한다.
같은 문자를 같은 개수만큼 포함해야 한다.
문자들의 순서는 달라도 상관없다.

애너그램 예시

"listen" → "silent" // ✅ (애너그램)
"hello" → "holle"   // ✅ (애너그램)
"apple" → "aplee"   // ❌ (애너그램 아님, 'p' 개수가 다름)

애너그램 판별 알고리즘

애너그램인지 확인하는 방법은 여러가지가 있지만 정렬을 이용한 방법과 해시맵(딕셔너리를) 이용한 방법이 있다.

해시맵(딕셔너리)을 이용한 방식

function validAnagram(string1, string2) {
  // 두 문자열의 길이가 다르면 애너그램이 아니므로 false를 반환한다.
  if (string1.length !== string2.length) return false;
 
  const stringMap = {};
 
  for (const char of string1) {
    stringMap[char] = (stringMap[char] || 0) + 1; // 해당 문자열이 있다면 1을 더하고 없다면 1을 넣는다.
  }
 
  for (const char of string2) {
    // 해당 문자열이 없다면 애너그램이 아니므로 false를 반환한다.
    if (!stringMap[char]) {
      return false;
    } else {
      // 해당 문자열의 개수를 1 감소시킨다.
      stringMap[char] -= 1;
    }
  }
 
  return true;
}
 
validAnagram("", ""); // true
validAnagram("aaz", "zza"); // false
validAnagram("anagram", "nagaram"); // true
validAnagram("rat", "car"); // false) // false
validAnagram("awesome", "awesom"); // false
validAnagram("amanaplanacanalpanama", "acanalmanplanpamana"); // false
validAnagram("qwerty", "qeywrt"); // true
validAnagram("texttwisttime", "timetwisttext"); // true

결론

문자열의 길이가 짧으면 정렬 방식을 사용하는게 좋고 길이가 길면 해시맵 방식이 더 효율적이다.

다중 포인터 패턴

특정 조건에 따라 배열이나 문자열 내에서 포인터를 이동시켜 문제를 해결하는 방법이다.

다중 포인터 패턴의 개념

인덱스나 위치에 해당하는 포인터(참조 값)를 생성한다.
특정 조건에 따라 포인터를 이동시킨다.
- 시작 지점 → 끝 지점
- 끝 지점 → 시작 지점
- 중앙에서 양쪽으로 이동
보통 한 쌍의 값을 찾는 데 사용된다.

이중 루프 사용

첫 번째 숫자를 선택하고, 두 번째 숫자를 찾아 0이 되는지 확인
배열 크기가 커질수록 비효율적 (시간 복잡도 O(n²))

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

슬라이딩 윈도우 패턴

슬라이딩 윈도우란?

특정 조건에 따라 배열이나 문자열 내에서 윈도우를 이동시켜 문제를 해결하는 방법이다.

슬라이딩 윈도우 구현해보기

초기 윈도우(첫 n개 요소)의 합을 계산.
윈도우를 한 칸씩 이동하며 이전 요소를 빼고 새로운 요소를 추가.
최대 합을 갱신하며 전체 배열을 한 번만 순회.

function maxSubarraySum(arr, num) {
  if (arr.length < num) return null;
 
  let maxSum = 0;
  let tempSum = 0;
 
  // 초기 윈도우 합 계산
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
 
  // 윈도우를 이동하며 최대 합 계산
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
 
  return maxSum;
}
 
// 테스트
console.log(maxSubarraySum([6, 9, 2, 1, 8, 5, 6], 3)); // 19

슬라이딩 윈도우의 장점

중첩 루프 없이 한 번의 순회로 해결 → O(n)
대량 데이터 처리에 유용
빼고 더하는 방식으로 불필요한 연산 최소화

재귀 함수

재귀의 정의

재귀(Recursion)는 자기 자신을 호출하는 함수나 절차를 의미함.
자바스크립트에서 재귀는 특정 함수가 자기 자신을 호출하는 방식으로 구현됨.

재귀가 중요한 이유

재귀는 모든 곳에서 사용됨: 많은 프로그래밍 문제에서 자연스럽게 등장함.
이미 사용하고 있을 가능성 높음: 예를 들어 JSON.parse나 JSON.stringify 같은 함수들은 내부적으로 재귀를 활용할 수 있음.
복잡한 데이터 구조에서 유용: 트리 구조(예: DOM, JSON)나 그래프 순회에 사용됨.

재귀의 예시

JSON 파싱 (JSON.parse)
- JSON 데이터를 객체로 변환할 때 내부적으로 재귀를 활용하는 경우가 많음.
DOM 탐색 (document.getElementById)
- 웹페이지의 요소를 찾거나 순회할 때 재귀적인 방식으로 접근할 수 있음.
트리 및 그래프 순회
- 데이터 구조를 탐색할 때 반복문보다 재귀가 더 직관적이고 간결한 코드 작성이 가능함.

재귀와 무한 루프의 차이

재귀는 종료 조건(Base Case)이 필요함. 종료 조건이 없으면 무한 루프처럼 계속 실행됨.
예를 들어, 함수에서 자기 자신을 호출하되, 점점 더 작은 리스트를 입력으로 전달하여 결국 종료되도록 설계해야 함.

반복(Iteration) vs. 재귀(Recursion)

때로는 반복문 보다 재귀가 더 직관적이고 깔끔하다.

트리 순회처럼 계층적 구조를 다룰 때 재귀가 코드의 가독성을 높임.
하지만 재귀 없이 구현할 수도 있음. 상황에 따라 선택하는 것이 중요.

JavaScript 알고리즘 & 자료구조 마스터클래스 2

On this page