[오독완 챌린지] 기술 면접 대비 CS 전공 핵심 요약집 (8일차)

오늘도 독서완료!

오늘은 비선형 자료구조에 대해서 학습했습니다.

 

비선형 자료구조(non-linear data structure)란 하나의 데이터 뒤에 N개의 데이터가 이어질 수 있는 1:N 또는 N:N 구조로 데이터가 나열되는 자료구조를 뜻합니다. 따라서 주로 계층적 자료구조를 나타내는데 쓰기이도 합니다.

 

이 중 가장 중요한 것은 그래프로 데이터를 포함하는 정점(vertex)과 정점을 잇는 간선(edge)로 구성된 자료구조가 있다. 정점은 노드(node)라고도 한다.

 

시작 정점이 주어지고 간선을 거쳐 모든 정점을 탐색하는 경로를 질문하는 그래프 탐색 문제가 코딩테스트에서 자주 출제되는데 가장 유명한게 BFS(너비우선 탐색)과 DFS(깊이 우선 탐색)가 있다.

 

너비 우선 탐색은 탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식이다.

깊이 우선 탐색은 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색한다. 최대 깊이 정점에 도달했다면 방문한 정점들을 역순으로 재방문해 탐색 가능한 정점이 있는지 확인한다. 재귀호출 또는 스택으로 구현할 수 있다.

 

마지막으로 트리가 매우 중요한데, 그래프의 한 종류로 사이클이 없어 계층적 관계를 표현하는데 가장 유명한 자료구조이다.
트리도 다양한 종류가 있지만 자식 노드가 최대 2개인 이진트리가 있고, 이진 트리도 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리 등 다양한 종류가 존재한다.