비선형 문제

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

배열, 벡터, 리스트, 덱 등의 선형 구조에서는 순방향과 역방향으로 원소를 순회할 수 있다.

 

하지만 다음과 같은 문제는 선형 구조로 표현할 수 없다.

• 계층적 문제: 회사의 조직도, 대학의 교과 과정 계층도
• 순환 종속성 문제: SNS의 친구 관계, 도시의 도로망

 

 

트리(Tree)

• 계층적 문제를 표현할 수 있는 자료 구조이다.
• 데이터가 저장되는 노드(Node)와 노드 사이를 잇는 간선(Edge)으로 표현된다.
• 자식(Child) 노드에 대한 참조를 가지며 부모(Parent) 노드에 대한 참조도 가질 수 있다.

 

 

그래프(Graph)

• 순환 종속성 문제를 표현할 수 있는 자료 구조이다.
• 데이터가 저장되는 정점(Vertex)과 정점 사이를 잇는 간선(Edge)으로 표현된다.
• 인접한(Adjacent) 정점들을 인접 행렬(Adjacency matrix) 혹은 인접 리스트(Adjacency list)로 관리한다.