코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

그래프

그래프는 G(V, E)로 정의하고, V(Vertext : 정점)과 E(Edge : 간선) 의 집합을 의미한다.
즉, 연결되어 있는 원소들간의 관계를 표현하는 자료구조이다.

---

1. 인접 행렬

2차원 배열을 이용해 그래프를 표현하는 방법

• 2차원 배열(n*m)이 기하급수적으로 커질 경우 성능이 안 좋아진다.
• 만약 n*n이라고 했을 때 n이 100,000일 경우 행렬에 그래프를 표현하려면 100,000x100,000 만큼 돌아야해 공간 복잡도가 높아 지고, 검색을 할 때도 그 크기만큼 돌아야 검색할 수 있으므로 시간 복잡도도 높아질 수 있다.

1-1. 무방향 그래프

• 입력형식 : edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]]

graph = [[0] * (n+1) for _ in range(n+1)]
for [a, b] in edge:
	graph[a][b] = 1 
    graph[b][a] = 1

1-2. 방향 그래프

• 입력형식 : edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]]

graph = [[0] * (n+1) for _ in range(n+1)]
for [a, b] in edge:
	graph[a][b] = 1

---

2. 인접리스트

연결리스트을 이용해 그래프를 표현하는 방법

• 인접 리스트는 n이 100,000이라고 할 경우, 확인하려는 edge의 연결된 리스트만 확인하면 되므로 공간 복잡도와 시간 복잡도가 인접행렬에 비해서 성능이 좋아진다.

2-1. 무방향 그래프

[
	[]
    [2, 3]
    [1, 4, 5]
    [1, 4]
    [2, 3]
    [2]
]

• 입력형식 : edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]]

graph = [[] for _ in range(n+1)]
for [a, b] in edge:
	graph[a].append(b) 
    graph[b].append(a)

2-2. 방향 그래프

[
	[]
    [2, 3]
    [5]
    [4]
    [2]
    []
]

• 입력형식 : edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]]

graph = [[] for _ in range(n+1)]
for [a, b] in edge:
	graph[a].append(b)

---

위와 같이 그래프를 학습한 후 풀이한 문제는 아래와 같다.

• 컴퓨터 개수