코딩테스트 - 패스트캠퍼스 챌린지 31일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 그래프 탐색 (Graph Search, DFS & BFS)

학습 후기
알고리즘에서 그래프 = 정점(Vertex) + 간선(Edge)
간선: 무방향 / 방향 + 가중치 가 있을 수 있음
정점의 차수(degree): 정점 x의 차수는 정점 x에 연결된 간선의 수
모든 정점의 차수의 합 = 간선의 개수의 2배, 이유는 모든 정점의 차수를 더하면 한 간선이 두 번씩 중복해서 더해지므로 2배가 된다.

그래프를 저장하는 방법
1. 인접 행렬: 2차원 행렬로 이어지는 간선이 있는 곳에 1을 표시한다. 0으로 표시되어있다면 연결되어 있지 않다. 가중치 그래프일 경우 0, 1 대신 가중치로 표시하기도 함. O(V^2) 만큼의 공간이 필요하다. V가 만약 10만이면 V^2은 100억 은 약 10기가다. 인접 행렬로 그래프를 푸는 문제는 공간 복잡도 이슈를 확인해야 한다.

2. 인접 리스트
2차원 ArrayList로 구현. O(E) 만큼의 공간이 필요(간선), 이 경우 V가 10만이고 E가 50만이면 공간 복잡도는 O(E) = 500K이다.

	인접 행렬	인접 리스트
A와 B를 잇는 간선 존재 여부 확인	O(1) list[A][B] == 1 인지 확인	O(min(deg(A), deg(B))) list[A]에 B가 있는지 확인
A와 연결된 모든 정점 확인	O(V)	O(deg(A))
공간복잡도	O(V^2)	O(E)

그래프 문제의 핵심
1. 정점과 간선에 대한 정확한 정의
2. 간선 저장 방식 확인하기

그래프에서의 탐색
인접 행렬의 DFS, BFS로 탐색할 경우 시간 복잡도는 O(V^2)
인접 리스트의 경우 DFS, BFS로 탐색할 경우 시간 복잡도는 O(E)
BFS로 탐색할 때 큐에서 해당 정점을 방문 가능하다고 큐에 넣을 때 방문 체크를 해줘야 한다.

이번 강의에서 푼 문제
https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

첫 문제라서 인접 행렬, 인접 리스트 두 가지 경우 다 풀이해 주었다. 또 탐색도 DFS, BFS 두 가지 방법으로 풀이해주셨다.
여러 번 연습해보며 바로바로 풀 수 있도록 익히자.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.