자료구조
- 여러데이터들의 묶음을 저장, 사용하는 방법
- 데이터 자체로는 정보, 즉 의미를 가지기 힘듬
- 분석, 정리, 활용을 해야 의미를 가질 수 있음, 즉 가공을 거쳐야 함.
- 사용 목적에 따라 형태를 구분, 분류
- 각 자료구조가 가진 특징을 학습한다.
- 각 자료구조를 사용하기 적합한 상황을 이해한다.
- 다른 자료구조와의 차이점을 이해하기 위해 자료구조 내부를 직접 구현한다.
- 자료구조를 구현하며, 자료구조의 동작원리를 이해한다.
Stack, Queue, Tree, Graph
Stack
- 데이터를 순서대로 쌓는 자료구조
- Last In First Out
- First In Last Out
- Browser의 뒤로/앞으로 가기 기능
-> 순서대로 1, 2, 3번 페이지를 이동한 경우, PrevPage=[1,2] now=[3] NextPage=[]
-> 4번 페이지로 이동, PrevPage=[1,2,3] now=[4] NextPage=[]
-> 뒤로 가기를 실행, PrevPage=[1,2] now=[3] NextPage=[4]
-> 뒤로 가기를 또 실행, PrevPage=[1] now=[2] NextPage=[3,4]
-> 앞으로 가기를 실행, PrevPage=[1,2] now=[3] NextPage=[4]
Queue
- 데이터를 줄을 세워 대기시키는 자료구조, Stack과 반대되는 개념
- First In First Out
- Last In Last Out
- 고속도로의 톨게이트와 유사한 구조로 이해
- 데이터가 입력된 순서대로 처리될 때 사용
- Printer의 인쇄 작업에 사용
- CPU는 임시 기억 장치인 버퍼에 빠르게 인쇄할 내용을 전달하고 다음 작업 수행
- Printer의 출력 시간은 상대적으로 느림, 버퍼에 저장된 인쇄 작업을 순차적으로 실행함(버퍼링)
Graph
- 자료구조의 그래프는 거미줄과 같은 복잡한 네트워크 망의 모습
- 점을 정점(vertex), 선을 간선(edge)라고 함
- 비가중치 그래프는 가중치 값이 없어 추가적인 정보를 파악할 수 없음
- 무(방)향그래프(undirected graph): 서로 오가는게 가능 (<-> 단방향(directed))
- 진입차수(in-degree) / 진출차수(out-degree): 한점에 진입 또는 진출하는 간선의 수
- 자기 루프(self loop): 간선이 곧바로 자기 자신에게 진입, 다른 정점을 거치지 않아야 함
- 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있어야 함
- 인접(adjacency): 두 정점간에 간선이 직접 이어진 경우
(인접 행렬: 모든 경우의 수를 가져 메모리 큼, 인접 리스트: 정점이 인접한 리스트, 상대적으로 작음)
Tree
- 무방향 그래프의 한 구조, 나무를 뒤집은 모양의 구조(하나의 뿌리에서 가지를 뻗은 형태)
- 루트(Root)라는 꼭짓점 데이터를 시작, 간선으로 연결됨, 각 데이터를 노드(Node), 노드가 상하계층으로 연결되면 부모/자식 노드로 표현, 자식이 없는 트리 구조의 끝지점 노드는 리프 노드(leaf)
- 깊이(depth): Root=0 === lv1, lv2~lvEnd의 깊이는 레벨-1
- 레벨(level): 같은 깊이를 가진 노드를 묶어서 레벨로 표현, 같은 레벨은 형제 노드(sibling Node)
- 높이(height): 각 리프는 0으로 기준, 부모는 가지가 여러개일 때 가장 큰 값을 높이로 가짐
- 서브 트리(sub tree): 루트의 내부에, 트리구조를 갖춘 작은 트리를 말함
- 예시값으로는 디렉토리 구조, 토너먼트 대진표, 가계도, 조직도 등
Binary Tree (Binary Search Tree)
- 이진 트리, 이진 탐색 트리: 트리의 형태 중 가장 많이 쓰임
- 정 이진 트리(Full binary tree): 각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
- 포화 이진 트리(Perfect binary tree): 모든 리프의 레벨이 동일, 모든 레벨이 채워져 있는 트리
- 완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
- 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징
- 이분 탐색 트리는 루트를 기준, 작은 수는 왼편, 큰 수는 오른편에 배치한다
배치 한 후에 데이터를 검색할 때에, 배치했던 기준을 가지고 찾으면 빠르게 탐색이 가능하다
Tree traversal
트리 순회: 특정 목적으로 모든 노드를 한 번씩 방문, 항상 왼쪽부터 다음에 오른쪽
A
B C
D E F G
H I J K L M N O
[포화 이진 트리로 구현한 예시]- 전위 순회(Preorder): 루트에서 시작, 순차적으로 순회
A - B - D - H - I / - E - J - K // - C - F - L - M / - G - N - O - 중위 순회(Inorder): 끝에서부터 시작, 왼쪽을 돌고 올라와서 루트를 거쳐 오른쪽으로 이동
H - D - I / - B - / J - E - K // - A - // L - F - M / - C - / N - G - O - 후위 순회(Postorder): 끝에서부터 시작, 루트를 마지막에
H - I - D / J - K - E / - B - // L - M - F / - N - O - G / - C - // A
BFS / DFS
그래프의 탐색은 하나의 정점을 출발, 모든 정점을 한 번씩 방문(배열처럼 정렬 상태가 아니므로)
BFS(Breadth-First Search)
가까운 정점부터 탐색, 멀어지는 순으로 같은 거리값의 정점을 탐색, 이후 다음 거리값으로 넘어감
너비 우선 탐색, 최단 경로를 찾을 때 사용, 최악의 경우 모든 경로를 다 탐색
DFS(Depth-First Search)
하나의 경로를 끝까지 탐색, 찾는 값이 없으면 다음 경로로 이동
깊이 우선 탐색, BFS보다 탐색 시간은 조금 오래 걸려도, 모든 노드를 완전히 탐색한다
