자료구조란?
자료(Data)의 집합을 의미하며, 각 원소들을 논리적으로 정의된 규칙에 따라 정리하여, 자료에 대한 처리를 효율적으로 수행할 수 있도록 구조화한 것이다.
자료구조를 사용하는 이유는?
- 자료를 더 효율적으로 저장하고, 2. 관리하며, 3. 잘 선택된 자료구조는 실행시간을 단축시켜주거나 4.메모리 용량의 절약을 이끌어 내기 때문이다.
→ 이를 위해서는 구현에 초점을 맞추기 보다는,어떻게 사용할지를 고민해 보아야한다. (어느 시점에 데이터를 삽입할 것인지? 데이터를 어떻게 사용할 것인지?)자료구조의 선택 기준은?
자료의 처리 시간/ 크기/ 활용 빈도/ 갱신 주기/ 프로그램에서의 용이성을 고려해야한다.
→ 검색 알고리즘을 구현할 때, 자료의 크기가 크다면Linear search보다는Binary Search방법이 더 효율적이다!
시간 복잡도(BIG-O)
알고리즘은 초, 시간 단위로 우수성을 평가하지 않는다. (시간 단위는 개인 컴퓨터의 하드웨어가 결정하기 때문이다.) 따라서, 알고리즘 평가 방법 중 하나인 시간복잡도는 완료까지의 절차 수를 기준으로 평가한다. 즉 STEP이 기준이다.
시간복잡도를 알아야하는 이유?
시간복잡도를 이용하면 알고리즘 분석을 빠르게하여, 언제 어떤 방법의 알고리즘을 사용해야하는지 빠른 판단을 돕는다. 시간복잡도가 알고리즘이 미래에 어떻게 작동할지 예상 가능하도록 하기 때문이다.
- 빅오 표기법의 두 가지 특징
- 상수항 무시
- 영향력 없는 항 무시
→ 입력값(n)이 충분히 크다고 가정하기 때문임
O(1)
: input의 크기와 상관없이 문제를 해결하기 위해 한 단계만 처리한다.
print(arr[0]) // 100번을 print해도 완료까지는 1단계만 필요하다.
arr.pop() // 배열의 마지막 요소제거를 위해서는 1단계면 충분하다. O(log n)
: 문제 해결에 필요한 단계들이 연산마다 줄어든다.
→ 이진검색 알고리즘이 대표적임
→ input이 두배가 되어도 단계는 1단계만 증가함
O(n)
: input과 step이 1:1 관계를 가진다.
→ 선형검색 알고리즘이 대표적임
→ 배열의 모든 요소를 탐색하는 반복문도 이에 해당함
O(n^2)
: input의 제곱이 step임
→ 중첩 반복문(Nested loops)이 이에 해당함
선형 자료 구조
자료를 1:1 관계로 나열시킨 형태이다.
✓ 배열(Array)
-
특징
- 같은 타입의 변수들로 이루어져 있다.
- 배열의 크기는 컴파일시 정해진다.
- 한 메모리 공간 안에 데이터를 나란히 저장한다.
- 인덱스를 가지고 있어 순서가 있으며 중복을 허용한다.
-
장점
-Reading에 적합한 자료구조이다.
- 인덱스만 알면 Random access을 이용하여 데이터에 원스텝 접근이 가능하기 때문이다.
- 따라서 시간복잡도는 O(1)이다. -
단점
Searching
- 데이터의 인덱스를 모른다면 모든 메모리를 뒤져야한다. → 시간복잡도 O(n)
Insert,Delete
- 배열은 데이터를 나란히 저장하며, 각 요소는 인덱스를 가진다.
- 따라서 배열의 중간, 혹은 맨 앞에 데이터를 추가, 삭제하고 싶다면 나란히 저장된 배열의 위치를 밀어내며 인덱스 값을 바꿔준 후에 생긴 공간에 데이터를 추가해야한다. → 시간복잡도 O(n)
✓ 연결 리스트(Linked list)
- 특징
- 연결리스트는 배열의 단점을 보완한 자료구조이다.
- 데이터를 나란히 저장하지 않고, 떨어진 공간에 저장하여 배열에서 데이터 변경(insert, delete)시 발생하는 비효율을 제거하였다.
- 또한 배열처럼 미리 데이터 공간을 확보하지 않고 원하는 때에 메모리 공간을 할당해서 사용한다.
- 떨어진 공간에 저장된 데이터를 연결하기 위해, 데이터 + 포인터(주소)를 하나의 노드로 저장한다.
- 종류
- 싱글 연결 리스트 : next 포인터만 가지고 있어, 단방향으로만 진행 가능
- 이중 연결 리스트 : next, prev 포인터를 가지고 있어 노드의 양방향으로 진행 가능. 따라서 유리한 위치에서 탐색 시작 위치(head or tail)를 정할 수 있음
- 원형 이중 연결 리스트 : 마지막 노드의 포인터가 head 노드를 가르키고 있음 - 장점
Insert,Delete
- 데이터를 변경하기 위해 배열처럼 인덱스를 미뤄가며 공간을 확보할 필요가 없다.
→ Insert : 새로운 노드를 추가하고 포인터만 변경하면 된다.
→ Delete : 노드를 삭제하고 포인터만 변경하면 된다.
→ 시간복잡도 O(1) - 단점
Reding,Searching
- 배열처럼 인덱스로 데이터에 접근할 수 없기 때문에 head부터 원하는 데이터가 위치한 곳까지 one by one 순회해야한다. (싱글 연결 리스트의 경우) → 시간복잡도 O(n)
저장공간 효율 낮음
- 노드에는 다음 데이터 연결 정보를 저장하는 별도의 데이터 공간이 추가로 필요하여, 저장공간은 효율이 높지 않다.
✓ 스택(Stack)
- 특징
- LIFO(Last In First Out)
- 데이터는 한쪽면에서만 추가되고 빠질 수 있다.
- 위에 쌓인 데이터가 모두 빠져야 맨 아래의 데이터(first in)에 접근이 가능하다.
- 마지막 데이터 삭제는 pop(), 마지막 데이터 추가는 push() 메소드를 사용할 수 있다.
- 마지막 요소의 추가, 삭제는 인덱스 이동이 필요하지 않기 때문에 배열에서 용이하다.
- 적합한 용도
서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 유용하게 쓰인다.
- 웹 브라우저 방문 기록(뒤로가기)
- 실행 취소(undo)
✓ 큐(Queue)
- 특징
- FIFO(First In First Out)
- 데이터는 양방향에서 추가되고 빠진다.
- 맨 앞(front)에서 데이터가 빠지는 것을dequeue, 맨 뒤(rear)에서 데이터가 추가되는 것을enqueue라고한다.
- 배열에서 큐 사용은 요소 이동에 따른 시간복잡도를 갖게한다. 연결리스트에서 사용하면 이 문제는 해결된다.
- 적합한 용도
- 스레드 행렬
- 네트워크 접속 행렬
비선형 자료 구조
자료 앞, 뒤로 여러개의 자료가 존재할 수 있는 구조이다. 자료의 관계는 1:n, n:n이 될 수 있다.
✓ 그래프
-
특징
- 정점(vertex)과 간선(edge)으로 이루어진 자료구조이다.
- 정점 : 노드(node)라고도 하며, 데이터가 저장된다.
- 간선 : 링크라고도 하며, 노드간의 관계를 나타낸다.
- 루트 노드, 부모와 자식 관계 개념이 존재하지 않는 점이 트리 구조와 다르다.
-
적합한 용도
- GPS에서 위치와 경로 나타내기
✓ 트리
-
특징
- 무방향 그래프 중 하나로 정점과 간선으로 이루어진다.
- 자료구조를 직관적으로 전시하며,효율적인 자료 탐색을 제공한다.
- 부모와 자식 관계가 존재하여 계층적 데이터 구조를 가진다.
- 루트노드, 내부노드, 리프노드 등이 있다. -
주요 용어
- 높이(height) : 트리의 높이는 누트노드부터 리프노드까지 가장 긴 거리이다.
- 깊이(Depth) : 루트노드부터 특정노트까지의 최단거리를 의미하기 때문에, 깊이는 각 노드마다 다르다.
- 레벨(Level) : 보통 깊이와 같은 의미를 가진다. 노드를 0레벨 혹은 1레벨로 할 수도 있다.
- 서브트리(Subtree) : 트리 구조를 갖춘 작은 트리를 말한다.
-
이진트리(Binary tree)
자식 노드가 두 개 이하인 트리를 의미하며, 두개의 자식은 왼쪽 자식 노드 / 오른쪽 자식 노드로 구분된다. 구분의 기준은 자료의 삽입, 삭제 방법이다.
- 정 이진 트리(full binary tree) : 자식 노드가 0 또는 2개인 이진트리이다.
- 완전 이진 트리(complete binary tree) : 왼쪽에서부터 노드를 채운다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져있다.
- 변질 이진 트리(degenerate binary tree) : 모든 레벨의 자식 노드가 하나이다.
- 포화 이진 트리(perfect binary tree) : 모든 노드가 꽉 채워져있다.
- 균형 이진 트리(balanced binary tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진트리이다.(=마지막 레벨을 제외하고는 균형을 맞춰 자식 노드를 만든다.)
-
이진 탐색 트리(Binary searchig tree)
- 검색, 추가, 삭제가 모두 빠른 자료구조이다. → 시간복잡도 O(log n)
- 오른쪽 노드에는 루트노드보다 큰 값을, 왼쪽 노드에는 루트노드보다 작은 값을 저장하기 때문이다
- 아래 그림을 보면 10을 찾기 위해서는 왼쪽 노드만 검색하면 된다.
- 하지만 균형잡힌 트리가 아닌 경우 노드가 한쪽으로만 쏠려(선형적인 트리 형태) 최악의 경우엔 → 시간복잡도 O(n)이 된다.
- Insert 구현
- Delete 구현
-
AVL 트리
최악의 선형적인 트리가 되는 것을 방지하기 위해, 스스로 균형을 잡는 이진 탐색 트리이다. 데이터를 삽입, 삭제할 때마다 균형을 맞추기 위해 트리 일부를 왼쪽, 오른쪽으로 이동시키며 균형을 잡아 두 자식의 서브트리의 높이는 최대 1만큼만 차이 나도록한다. → 시간복잡도는 언제나 O(log n)이다.
-
적합한 용도
- 컴퓨터 디렉토리 등
✓ 힙(Heap)
- 특징
- 힙(heap : 더미)은 완전 이진 트리 기반의 자료구조이다.
- 완전 이진 트리이기 때문에 빈 공간이 없어 배열을 사용하여 구현하기 용이하다. 즉, random access가 가능하다.
- 최소 힙과 최대 힙이 있다.
최대 힙(max heap)
루트노드의 데이터는 모든 자식 노드 데이터 보다 커야한다. 모든 서브트리도 동일한 규칙을 따른다. → 따라서 최댓값을 찾기 위한 시간복잡도는 O(1)이다.
최소 힙(min heap)
루트노드가 가장 작아야한다.
-
Insert 구현 (max heap 기준)
1️⃣. 힙의 가장 마지막 원소에 원하는 값을 삽입한다.
2️⃣. 부모가 삽입 원소보다 작다면(Max_Heap기준) 부모와 자식의 값을 교환한다.
3️⃣. 2번에서 부모가 없거나, 부모가 자식보다 클 경우에 종료
→ 실행 단계는 이진 구조를 따라 트리 높이에 영향을 받기 때문에, 시간복잡도는 O(log n)이다.
-
Delete 구현 (max heap 기준)
1️⃣. 루트노드를 삭제하고 힙의 마지막 노드를 루트로 가져온다.
2️⃣. 가져온 루트와 자식노드를 비교하고 가져온 노드가 작을 경우 자식과 위치 변경
3️⃣. 자식 노드가 더이상 없거나, 자식보다 클 경우 종료
→ 시간복잡도는 O(log n)
-
적합한 용도
- 최댓값, 최솟값을 찾는데 유용하다.
✓ 해시테이블(Hash table)
-
특징
- Key : value의 구조를 가진다.
- 해시함수를 이용하여 key값을 해시코드로 반환 받고, 어떤 양의 정수(보통은 해시 테이블의 크기)로 나머지 연산을하여 인덱스 번호를 얻는다.
- 이 인덱스 번호로 배열에 데이터를 저장한다.
→ key로 인덱스 번호를 얻을 수 있기 때문에 검색이 빠르다.
→ 시간복잡도 O(1)
- 각 배열방(아래 이미지의 Index 0 , 1 ...)은 연결 리스트로 되어 있어, 데이터를 추가/ 삭제하여도 시간복잡도는 O(1)이다.
- 따라서, 방대한 양의 데이터를 검색/ 추가/ 삭제할 때 적합한 자료 구조이다.
-
단점
1개의 배열방에 여러 데이터가 저장되는 해시충돌을 피할 수 없다.
해시충돌이 발생할 경우엔, 인덱스로 접근한 배열방에서 해당 key 값을 찾기 위해 모든 요소를 순회해야 하기 때문에 시간복잡도는 O(n)이 된다. -
해시 충돌이 발생하는 이유
1️⃣. 서로 다른 Key 값이지만, 동일한 해시코드로 반환받는 경우
Key 값은 문자열이기 때문에 그 가짓수가 무한하다. 하지만 해시코드는 정수이기 때문에, 알고리즘이 아무리 좋아도 어떤 Key들은 중복되는 해시코드를 가질 수 밖에 없다.
2️⃣. 서로 다른 해시코드이지만, 동일한 인덱스로 바뀌는 경우
배열방은 한정되어 있기 때문에, 다른 해시코드가 동일한 인덱스를 얻게 되면 같은 배열방에 배정받게 된다.
