📌 자료구조 기초

탐색과 자료구조

탐색: 많은 양의 데이터 중 원하는 데이터를 찾는 과정

자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조

스택(Stack)과 큐(Queue)

스택(Stack): 선입후출 / 후입선출

큐(Queue): 선입선출

자바스크립트에서의 큐(Queue) 구현

자바스크립트에서 shift() 를 이용한 큐(Queue) 구현은 O(1)보다 높은 시간복잡도를 가진다. 대부분의 코딩테스트에서는 크게 문제되지 않지만, 최적화를 위해서는 연결리스트 형태의 큐(참고)를 구현해야 한다.

재귀함수

• 자기 자신을 다시 호출하는 함수
• 재귀함수가 언제 끝날지 종료조건을 꼭 명시해야 한다.
• 컴퓨터 내부에서 재귀함수는 스택 자료구조를 이용한다.

function iterativeFactorial(n) { // 반복문
  let result = 1;
  for (let i = 1; i <= n; i++) result *= i
  return result
}

function recursiveFactorial(n) { // 재귀함수
  if (n <= 1) return 1
  else return n * recursiveFactorial(n - 1);
}

📌 탐색 알고리즘 DFS/BFS

graph 이미지

DFS

깊이 우선 탐색 알고리즘(최대한 멀리 있는 노드를 우선으로 탐색)

const graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
];
const visited = Array.from({ length: 9 }, isVisited => false);

function DFS(graph, v, visited) {
  visited[v] = true;
  console.log(v);
  for (let i of graph[v]) {
    !visited[i] && DFS(graph, i, visited)
  }
}
DFS(graph, 1, visited);

BFS

너비 우선 탐색(가까운 노드부터 탐색)

const graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7],
];
const visited = Array.from({ length: 9 }, isVisited => false);
function BFS(graph, start, visited) {
  const queue = [start];
  visited[start] = true;
  while (queue.length) {
    const v = queue.shift();
    console.log(v);
    for (let i of graph[v]) {
      !visited[i] && queue.push(i);
      visited[i] = true;
    }
  }
}
BFS(graph, 1, visited);

---

이코테 예제부터 프로그래머스 DFS/BFS 문제도 풀어보고는 있지만, 이전 코드를 참고하지 않고는 풀지 못하고 있다. 내 실력에 비해 문제가 어려운 것도 있겠지만, 계속되는 코드 실패를 보고 있으니 자존심이 많이 상한다. 이러다 울 것 같으니 백준에서 쉬운 DFS/BFS부터 차곡차곡 풀어봐야겠다😢