[CS] 알고리즘- 그래프, DFS, BFS

1. 스택

- 먼저들어온 데이터가 나중에 나감(박스 쌓기)

 

2. List

- append() 추가

- pop() 제거

 

3. 큐

- 먼저들어온 데이터가 먼저 나가는 자료구조

- deque 라이브러리 사용(시간 복잡도를 줄이기 위해)

- append() 추가

- popleft() 제거

 

4. 재귀함수(Recursive)

- 자기 자신을 다시 호출하는 함수

- 컴퓨터가 함수를 연속적으로 호출하면, 컴퓨터 메모리 내부의 스택 프레임에 쌓인다

=> 스택을 사용해야 할 때 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다

=> 메모리에 문제가 생길 수 있음 => 최대 재귀 깊이 설정(함수 시작부분에 종료 조건 명시)

 

1) 팩토리얼

- 0!과 1!의 값은 1이다

 

2) 유클리드호제법: 최대 공약수(GCD) 계산

- A>B인 자연수에서 A%B = R일때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

- 예시: A:119 = 17*7, B:34=17*2 일때 최대공약수는 17, 119%34 = 17:R, 34와 17의 최대공약수는 17

단계	A	B	R(=A%B)
1	192	162	30
2	162	30	12
3	30	12	6
4	12	6	0

 

5. 그래프(Graph)

1) 노드

2) 엣지

- 노드를 연결

 

6. DFS (Depth-First Search)

- 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- DFS는 스택 자료구조(혹은 재귀함수)를 이용

1) 탐색 시작 노트를 스택에 삽입하고 방문처리

2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

3) 방문처리하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다

4) 더이상 과정을 수행할 수 없을때까지 반복

 

7. BFS (Breadth-First Search)

- 너비 우선 탐색, 가까운 노트부터 우선적으로 탐색하는 알고리즘

- 큐 자료구조를 이용

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리

2) 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

3) 더 이상 과정을 수행할 수 없을 때까지 반복

 

※ 참고: 이것이 취업을 위한 코딩 테스트다 - DFS&BFS