HHyo814
발행일

[ZBF] 240620 코딩테스트 : 그래프

코딩테스트

[ZBF] 240620 코딩테스트 : 그래프

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

그래프 문제는 알고리즘 코딩 테스트에서 자주 등장하는 주제 중 하나입니다. 그래프 문제를 잘 풀기 위해서는 몇 가지 중요한 개념과 알고리즘을 이해하고 있어야 합니다. 여기서는 그래프 문제를 잘 풀 수 있는 방법을 단계별로 설명하겠습니다.

1. 그래프의 기본 개념 이해하기

그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조입니다. 노드는 그래프의 개별 요소를 의미하고, 간선은 노드 간의 연결을 의미합니다. 그래프에는 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph), 가중치 그래프(Weighted Graph)와 비가중치 그래프(Unweighted Graph)가 있습니다.

2. 그래프 표현 방법

그래프를 표현하는 방법에는 여러 가지가 있지만, 주로 사용하는 두 가지 방법은 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다.

  • 인접 행렬: 2차원 배열을 사용하여 그래프를 표현합니다.
  • 인접 리스트: 각 노드에 연결된 노드들의 리스트를 사용하여 그래프를 표현합니다.
// 인접 행렬 예제 (JavaScript)
let graphMatrix = [
  [0, 1, 0, 0],
  [1, 0, 1, 1],
  [0, 1, 0, 1],
  [0, 1, 1, 0]
];

// 인접 리스트 예제 (JavaScript)
let graphList = {
  0: [1],
  1: [0, 2, 3],
  2: [1, 3],
  3: [1, 2]
};

3. 주요 그래프 알고리즘 익히기

그래프 문제를 풀기 위해서는 몇 가지 주요 알고리즘을 알아야 합니다.

깊이 우선 탐색(Depth-First Search, DFS)

DFS는 그래프의 모든 노드를 방문하는 알고리즘 중 하나입니다. 재귀 또는 스택을 사용하여 구현할 수 있습니다.

// 깊이 우선 탐색 (DFS) 예제 (JavaScript)
function dfs(graph, start) {
  let visited = [];
  let stack = [start];

  while (stack.length > 0) {
    let node = stack.pop();
    if (!visited.includes(node)) {
      visited.push(node);
      stack.push(...graph[node].filter(n => !visited.includes(n)));
    }
  }
  return visited;
}

너비 우선 탐색(Breadth-First Search, BFS)

BFS는 그래프의 모든 노드를 방문하는 또 다른 알고리즘입니다. 큐를 사용하여 구현합니다.

// 너비 우선 탐색 (BFS) 예제 (JavaScript)
function bfs(graph, start) {
  let visited = [];
  let queue = [start];

  while (queue.length > 0) {
    let node = queue.shift();
    if (!visited.includes(node)) {
      visited.push(node);
      queue.push(...graph[node].filter(n => !visited.includes(n)));
    }
  }
  return visited;
}

4. 그래프 문제 해결 전략

그래프 문제를 해결하기 위한 몇 가지 전략을 소개합니다.

문제 이해 및 그래프 모델링

문제를 잘 이해하고, 주어진 문제를 그래프로 어떻게 모델링할지 결정합니다. 노드와 간선이 무엇을 의미하는지 파악합니다.

알고리즘 선택

문제의 특성에 따라 적절한 탐색 알고리즘(DFS, BFS 등)을 선택합니다. 최단 경로를 구해야 하는 경우에는 다익스트라 알고리즘(Dijkstra's Algorithm)이나 벨만-포드 알고리즘(Bellman-Ford Algorithm)을 사용할 수 있습니다.

코딩 및 테스트

선택한 알고리즘을 코드로 구현하고, 주어진 테스트 케이스를 통해 검증합니다. 다양한 경로, 노드 수, 간선 수를 고려하여 테스트를 진행합니다.

https://school.programmers.co.kr/learn/courses/30/parts/14393

  • 프로그래머스 스쿨 - 온라인 IT 특화 교육 전문 플랫폼 — 프로그래머스 스쿨은 IT 분야 교육 전반의 과정을 제공하는 온라인 교육 플랫폼입니다. 프로그래밍, 데이터, 인공지능 등의 학습부터 코딩 테스트, 과제 테스트 연습까지, 프로그래머스 스쿨과 함께 성장해 보세요!
← 글 목록으로