본문 바로가기
코딩테스트1

[코딩 테스트] 7일차: 트리와 그래프

by cogito21_js 2024. 9. 7.
반응형

트리

트리는 노드와 에지로 구성된 자료구조로, 계층적인 데이터를 표현하는 데 사용됩니다. 트리는 루트 노드를 가지고 있으며, 각 노드는 자식 노드를 가질 수 있습니다.

트리의 주요 개념

  • 루트 노드: 트리의 시작 노드
  • 리프 노드: 자식 노드가 없는 노드
  • 간선(Edge): 노드를 연결하는 선
  • 깊이(Depth): 루트 노드에서 특정 노드까지의 경로 길이
  • 높이(Height): 루트 노드에서 리프 노드까지의 가장 긴 경로 길이

트리 순회

트리 순회 방법에는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)가 있습니다.

전위 순회 (Preorder)

  1. 현재 노드를 방문
  2. 왼쪽 서브트리를 전위 순회
  3. 오른쪽 서브트리를 전위 순회

중위 순회 (Inorder)

  1. 왼쪽 서브트리를 중위 순회
  2. 현재 노드를 방문
  3. 오른쪽 서브트리를 중위 순회

후위 순회 (Postorder)

  1. 왼쪽 서브트리를 후위 순회
  2. 오른쪽 서브트리를 후위 순회
  3. 현재 노드를 방문

예제: 트리 순회

JavaScript

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // 전위 순회
  preorder(node) {
    if (node !== null) {
      console.log(node.data);
      this.preorder(node.left);
      this.preorder(node.right);
    }
  }

  // 중위 순회
  inorder(node) {
    if (node !== null) {
      this.inorder(node.left);
      console.log(node.data);
      this.inorder(node.right);
    }
  }

  // 후위 순회
  postorder(node) {
    if (node !== null) {
      this.postorder(node.left);
      this.postorder(node.right);
      console.log(node.data);
    }
  }
}

let tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

console.log("Preorder:");
tree.preorder(tree.root); // 1 2 4 5 3

console.log("Inorder:");
tree.inorder(tree.root); // 4 2 5 1 3

console.log("Postorder:");
tree.postorder(tree.root); // 4 5 2 3 1

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    # 전위 순회
    def preorder(self, node):
        if node:
            print(node.data, end=' ')
            self.preorder(node.left)
            self.preorder(node.right)

    # 중위 순회
    def inorder(self, node):
        if node:
            self.inorder(node.left)
            print(node.data, end=' ')
            self.inorder(node.right)

    # 후위 순회
    def postorder(self, node):
        if node:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.data, end=' ')

tree = BinaryTree()
tree.root = Node(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

print("Preorder:")
tree.preorder(tree.root) # 1 2 4 5 3
print("\nInorder:")
tree.inorder(tree.root) # 4 2 5 1 3
print("\nPostorder:")
tree.postorder(tree.root) # 4 5 2 3 1

이진 탐색 트리 (BST)

이진 탐색 트리(Binary Search Tree)는 왼쪽 서브트리의 모든 노드 값이 현재 노드 값보다 작고, 오른쪽 서브트리의 모든 노드 값이 현재 노드 값보다 큰 이진 트리입니다.

예제: 이진 탐색 트리 삽입과 탐색

JavaScript

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // 노드 삽입
  insert(data) {
    let newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 노드 탐색
  search(node, data) {
    if (node === null) {
      return null;
    } else if (data < node.data) {
      return this.search(node.left, data);
    } else if (data > node.data) {
      return this.search(node.right, data);
    } else {
      return node;
    }
  }
}

let bst = new BinarySearchTree();
bst.insert(10);
bst.insert(20);
bst.insert(5);
bst.insert(15);

let node = bst.search(bst.root, 15);
console.log(node ? "Node found" : "Node not found"); // "Node found"

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    # 노드 삽입
    def insert(self, data):
        new_node = Node(data)
        if self.root is None:
            self.root = new_node
        else:
            self._insert(self.root, new_node)

    def _insert(self, node, new_node):
        if new_node.data < node.data:
            if node.left is None:
                node.left = new_node
            else:
                self._insert(node.left, new_node)
        else:
            if node.right is None:
                node.right = new_node
            else:
                self._insert(node.right, new_node)

    # 노드 탐색
    def search(self, node, data):
        if node is None or node.data == data:
            return node
        if data < node.data:
            return self.search(node.left, data)
        return self.search(node.right, data)

bst = BinarySearchTree()
bst.insert(10)
bst.insert(20)
bst.insert(5)
bst.insert(15)

node = bst.search(bst.root, 15)
print("Node found" if node else "Node not found") # "Node found"

그래프

그래프는 노드(정점)와 노드를 연결하는 에지(간선)로 구성된 자료구조입니다. 그래프는 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나눌 수 있습니다.

그래프의 주요 개념

  • 정점(Vertex): 그래프를 구성하는 기본 요소
  • 간선(Edge): 정점 간의 연결
  • 인접 행렬(Adjacency Matrix): 그래프를 표현하는 2차원 배열
  • 인접 리스트(Adjacency List): 그래프를 표현하는 리스트의 리스트

그래프 탐색 (DFS, BFS)

  • 깊이 우선 탐색(DFS, Depth-First Search): 그래프의 깊이를 우선으로 탐색하는 방법
  • 너비 우선 탐색(BFS, Breadth-First Search): 그래프의 너비를 우선으로 탐색하는 방법

예제: 그래프 탐색

JavaScript

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.adjList = new Map();
  }

  addVertex(v) {
    this.adjList.set(v, []);
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v);
  }

  // DFS 탐색
  dfs(v, visited = new Set

()) {
    visited.add(v);
    console.log(v);

    let neighbors = this.adjList.get(v);
    for (let neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        this.dfs(neighbor, visited);
      }
    }
  }

  // BFS 탐색
  bfs(startingNode) {
    let visited = new Set();
    let queue = [startingNode];

    visited.add(startingNode);

    while (queue.length > 0) {
      let v = queue.shift();
      console.log(v);

      let neighbors = this.adjList.get(v);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
}

let g = new Graph(5);
let vertices = ['A', 'B', 'C', 'D', 'E'];

for (let i = 0; i < vertices.length; i++) {
  g.addVertex(vertices[i]);
}

g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'C');
g.addEdge('C', 'E');

console.log("DFS:");
g.dfs('A');

console.log("BFS:");
g.bfs('A');

Python

class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_vertex(self, v):
        if v not in self.adj_list:
            self.adj_list[v] = []

    def add_edge(self, v, w):
        if v in self.adj_list and w in self.adj_list:
            self.adj_list[v].append(w)
            self.adj_list[w].append(v)

    # DFS 탐색
    def dfs(self, v, visited=None):
        if visited is None:
            visited = set()
        visited.add(v)
        print(v, end=' ')

        for neighbor in self.adj_list[v]:
            if neighbor not in visited:
                self.dfs(neighbor, visited)

    # BFS 탐색
    def bfs(self, starting_node):
        visited = set()
        queue = [starting_node]
        visited.add(starting_node)

        while queue:
            v = queue.pop(0)
            print(v, end=' ')

            for neighbor in self.adj_list[v]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

g = Graph()
vertices = ['A', 'B', 'C', 'D', 'E']

for vertex in vertices:
    g.add_vertex(vertex)

g.add_edge('A', 'B')
g.add_edge('A', 'D')
g.add_edge('A', 'E')
g.add_edge('B', 'C')
g.add_edge('D', 'E')
g.add_edge('E', 'C')
g.add_edge('C', 'E')

print("DFS:")
g.dfs('A') # A B C E D

print("\nBFS:")
g.bfs('A') # A B D E C

연습 문제

문제 1: 이진 탐색 트리의 삽입, 삭제, 탐색

이진 탐색 트리에 값을 삽입, 삭제, 탐색하는 함수를 작성하세요.

JavaScript

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    let newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  search(node, data) {
    if (node === null) {
      return null;
    } else if (data < node.data) {
      return this.search(node.left, data);
    } else if (data > node.data) {
      return this.search(node.right, data);
    } else {
      return node;
    }
  }

  remove(data) {
    this.root = this.removeNode(this.root, data);
  }

  removeNode(node, key) {
    if (node === null) {
      return null;
    } else if (key < node.data) {
      node.left = this.removeNode(node.left, key);
      return node;
    } else if (key > node.data) {
      node.right = this.removeNode(node.right, key);
      return node;
    } else {
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }

      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }

      let aux = this.findMinNode(node.right);
      node.data = aux.data;

      node.right = this.removeNode(node.right, aux.data);
      return node;
    }
  }

  findMinNode(node) {
    if (node.left === null) {
      return node;
    } else {
      return this.findMinNode(node.left);
    }
  }
}

let bst = new BinarySearchTree();
bst.insert(10);
bst.insert(20);
bst.insert(5);
bst.insert(15);
bst.remove(20);

let node = bst.search(bst.root, 15);
console.log(node ? "Node found" : "Node not found"); // "Node found"

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        new_node = Node(data)
        if self.root is None:
            self.root = new_node
        else:
            self._insert(self.root, new_node)

    def _insert(self, node, new_node):
        if new_node.data < node.data:
            if node.left is None:
                node.left = new_node
            else:
                self._insert(node.left, new_node)
        else:
            if node.right is None:
                node.right = new_node
            else:
                self._insert(node.right, new_node)

    def search(self, node, data):
        if node is None or node.data == data:
            return node
        if data < node.data:
            return self.search(node.left, data)
        return self.search(node.right, data)

    def remove(self, data):
        self.root = self._remove(self.root, data)

    def _remove(self, node, data):
        if node is None:
            return node

        if data < node.data:
            node.left = self._remove(node.left, data)
        elif data > node.data:
            node.right = self._remove(node.right, data)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left

            temp = self.find_min(node.right)
            node.data = temp.data
            node.right = self._remove(node.right, temp.data)

        return node

    def find_min(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

bst = BinarySearchTree()
bst.insert(10)
bst.insert(20)
bst.insert(5)
bst.insert(15)
bst.remove(20)

node = bst.search(bst.root, 15)
print("Node found" if node else "Node not found") # "Node found"

결론

이번 글에서는 코딩 테스트 준비를 위해 트리와 그래프에 대해 배웠습니다. 이를 통해 트리의 개념과 순회, 이진 탐색 트리, 그래프의 개념과 탐색 방법(DFS, BFS)을 익힐 수 있었습니다. 다음 글에서는 해시 테이블에 대해 알아보겠습니다.

다음 글에서 만나요!

반응형
저작자표시

'코딩테스트1' 카테고리의 다른 글

[코딩 테스트] 9일차: 정렬 알고리즘  (0) 2024.09.09
[코딩 테스트] 8일차: 해시 테이블  (1) 2024.09.08
[코딩 테스트] 6일차: 연결 리스트  (0) 2024.09.06
[코딩 테스트] 5일차: 스택과 큐  (0) 2024.09.05
[코딩 테스트] 4일차: 배열과 문자열  (0) 2024.09.04

관련글

티스토리툴바