자료구조
자료구조의 분류
스택 (stack)
스택의 특징
- 입력과 출력이 하나의 방향으로 이뤄짐
- LIFO(Last In First Out) || FILO(First In Last Out)
- 저장되는 데이터는 유한하고 정적
- 스택의 크기는 제한되어 있음
- 스택 오버플로우(stack overflow)
스택의 실사용 예제
브라우저의 뒤로 가기, 앞으로 가기 기능
큐 (queue)
- 스택과 반대되는 개념
- 입력과 출구 방향이 다름
- FIFO(First In First Out) || LILO(Last In Last Out)
큐의 실사용 예제
프린터 인쇄작업
유튜브
- 다운로드 된 데이터가 영상 재생에 충분치 않은 경우
- 동영상의 정상적 재생을 위해
- Queue에 모아 두었다가
- 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생함
버퍼링 buffering
컴퓨터 장치들 사이에서 데이터 주고받을 때 각 장치 사이에 존재하는 속도 차이와 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue 사용
Tree
트리 구조와 특징
루트(root)라는 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)로 연결함.
각 데이터를 노드(node)라고 하며 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가짐
깊이
루트로부터 하위 계층의 특정 노드까지의 길이
루트노드는 깊이가 0
레벨
같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현
같은 레벨에 있는 노드를 형제 노드(Sibling Node)
높이
리프 노드를 기준으로 루트까지의 높이
ex) H, I, E, F, J의 높이 => 0
D, G의 높이 => 1
B, C의 높이 => 2
A의 높이 => 3
서브 트리
큰 트리 내부에 트리 구조를 갖춘 작은 트리
이진트리 (binary tree)
자식 노드가 최대 두 개인 노드들로 구성됨
정 이진 트리(Full binary tree)
각 노드가 0개 혹은 2개의 자식노드를 가짐
포화 이진 트리(Perfect binary tree)
정 이진 트리이면서 완전 이진 트리인 경우
모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워진 트리
완전 이진 트리
마지막 레벨을 제외한 모든 노드가 가득 차 있어야 함
마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽은 다 채워져야 함
이진 탐색 트리 (Binary Search Tree)
이진 탐색과 연결 리스트를 결합한 이진트리
이진 탐색 트리 특징
- 각 노드에 중복되지 않은 Key가 있음
- 루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이뤄짐
- 루트 노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이뤄짐
- 좌우 서브트리 모두 이진 탐색 트리
- 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐
- 기존 이진 트리보다 탐색이 빠름
- 루트 노드 키와 찾고자 하는 값 비교
- 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브트리로 탐색 진행
- 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브트리로 탐색 진행
트리 순회
트리의 모든 노드를 한 번씩 방문하는 것
1. 전위 순회 (preorder traverse)
루트 -> 왼쪽노드 -> 오른쪽 노드
부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용
2. 중위 순회 (inorder traverse)
제일 왼쪽 끝 노드 -> 루트 -> 오른쪽 노드
루트를 가운데에 두고 서브트리를 먼저 방문한 후 부모 노드를 방문하는 순회방식
이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰임
3. 후위 순회 (postorder traverse)
제일 왼쪽 끝 노드 -> 루트 거치지 않고 오른쪽으로 바로 이동-> 마지막에 루트 방문
트리 삭제 시 사용 (자식 노드가 먼저 삭제 되어야 상위 노드를 삭제할 수 있기 때문)
그래프 Graph
여러개의 점들이 서로 복잡하게 연결되어 있는 관계
그래프의 구조
- 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있음
- 간접적 관계라면 몇 개의 점과 선에 걸쳐 이어짐
- 점: 정점(vertex)
- 선: 간선(edge)
그래프의 표현 방식 - 인접 행렬
- A의 진출차수는 1개 입니다: A —> C
[0][2] === 1 - B의 진출차수는 2개 입니다: B —> A, B —> C
[1][0] === 1
[1][2] === 1 - C의 진출차수는 1개입니다: C —> A
[2][0] === 1
그래프의 표현 방식 - 인접 리스트
그래프 주요 용어
- 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
- 간선 (edge): 정점 간의 관계 (정점을 이어주는 선)
- 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
- 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프
- 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프
- 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능. 하지만 단방향(directed) 그래프로 구현된다면 편도만 가능. 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현가능.
- 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄.
- 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점.
- 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현 => 다른 정점을 거치지 않음
- 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프.
1. BFS (Breadth-First Search)
너비 우선 탐색
두 정점 사이의 최단 경로를 찾을 떄 사용
- level 1에 있는 모든 경우의 수를 다 본 후 level 2로 넘어감
- 찾는 값이 있는 level 까지 내려가야 함
2. DFS (Depth-First Search)
깊이 우선 탐색
- 리프 노드(자식 없는 노드)가 나올 때까지 끝까지 탐색함
- 찾는 값이 없을 경우 level 1의 다음 노드로 넘어가 또 끝까지 탐색함
