74일차 TIL (면접 카타 7일)

13. DFS와 BFS의 차이를 말해주세요

기본 개념
DFS(Depth-First Search, 깊이 우선 탐색)

그래프의 한 노드에서 출발하여 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 뒤로 돌아가면서 탐색하는 방식.
재귀(Recursion) 또는 **스택(Stack)**을 이용해 구현 가능.
BFS(Breadth-First Search, 너비 우선 탐색)

시작 노드에서 가까운 노드부터 탐색하는 방식으로, 모든 이웃 노드를 먼저 방문한 후 다음 레벨로 이동.
**큐(Queue)**를 이용해 구현.

// DFS (스택을 사용한 구현)
function dfs(graph: number[][], start: number) {
  const stack = [start];
  const visited = new Set<number>();

  while (stack.length > 0) {
    const node = stack.pop()!;
    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      for (const neighbor of graph[node]) {
        stack.push(neighbor);
      }
    }
  }
}

// BFS (큐를 사용한 구현)
function bfs(graph: number[][], start: number) {
  const queue = [start];
  const visited = new Set<number>();

  while (queue.length > 0) {
    const node = queue.shift()!;
    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      for (const neighbor of graph[node]) {
        queue.push(neighbor);
      }
    }
  }
}

 

DFS(깊이 우선 탐색)는 한 경로를 끝까지 탐색한 후 되돌아오는 방식이며, 스택 또는 재귀를 사용해 구현합니다. 반면 BFS(너비 우선 탐색)는 시작점에서 가까운 노드부터 탐색하며, 큐를 사용해 구현합니다.
DFS는 백트래킹이 필요한 퍼즐 문제에서 유용하고, BFS는 최단 경로 탐색(예: 네비게이션)에서 많이 사용됩니다.

 

 

---

14. Array과 LinkedList를 비교설명해주세요.

 

개념
배열(Array)

연속적인 메모리 공간에 저장되는 데이터 구조.
인덱스를 통해 O(1) 시간 복잡도로 접근 가능.
크기가 고정적이거나 동적 배열(예: JavaScript의 Array)처럼 크기를 조절할 수 있음.
연결 리스트(Linked List)

**노드(Node)와 포인터(Next)**로 구성된 데이터 구조.
노드는 데이터와 다음 노드를 가리키는 포인터를 가짐.
연속적인 메모리가 필요하지 않으며, 크기가 동적으로 조절됨.

언제 사용해야 할까?
배열(Array)을 선택할 때

데이터 크기가 고정되어 있을 때
인덱스를 통해 빠르게 접근해야 할 때 (예: arr[i])
캐시 효율이 중요한 경우 (연속된 메모리 할당)
연결 리스트(Linked List)를 선택할 때

데이터 크기가 동적으로 변할 가능성이 있을 때
삽입/삭제가 빈번할 때 (예: 큐, 스택 구현)
중간 삽입/삭제가 필요할 때 (포인터 변경만 하면 됨)

// 배열 (Array) 예제
const arr: number[] = [1, 2, 3, 4, 5];
console.log(arr[2]); // O(1) - 인덱스를 통한 빠른 접근
arr.splice(2, 0, 99); // O(N) - 중간 삽입 비용 발생
console.log(arr);

// 단일 연결 리스트 (Linked List) 예제
class Node {
  value: number;
  next: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class LinkedList {
  head: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
}

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);

 

배열은 연속적인 메모리 공간을 사용해 O(1)로 빠르게 접근할 수 있지만, 크기 변경이 어렵고 삽입/삭제가 O(N)입니다. 반면 연결 리스트는 동적 크기 조절이 가능하며 삽입/삭제가 O(1)로 빠르지만, 인덱스로 접근하려면 O(N)이 걸립니다. 따라서 빠른 랜덤 접근이 필요하면 배열을, 삽입/삭제가 빈번하면 연결 리스트를 사용하는 것이 적절합니다.