220809_Algorithm.md

💻그래프

정점(Vertex/Node)과 이를 연결하는 간선(Edge)의 집합으로 이루어진 비선현 자료구조

• 정점(Vertex)J: 간선으로 연결되는 객체이며, 노드(Node)라고도 한다.

• 간선(Edge): 정점 간의 관계(연결)를 표현하는 선을 의미한다.

• 경로(Path): 시작 정점부터 도착 정점까지 거치는 정점을 나열한 것을 의미힌다.

• 인접(Adjacency): 두 개의 정점이 하나의 간선으로 직접 연결된 상태를 의미한다.

1. 무방향 그래프 (Undirected graph)

• 간선의 방향이 없는 가장 일반적인 그래프

• 간선을 통해 양방향의 정점 이동 가능

• 차수(Degree): 하나의 정점에 연결된 간선의 개수

• 모든 정점의 차수의 합 = 간선 수 * 2

2. 유방향 그래프 (Directed graph)

• 간선의 방향이 있는 그래프

• 간선의 방향이 가리키는 정점으로 이동이 가능

• 차수(Degree): 진입 차수와 진출 차수로 나누어짐

  • 진입 차수(In-degree): 외부 정점에서 한 정점으로 들어오는 간선의 수
  • 진출 차수(Out-degree): 한 정점에서 외부 정점으로 나가는 간선의 수

💻그래프의 표현 그래프를 실제 문제에서 어떻게 코드로 표현할까?

각 노드가 어떤 노드와 인접해 있는지를 토대로 코드로 표현이 가능하다.

graph = {
    0: [1,2],
    1: [0,3,4],
    2: [0,4,5],
    3: [1],
    4: [1,2,6],
    5: [2],
    6: [4],
}

# 지하철의 경우, 아래와 같이 표현도 가능하다.
subway = {
    '교대': ['연산', '동래'], # 교대의 이전역은 연산, 다음역은 동래
    '부산대': ['온천장', '장전'],
}

🍯key를 인덱스 자체로 활용하여 그래프 생성도 가능하다. 이 방식을 인접리스트(Adjacent List)라고 한다.

graph = {
    [1,2],
    [0,3,4],
    [0,4,5],
    [1],
    [1,2,6],
    [2],
    [4],
}

💻인접 행렬(Adjacent matrix)

두 정점을 연결하는 간선이 없으면 0, 있으면 1을 가지는 행렬로 표현하는 방식

인접 행렬을 만들어보자.

edges = [
    [0,1],
    [0,2],
    [1,3],
    [2,4],
    [1,4],
    [2,5],
    [4,6],
]

n = 7 # 정점(vertex) 갯수
m = 7 # 간선(edge) 갯수

# 입력 값
0 1
0 2
1 3
1 4
2 4
2 5
4 6

# n X n 매트릭스를 생성
graph = [[0] * n for _ in range(n)]

for edge in edges:
    v1,v2 = map(int, input().split())
    graph[v1][v2] = 1
    graph[v2][v1] = 1

🍯팁: Flatten 기법
# 여러 개의 인자가 있을 때 풀어서 한번에 출력하고 싶을 때 flatten 기법을 사용한다.
print(*edges) # [0,1,0,2,1,3,2,4,1,4,2,5,4,6]

💻인접 리스트 리스트를 통해 각 정점(vertex/node)에 대한 인접 정점들을 순차적으로 표현하는 방식

인접 리스트를 만들어보자

n = 7 # 정점 갯수
m = 7 # 간선 갯수

adjacent_lst = [ for _ in range(n)]

for _ in range(m):
    v1, v2 = map(int, input().split())

# 0 1 이 입력됨
adjacent_lst =

💻인접행렬 vs 인접 리스트

인접 행렬은 직관적이고 만들기 편하지만, 불필요하게 공간이 낭비된다.

인접 리스트는 연결된 정점만 저장하여 효율적이므로 자주 사용된다.