티스토리 뷰
자료구조를 사용하는 이유
- 데이터를 적절한 방법으로 저장, 관리하여 메모리를 효율적으로 사용하기 위해 사용한다. 때문에 적절한 자료구조의 사용은 메모리 절약과 실행시간 단축을 가져온다.
- 자료구조를 선택하는 기준은 자료의 처리시간, 탐색 빈도, 크기, 갱신 정도를 종합하여 선택한다.
재귀란?
- 자기 자신을 호출하는 함수이다.
- 재귀 호출은 Stack 메모리에 쌓인다. 때문에 메모리 용량이 초과하면 OverFlow가 난다.
- 종료 조건에 도달하면 종료한다.
Q 하노이의 탑, 피보나치수열
연결 리스트 (Linked List)
- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결된 자료구조이다.
- 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
- 검색 O(N)
- 헤드 노드부터 원하는 값을 찾을 때까지 이동하기 때문에
- 삽입/삭제 O(N)
- 해당 원소를 O(N) 시간 동안 찾고 O(1) 시간 동안 삽입, 삭제를 위한 포인터를 변경한다.
- 트리구조의 근간이 된다.
스택 (Stack) & 큐 (Queue)
- 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 자료구조이다.
- 스택은 자료가 쌓인다.
- 큐는 한쪽 끝에서는 자료를 넣기만 하고 반대쪽에서는 자료를 빼기만 하는 FIFO(First In First Out) 자료구조이다.
- 큐는 먼저 들어간 데이터가 먼저 나온다.
Q 스택 2개를 이용하여 큐를 구현하라
트리 (Tree) & 힙 (Heap) & 우선순위 큐 (Priority Queue)
- 트리는 정보를 계층적 관계로 표현하는 비 선형 자료구조이다.
- 구성요소
- Node - 트리 구성하는 각각의 요소
- Edge - 트리를 구성하기 위해 노드와 노드를 연결하는 선
- Root Node - 트리구조에서 최상단에 있는 노드
- Leaf Node(Terminal Node) - 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node - Leaf Node를 제외한 모든 노드
- 이진트리 (Binary Tree)
- 이진트리는 트리를 구성하는 노드들의 최대 차수(Degree)가 2인 노드들로 구성되는 트리
- 이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i
- 깊이가 K인 이진트리가 가질 수 있는 최대 노드의 수는 2^k - 1
- 완전 이진트리
- 마지막 레벨을 제외한 모든 레벨이 채워져 있고 마지막 레벨의 모든 노드들이 왼쪽부터 차례대로 채워진 이진트리
- 포화 이진트리
- 모든 레벨의 노드가 꽉 차서 포화상태인 이진트리
- 개수는 2^K - 1
- BST (Binary Search Tree)
- 이진트리 이면서 모든 노드가 자신의 왼쪽 서브 트리에는 작은 키값이, 오른쪽 서브트리에는 큰 키값이 오는 규칙을 만족하는 노드를 가진 트리
- 저장된 키는 유일
- 부모 노드는 왼쪽 자식의 값보다 크다.
- 부모 노드는 오른쪽 자식의 값보다 작다.
- 왼쪽, 오른쪽 서브 트리도 이진 탐색 트리이다.
- 탐색 연산은 평균 O(logN)
- * 한쪽으로만 계속 삽입이 일어나면 O(N) 이기 때문이다. (AVL, Red-Black Tree)
- 순회
- 이진트리에서 순회는 방문 순서를 의미한다.
- 전위 순회 - Root, Left, Right
- 중위 순회 - Left, Root, Right
- 후위 순회 - Left, Right, Root
Q Binary Search Tree 구현, BST 인지 확인하는 알고리즘 구현
Heap
- 힙은 부모 노드의 키값이 자식 노드의 키 값보다 항상 크거나 작은 자료구조이다.
- Max Heap을 기준으로 루트 노드에 있는 값이 제일 크므로 최댓값을 찾는데 O(1)의 시간이 걸린다.
- 삽입
- 힙의 가장 마지막 원소에 원하는 값을 삽입한다.
- 부모가 삽입 원소보다 작으면 부모와 자식의 값 교환
- 2에서 부모가 없거나 (루트 노드) , 부모가 자식보다 클 경우 종료
- 삭제
- 루트 노드를 삭제하고 힙의 마지막 노드를 루트로 가져온다.
- 루트 노드와 자식 노드를 비교해 가져온 노드(부모 노드)가 작으면 교환
- 자식 노드가 없거나, 자식들보다 클 경우 종료
Q Max Heap 구현, Heapify (힙 구조로 만드는 알고리즘) 구현
Priority Queue
- 우선순위를 가지는 데이터를 힙 구조에 저장하는 것을 우선순위 큐라고 한다.
- 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다.
- 보통 Max Heap을 이용하여 구현한다.
- Max Heap을 사용하는 이유는 배열, 연결 리스트로 구현 가능하지만 배열은 Shift 해주어야 하고 연결 리스트는 원하는 원소까지 탐색이 오래 걸린다.
- 운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등에 사용된다.
해시 (Hash)
- Key와 Value가 하나의 쌍을 이루는 데이터 구조이다.
- Key를 Hash Function을 이용하여 해시 값(Index)으로 만든 뒤 배열을 활용하여 저장한다.
- *** 삽입, 삭제, 검색 모두 평균 O(1)의 시간이 걸린다. ***
- Collision이 많이 일어나는 경우 최악 O(N)까지 걸릴 수 있다.
- Collision (충돌)
- Hash값이 동일하여 값이 있는 곳에 다시 저장해야 할 경우 Collision이 일어난다.
- 해결방안
- Chaining
- 연결 리스트를 활용하여 기존 자료에 이어 다음 자료를 저장한다.
- 메모리 효율은 높아지지만 한쪽에만 계속 저장될 수 있다.
- Open Addressing
- 그 값 다음에 규칙에 맞게 저장한다.
- 미리 공간을 잡아둬야 하기 때문에 공간 복잡도가 커진다.
- 순서가 있는 배열에 어울리지 않는다.
그래프 (Graph)
- 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조이다.
- 연결되어 있는 객체 간의 관계를 표현할 수 있다.
- 사이클이 가능하며 사이클이 없는 그래프를 트리라고 할 수 있다.
- 그래프의 특징
- 네트워크 모델
- 2개 이상의 경로 가능
- DFS, BFS 순회
- 순환, 비순환
- 방향, 무방향
- 깊이 우선 탐색 (DFS) (Depth-First Search)
- 한 노드에서 시작해 다음 분기(Branch)로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법
- 모든 노드를 탐색하고자 할 때 사용한다.
- 너비 우선 탐색 (BFS) (Breadth-First Search)
- 한 노드에서 시작해 인접 노드를 먼저 탑색
- 최단 경로를 찾고자 할 때 사용
Q 그래프 구현(인접 행렬, 인접 리스트)