Shortest Path(최단 경로) 특징

1. 음수 사이클이 없다.

2. 방향 그래프(directed graph)

3. 가중치 그래프(weighted graph)

4. 경로의 길이 : edge 가중치의 합

Prim algorithm

1. 정점 하나를 가진 트리에서 시작
   • TV = {v1}
     • TV : 트리의 정점
2. 트리 내의 정점 u와 트리 밖의 정점 v를 잇는 Edge 중 최소 비용을 가진 (u,v)를 트리 Edge로 만든다.
   • TE = TV U {u,v}
3. 트리 밖의 정점 v도 트리의 정점으로 만든다.
   • TV = TV U {v}
4. TV = V(G)와 같아지면 종료

Kruskal algorithm

1. Edge를 가중치가 작은 것에서 큰 것 순으로 정렬
2. 트리에 Edge를 하나씩 추가
3. 사이클이 생기면 추가하지 않는다.
4. 최소 비용 신장 트리가 완성되면 |E| = |v|-1

MST(Minimum cost Spanning Tree)

신장 트리(Spanning Tree)

1. connected(연결되어 있다.)
2. 최소 엣지 수 |E| = |V| - 1 (트리 조건)
3. E(G’)는 E(G)에 포함되어 있다.
4. V(G’) = V(G)

최소 비용 신장 트리

1. 무방향 그래프
2. 가중치 그래프
3. 비용(cost) 최소화

B-tree를 사용하는 이유

• 탐색에서 최악의 경우에도 O(log2n)이 걸리는 균형 이진트리도 굉장히 큰 성과이지만,
• 데이터가 메인 메모리에 저장되어 있거나,
• 데이터베이스의 경우 하드디스크에 저장되어 있으면,
• 데이터의 연산보다는 메모리 접근에 엄청난 시간이 소요된다.
• 이 문제를 해결하기 위해 B-tree 자료구조가 필요하다.

Graph 정의

그래프 G는 두 집합 V, E로 나타낸다.

1. V(G) : 노드(node) 혹은 정점(vertex)의 집합
2. E(G) : 정점을 잇는 엣지(edge)의 집합

완전탐색 (Brute-Force-Search) 문제 2 - Boardcover

• height(H) * width(W)의 보드가 검은색과 흰색으로 채워져 있다.
• 모든 흰칸을 ‘ㄱ’ 모양의 흰색 블록으로 덮고 싶다.
• 블록은 회전 가능하지만 겹치거나 검은색 블록을 침범하거나 밖으로 이탈되어서는 안된다.
• 보드가 있을 때 이를 덮는 방법의 수를 계산하는 프로그램을 만드시오.
• 알고리즘 문제해결 전략 p.159 게임판 덮기

완전탐색 (Brute-Force-Search) 문제 1 - picnic

• 학교에서 소풍을 가려고 한다.
• 학생들을 두명씩 짝지어 행동하게 하려고 한다.
• 단, 서로 친구인 경우에만 짝을 지어야 한다.
• 서로 친구인 경우의 쌍이 주어질 때, 학생들을 짝지을 수 있는 방법의 수를 구하는 프로그램을 구현하라.
• n(학생 수)은 항상 짝수이다.
• 알고리즘 문제해결 전략 1권 p.157

이진 탐색 트리(Binary-Search-Tree)

• 모든 원소는 상이한 키를 갖는다.
• 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
• 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.
• 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리이다.

이진트리(Binary Tree)란?

• 어떤 노드의 자식 노드의 수가 최대 2개인 트리

• 공집합 혹은 루트(root)와 왼쪽 서브 트리, 오른쪽 서브 트리로 이루어진 유한 집합, 각각의 서브 트리는 모두 이진 트리이다.

• 트리는 connected acyclic graph

  • 루트 노드(root)를 반드시 가진다.
  • 트리를 구성하는 노드 간 단순 경로가 존재한다.

• 트리는 1개 이상의 노드로 이루어진 유한 집합

  • 루트 노드(root)를 반드시 가진다.
  • 나머지 노드들은 분리집합 T1, …, Tn으로 분할 가능
    • T1, T2 등은 각각의 하나의 트리(서브 트리)가 된다.