외워서 푸는 알고리즘 테스트

알고리즘 풀이 시 어느정도 외워두면 편한 패턴들이 있다. 코딩테스트 합격자 되기 도서를 참고하여 작성하였으며, 자바스크립트로 코딩테스트를 준비하는 분들이라면 해당 도서를 한번 쯤 읽어 봄직하다.

스택

• 선입후출(FILO)
• 최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋다.
• 가장 가까운(최근)이라는 키워드를 보면 스택을 떠올려 봐야 한다.

큐

• 선입선출(FIFO)
• 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용된다.
• 성능이 중요한 문제라면 큐를 직접 구현하거나 연결리스트를 직접 구현하여 푸는 것이 좋으나, 난이도가 높지 않다면 굳이 구현하지 않아도 통과할 수는 있다.

// 연결리스트
class Node {
  constructor(data) {
    this.data = data; // 요소의 값
    this.next = null; // 다음 요소를 참조
  }
}
class Queue {
  constructor() {
    this.head = null; // 첫 번째 요소 참조
    this.tail = null; // 마지막 요소 참조
    this.size = 0; // 큐의 길이
  }
  push(data) {
    // 새로운 요소를 생성
    const newNode = new Node(data);
    if (!this.head) {
      // 큐가 비어 있다면 head와 tail을 모두 새로 생성한 요소로 설정
      this.head = newNode;
      this.tail = newNode;
      //  아니면 현재 tail의 next 속성을 새로운 요소로 설정 후 tail이 새로운 요소를 참조하도      록 변경
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++; // 큐 길이 증가
  }
  pop() {
    // head가 null이라면 비어 있다는 뜻
    if (!this.head) {
      return null;
    }
    // 두 번째 요소를 head의 참조로 변경하면
    // 자연스럽게 첫 번째 요소가 사라짐
    const removeNode = this.head;
    this.head = this.head.next;
    // 만약 두 번째 요소가 없었다면
    // 큐가 비어 있다는 뜻이니 tail도 null로 설정
    if (!this.head) {
      this.tail = null;
    }
    this.size--; // 큐 길이 감소
    // 삭제된 요소의 값을 반환
    return removeNode.data;
  }

  isEmpty() {
    return this.size === 0;
  }
}

해시

• 해시 함수를 통해 키와 값으로 저장하여 빠른 데이터 탐색이 가능한 자료구조
• 단방향으로 동작하기 때문에 키를 통해 값을 찾을 수는 있지만 값을 통해 키를 찾을 수는 없다.
• 해시를 비교하는 함수도 O(n)이기 때문에 해시를 사용할 때라면 크게 문제가 되지 않는다.

이진 탐색

• 정렬된 배열은 이진탐색을 통해 시간복잡도를 O(logN)으로 낮출 수 있다.
• 배열의 절반을 나누어 중위 값이 목표값보다 크고 작은지를 비교하여 탐색한다.

function binarySearch(sortedArray, target) {
    let left = 0;
    let right = sortedArray.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (sortedArray[mid] === target) {
            return mid; // 찾은 경우 해당 인덱스 반환
        } else if (sortedArray[mid] < target) {
            left = mid + 1; // 왼쪽 포인터를 오른쪽으로 이동
        } else {
            right = mid - 1; // 오른쪽 포인터를 왼쪽으로 이동
        }
    }

    return -1; // 찾지 못한 경우 -1 반환
}

// 사용 예제
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 7;
const result = binarySearch(sortedArray, target);

if (result !== -1) {
    console.log(`타겟 값 ${target}은(는) 인덱스 ${result}에 있습니다.`);
} else {
    console.log("타겟 값을 찾지 못했습니다.");
}

그래프

DFS

깊이 탐색한 다음 되돌아오는 깊이 우선 탐색으로, 하나의 경로를 끝까지 시도해봐야 하는 문제에서 주로 사용된다.
DFS에서 시간초과가 발생한다면 BFS를, BFS에서 메모리 초과가 발생한다면 DFS를 시도해보는 것이 좋다.

function solution(graph, start) {
  const result = []
  const list = {};
  const visited = new Set();
  for (const [a, b] of graph) {
    list[a] = list[a] ? list[a].concat(b) : [b];
  }
  function dfs(node, visited, result) {
    visited.add(node); 
    result.push(node); 
    (list[node] || []).forEach((neighbor) => { 
    if (!visited.has(neighbor)) { 
      dfs(neighbor, visited, result);
    }
    });
  }
  dfs(start, visited, result);
  return result; 
}

BFS

넓게 탐색하며 진행하는 너비 우선 탐색으로, 최단거리를 찾아야 하는 문제에서 주로 사용된다.

/** 넓이 우선탐색 */
function solution(graph, start) {
  const result = [start]
  const list = {};
  const visited = new Set();
  for (const [a, b] of graph) {
    list[a] = list[a] ? list[a].concat(b) : [b];
  }

  const queue = [];
  queue.push(start);
  visited.add(start);
  while (queue.length) {
    const node = queue.shift();
    for (const target of list[node] || []) {
      if (!visited.has(target)) { 
        queue.push(target);
        visited.add(target);
        result.push(target);
        }
    }
  }

  console.log(result)
  return result;
}