SECTION 5.3 - 비선형 자료 구조
.1 비선형 구조 (Non-Linear)
선형구조는 자료를 저장하고 꺼내는 것이 중점이라면 ( 데이터의 삽입, 삭제 )
비선형 구조는 자료의 표현에 중점을 맞추고 있음
하나의 자료 안(뒤)에 1:N 혹은 N:N의 관계
왜 비선형 구조가 필요한지 생각해보자.
모든 것에서 선형구조가 효율적이지 않음을 알기 때문
선형 자료구조로 표현할 수 없는 문제들이 분명 있을 것
계층적 문제와 순환 종속성 문제.
계층적 문제란?.
가계도, 조직도, 고등학교 교육과정등.. 다양한 예가 있음
순환 종속성 문제?...
A B C 순서로 저장하면 위정보가 전달 될것인가?..
위와 같은 문제들로 인해 우리는 비선형 자료 구조의 필요를 가져왔고
트리, 그래프 라는 자료구조를 필요로 하게된다.
-
비단순 - 비선형 -그래프 (Graph)
단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조.
-
오일러 경로 (참고)
그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 돌아오는 것. ( 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로 존재 )
-
그래프 특징
- 네트워크 모델
- 2개이상 경로 가능
- 루트 노드라는 개념이 없음
- 부모-자식 관계라는 개념 없음
- 순회는 DFS나 BFS로 이루어짐
- 순호나 혹은 비순환
-
그래프 종류
-
무방향 그래프 ( Undirected Graph )
무방향 그래프의 간선은 간선을 통해 양 방향으로 갈수 있음 (A,B) = (B,A)
ex) 양방향 통행 도로- 방향 그래프 ( Directed Graph )
간선에 방향성이 존재하는 그래프 A->B만로만 갈수있다면 (A,B) !=(B,A)
ex)일방 통행- 그 외
가중치 그래프, 순환,비순환 그래프, 완전그래프 등등이 있음
-
-
-
비단순 - 비선형 - 트리 (Tree)
Node와 Branch로 이루어진 자료구조로 사이클로 이루어지지 않도록 구성
-
트리 구현 방법
배열이나, 연결리스트로 구현 가능
이제 부터는 연속된 구조와 연결된 자료구조에 대해 장단점 및 특징들은 알고 있어야 함
-
배열
메모리 낭비가 매우 심한것을 볼 수 있음
=> 2^h개의 메모리를 차지하지만 그 공간을 모두 쓰고있지는 않음 -
연결 리스트
연결리스트 기반 트리 구현 방식은 연결리스트의 노드를 생각해보자.
자기 자신이 갖는 데이터와 왼,오른쪽 자식 데이터 각각 1개씩 갖게 됨 = 노드
배열로 표현을 하면 자식들을 가리키는 링크를 가져야함. 하지만 차수가 달라지면 배열의 각 노드 마다의 크기도 달라져야함... 어떻게할까?..
트리의 차수를 통일시키면 해결 -> 그래서 등장한것이 2진 트리
-
-
이진 트리
이진트리도 종류가 여러가지 있으나 이진트리가 뭔지 알면 자연스럽게 이해 가능
-
성질
- n개의 노드를 가진 트리는 n-1개의 간선을 갖는다.
- 높이가 h인 이진트리는 h개 이상, 2^ℎ-1개 이하의 노드를 가짐
- n개의 노드를 가지는 이진트리의 높이는 역으로 log₂(N+1)를 취함
-
-
이진 탐색 트리
노드의 오른쪽 하위에는 노드 값보다 큰값, 왼쪽 하위에는 작은값이 들어오는 트리
-> 최악의 경우에는 선형적 트리가 생길 수 있음 O(n) -
AVL 트리
최악의 경우인 선형적 트리가 생기는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
최악의 경우 O(n)을 위에서 학습한 조건에 맞게 직접 바꿔 보면 이해가 훨씬 쉬움
-
-
비단순 - 비선형 - 우선순위 큐( Priority Queue) 와 힙 (Heap)
큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식
우선순위 큐 : 우선순위가 높은 데이터가 먼저 나가는 형태
힙 : 우선순위 큐를 위해 고안된 완전 이진 트리를 기초로 하는 자료구조
=> 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠름-
힙의 종류
-
최대힙 (Max Heap)
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진 트리key ( 부모노드 ) ≥ key ( 자식노드 )
-
최소힙 (Min Heap)
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진 트리key ( 부모노드 ) ≤ key ( 자식노드 )
-
-
-
비단순 - 비선형 - 맵, 셋, 해쉬 (Map, Set, Hash)
누군가 했겠지....
.2 시간 복잡도
복잡도까지 오기까지에 빌드업이 길었다...
앞서 간단히 소개했듯이 복잡도에도 여러가지가 있지만,그중 가장 중요한 시간 복잡도에 대해 이야기 해보자.
알고리즘의 성능 평가는 알고리즘의 수행 시간을 비교해서 진행
즉, 시간 복잡도는 알고리즘 성능평가 지표중 하나
위 내용을 토대로 선형/비선형 자료 구조의 특징들을 생각해보자.
-
자료구조에서 시간 복잡도
-
배열
index로 정렬된 배열을 생각해보자
- 조회를 할때 index 번호만 검색하면 되니 조회시 복잡도는 O(1)
- 삽입이나 삭제할때는 해당 n번째에 있는 데이터를 찾고 그 뒤쪽 데이터들을 뒤로 한칸씩 밀거나 앞쪽으로 땡겨줌 복잡도는 O(n)
-
연결 리스트
Linked List를 한번 생각해보자
- 조회할때 노드에있는 자식정보를 참고하면서 해당 노드까지 찾아가기 때문에 복잡도는 O(n)
- 삽입이나 삭제를 할때는 노드에있는 자식정보만 고쳐쓰면 되기 때문에 복잡도는 O(1)
-
표로 간단하게 정리
구현 방법 삽입 삭제 조회 순서없는 배열 O(1) O(n) O(n) 순서없는 연결 리스트 O(1) O(n) O(n) 정렬된 배열 O(n) O(1) O(1) 정렬된 연결 리스트 O(n) O(1) O(1) 다른 자료 구조들도 마찬가지로 구조를 파악하면 조금 더 복잡해질뿐 똑같다고 생각한다.
-
-
정리
자료 구조의 특징을 잘 알고 있으면 어떠한 특정 상황. 즉, 알고리즘을 만들 때, 어떤 프로그램을 구현할 때. 어느 상황에서 어떤것을 사용해야 할지 감이 잡힐 것이라고 생각한다.
각각의 자료구조의 특성 때문에 특정 상황에서 유리한 부분이 있고 불리한 부분이 있을 것이라고 생각할 수 있는 단계까지 왔을것이라 생각한다. 그렇다면 자연스럽게 시간 복잡도와 연관 지을 수 있을것이고 더 나아가 알고리즘을 이해하고, 데이터를 관리한다면 더 효율적으로 관리할 수 있을것이다...
