자료구조란?
- 대량의 데이터를 효율적으로 관리할 수 있는 데이터 구조
- 프로그래밍에서 데이터 특정에따라 어떤 데이터 구조를 사용하느냐에 따라 코드 효율이 달라진다.
배열(Array)
- 같은 종류의 데이터를 순차적으로 연결된 공간에 나열하는 자료 구조
- 각 데이터를 인덱스에 대응하도록 구성한다.
장점
첫 데이터의 위치에서 상대적인 위치(인덱스 번호)로 데이터를 접근하므로, 빠른 접근이 가능하다.
- 인덱스 위치를 안다면, 상수 시간으로 접근 가능하다 O(1)
단점
데이터의 길이가 정해져있으므로, 크기 이상의 데이터를 저장할 때 새로운 배열을 만들어야한다.
링크드리스트( LinkedList)
- 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
<-> 배열, 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 하나의 데이터를 저장할때,
1. 데이터를 저장할 공간과 (Data, 노드)
2.다음 데이터 주소를 저장하는 공간(Next, 포인터)을 생성한다.
장점
- 자료구조의 크기를 미리 정하지 않고, 새로운 데이터를 저장할 때만 데이터를 할당한다. (불필요한 메모리 공간을 소모 x)
단점
- 데이터를 저장할 때, 데이터를 위한 공간 이외에 연결을 위한 데이터 공간이 추가적으로 필요하므로, 저장공간이 낭비된다.
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다 O(N)
스택(Stack)
스택은 박스 쌓기에 비유할 수 있다. 박스는 아래에서 위로 차곡차곡 쌓고, 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 한다. 이런 구조를 선입후출(First In Last Out) 또는 후입선출(Last In First Out)구조라 한다.
큐(Queue)
큐는 대기 줄에 비유할 수 있다. 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 된다. 나중에 온 사람일수록 나중에 들어가기 때문에 ‘공정한’ 자료구조라고 비유된다. 이러한 구조는 선입선출(First In First Out) 구조라고 한다.
그래프(Graph)
· 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조
· 그래프를 구현하는 2가지 방식:
1. 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식
ex) 플로이드 워셜 알고리즘에서 이용
2. 인접 리스트(Adjacency List): 리스트를 사용하는 방식
ex) 우선순위 큐를 이용하는 다익스트라 알고리즘에서 이용
· 그래프 구현 방식에 따라 메모리와 속도 측면에서 구별되는 특징이 있음
- 노드의 개수가 V, 간선의 개수가 E인 그래프의 경우:
| 인접 행렬 | 인접 리스트 | |
| 간선 정보를 저장하는 메모리 공간 | O(V^2) | O(E) |
| 특정 노드 A에서 다른 노드 B로 이어진 간선의 비용 측정 |
O(1) | O(V) |
해시 테이블(Hash Table)
- 키(Key)에 값(Value)을 매핑할 수 있는 자료 구조
- 해시 테이블 자료구조에 키를 입력하면 해시 함수(hash funciton)는 값을 저장할 수 있는 공간의 주소를 반환한다.
- 해시 함수: 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
- 해시(Hash), 해시 값(Hash Value), 해시 주소(Hash Address): 해싱 함수를 통해 리턴된 고정 길이의 값
- 슬롯(slot): 해시 테이블에서 한 개의 데이터를 저장할 수 있는 공간
트리(Tree)
· 노드와 간선(Branch)를 이용하여, 사이클을 이루지 않도록 구성한 데이터 구조
- 그래프의 일종
- 노드(정보의 단위)와 노드 사이에 하나의 간선만 존재
- 계층형 자료구조
· 용도: 이진 트리 구조로 검색 알고리즘 구현을 위해 많이 사용함
- 내부 데이터를 이진 탐색 등과 같은 탐색 기법으로 빠르게 탐색 가능
- 예: 데이터베이스, 파일시스템처럼 많은 양의 데이터를 데이터를 관리 (계층적이고, 정렬된 데이터)
· 트리 자료 구조의 특징/용어
- 트리는 부모와 자식 노드의 관계로 표현한다.
- Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Brach로 연결된 노드의 깊이
- Depth: 트리에서 Node가 가질 수 있는 최대 Level
- Siblings(Brother Node): 동일한 부모 노드를 가진 노드
- 루트노드: 트리의 최상단 노드
- 단말 노드(leaf node, Terminal Node): 트리의 최하단 노드, 자식 노드가 하나도 없는 노드
- 서브 트리: 트리의 일부를 떼어내도 트리 구조이며, 이를 서브 트리라고 한다.
이진 탐색 트리 (BST, Binary Search Tree)
· 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
· 이진 트리 자료 구조의 특징
- 부모 노드보다 왼쪽 자식 노드가 작다
- 부모 노드보다 오른쪽 자식 노드가 크다
- 즉, 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
· vs HashTable: 단일 검색에는 HashTable보다 느린 속도를 보이지만, 범위 검색(예:0~10000)에는 HashTable 보다 유리하다.
또한 메모리도 더 효율적으로 사용한다. HashTable은 키와 값을 연결하기 위한 포인터가 추가적으로 필요하다.
· 코딩 테스트에서 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 고려하자
· 트리 순회
- 전위 순회: [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회
- 중위 순회: [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회
- 후위 순회: [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회
힙(Heap)이란?
· 데이터에서 최댓값 및 최솟값을 빠르게 찾기 위해 고안된 완전이진트리(complete binary tree)
- 완전이진트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
· 다음과 같은 힙 속성(property)을 만족한다.
- A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
· 부모 노드가 자식 노드들보다 크다면 최대 힙(Max Heap)구조,
부모 노드가 자식 노드들보다 작다면 최소 힙 구조(Min Heap)라고 한다.
· 사용 이유(장점):
- 데이터의 최대값과 최소값을 찾는데 매우 적은 비용 O(1) 이 소모 된다. < - > 배열 O(n)
· 단점: 삽입, 삭제시 때 최대, 최소 값을 찾기 위해 재정렬하는 비용 O(log n)이 소모된다.
· 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나다.
힙과 이진 탐색 트리의 공통점과 차이점
· 공통점: 둘 다 이진 트리다.
· 차이점:
- 구조의 차이:
이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 크다.
(최대)힙은 부모 노드가 가장 크고, 왼쪽과 오른쪽 노드의 크기는 조건이 없다. (둘 중 누가 커도 상관 없다)
- 목적의 차이: 이진 탐색 트리는 특정한 크기의 데이터 탐색, 힙은 최대/최소값 탐색을 위한 구조다.
TODO: 힙의 추가, 삭제 동작 방식
출처
이것이 취업을 위한 코딩테스트다
fastcampus - 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online
댓글