20240215 이것이 코딩 테스트다 챕터5(DFS/BFS)
자료구조(Data Structure)
데이터를 표현하고 관리하고 처리하기 위한 구조.
스택(Stack)
아래에서부터 위로 쌓고 뺄때는 위에서부터 빼는 박스 쌓기 구조. 선입후출(First In Last Out). 후입선출(Last In First Out) 구조.
별도의 라이브러리 사용할 필요 없이 리스트 사용해주면 됨.
삽입 : append() - 리스트 가장 뒤쪽에 데이터 삽입
삭제 : pop() - 리스트 가장 뒤쪽 데이터 삭제
큐(Queue)
먼저 온 사람이 먼저 들어가는 대기줄 구조. 선입선출(First In First Out)구조.
collections 모듈에서 제공하는 deque 자료구조를 사용.
삽입 : append() - 디큐의 가장 뒤쪽에 데이터 삽입
삭제 : popleft() - 디큐의 가장 앞쪽의 데이터 삭제
deque 객체를 리스트 자료형으로 변경하고 싶으면 list() 메서드 사용하여 list(queue)해주면 됨.
그래프(Graph)
- 노드(Node) : 정점(vertex)라고도 함. 쉽게 도시라고 생각하면 됨.
- 간선(Edge) : 쉽게 도로라고 생각하면 됨.
- 인접(adjacent) : 두 노두가 간선으로 연결되어 있을 때 두 노드는 인접함.
그래프 표현 방식
-
- 인접 행렬
- 2차원 matrix를 만들고 row와 column명에 노드를 적어, row 0과 column 0의 해당값은 노드0과 노드0의 거리는 0이기 때문에 0, row 1과 column 1의 해당값은 노드0과 노드1의 거리가 7이기 때문에 7, row 1과 column 2의 해당값은 노드1과 노드2가 연결되어 있지 않기 때문에 무한값을 적는것이다.
파이썬에서 인접 행렬 방식으로 그래프를 표현해보면,
inf = 999999999
graph = [
[0, 7, 5],
[7, 0, inf],
[5, inf, 0]
]
print(graph)
### 출력
## [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]
장점 : 특정 노드와 특정 노드가 연결되어 있는지 확인하기에 속도 빠름.
단점 : 모든 관계를 저장하기 때문에 메모리 낭비.
-
- 인접 리스트
- 행이 노드 개수인 2차원 리스트를 만들고 노드0에 노드1이 7만큼의 거리로, 노드2가 5만큼의 거리로 연결되어 있다면, graph[0]에 (1,7)과 (2,5), 즉 연결된 노드의 정보를 (노드, 거리)로 삽입해준다.
graph = [[] for _ in range(3)]
graph[0].append((1, 7))
graph[0].append((2, 5))
graph[1].append((0, 7))
graph[2].append((0, 5))
print(graph)
### 출력
## [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]
장점 : 연결된 정보만을 저장하기 때문에 메모리 효율성.
단점 : 특정 노드와 특정 노드가 연결되어 있는지 확인하려면 특정 노드에 연결된 모든 노드들을 살펴봐야하기 때문에 속도 느림.
오버플로(Overflow)
특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 데이터를 삽입했을 때 발생.
언더플로(Underflow)
특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 발생.
재귀 함수(Recursive Function)
자기 자신을 다시 호출하는 함수.
재귀 함수를 문제 풀이에서 사용할 때는 반드시 재귀 함수가 언제 끝날지 종료 조건을 명시해줘야 됨.
재귀 함수의 수행은 스택 자료구조를 이용함. 즉 함수를 계속 호출하는데 그리고 가장 마지막에 호출한 함수가 수행을 끄태냥 그 앞의 함수 호출이 종료됨.
따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수로 간단히 구현됨. DFS가 대표적 예.
소스코드를 반복적(iterative)으로 구현한다는 것은 반복문을 이용한다는 의미. 재귀적(recursive)으로 구현한다는 말과 대비적으로 사용함.
탐색 알고리즘
많은 양의 데이터 중에서 원하는 데이터를 찾는 과정. Search algorithm.
프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸.
대표적 탐색 알고리즘 : DFS, BFS
DFS(Depth-First Search)
깊이 우선 탐색. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 즉, 최대한 멀리 있는 노드를 우선으로 탐색하는 방식.
스택 자료구조를 이용. 따라서 재귀 함수 이용하면 간결하게 구현 가능.
시간복잡도 데이터 개수 N일때, O(N)
- 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리. 이때 방문하지 않은 인접 노드가 여러개일때, 일반적으로 숫자가 낮은 노드부터 처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼냄.
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복.
BFS(Breadth First Search)
너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘.
선입선출 방식은 큐 자료구조를 이용. 따라서 deque 라이브러를 사용해 구현 가능.
시간복잡도 데이터 개수 N일때, O(N). 일반적으로 실제 수행 시간이 DFS보다 좋은 편임.
- 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모듀 큐에 삽입하고 방문 처리. 이때 방문하지 않은 인접 노드가 여러개일때, 숫자가 낮은 노드부터 큐에 삽입함.
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복.
Leave a comment