자료구조 Basic

 

 

이번 블로그에서는 자료구조의 기본적인 내용을 총 정리해보고자 한다.

 

1.  자료 구조의 정의

• 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.

알고리즘 문제를 풀다보면 자연스럽게 여러가지 자료구조를 배울 수 있게 된다.

자료구조가 무엇이 있는지 구별하면서 사용을 한다면 좀 더 이해하기 쉽고 알고리즘 해결 능력이 향상될 것이라 믿는다.

 

 

 

 

2. 복잡도

복잡도는 크게 시간 복잡도와 공간 복잡도로 나뉜다.

쉽게 말해서 복잡도는 해당 알고리즘이 얼마나 시간이 걸리며 얼마나 공간을 차지하는 지를 의미한다.

 

시간 복잡도

• 표기법 : 빅오 표기법

공간 복잡도

• 표기법 : 보통 MB 단위

시간복잡도 속도 빠른 순서

• O(1) > O(N) > O(logN) > O(N^2)

 

 

 

 

3. 선형 자료 구조

자료구조는 크게 선형, 비선형으로 나뉘고 여러가지 자료구조가 이 카테고리안에 속한다. 먼저 선형 자료구조에 대해서 알아보려고 한다.

종류 : 연결리스트, 벡터, 배열, 스택, 큐

 

 

 

3-1. 연결리스트

정의

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조.

 

시간복잡도

• 삽입, 삭제 : O(1) -> 포인터만 변경해주면 되므로
• 접근, 탐색 : O(N) -> 포인터를 따라 찾으려는 노드를 찾는데, 최악의 경우 총 N개의 노드를 모두 탐색해야 하므로

종류

• 싱글 연결 리스트 : next 포인터만 가진다.
• 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
• 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.

자바

LinkedList<Integer> linkedList = new LinkedList<>();

 

 

 

3-2. 배열

정의

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리에 위치해 있는 데이터를 모아놓은 집합으로 중복을 허용하고 순서가 존재한다.

 

시간복잡도

• 삽입, 삭제 : O(N) -> 삽입, 삭제시 배열의 위치를 하나하나 옮겨가며 삽입, 삭제를 해야하므로
• 탐색, 접근 : O(N) or O(1) -> 랜덤접근시 O(1), 순차적 접근 시 O(N)

순차적 접근 vs 랜덤 접근

• 순차적 접근 : 데이터가 저장된 순서로 접근 하는 과정
• 랜덤 접근 : 임의의 위치에 있는 데이터에 접근하는 과정, 즉, 운좋으면 시간복잡도가 O(1)이 된다.

자바

int[] array = new int[3];

List<Integer> array = new ArrayList<>();

 

(+) 연결리스트 vs 배열

- 탐색은 배열이 빠르고 삽입, 삭제는 연결리스트가 빠르다.

 

 

 

3-3. 벡터

정의 

동적으로 요소를 할당할 수 있는 동적 배열을 의미한다. 컴파일 시점에 개수를 모른다면 벡터를 써야한다.

중복을 허용하고 순서가 잇고 랜덤접근이 가능하다. 

- 생성시 배열로 생성

 

시간 복잡도

• 삽입, 삭제 : O(1)(맨뒤나 맨앞 삽입, 삭제) or O(N)(맨뒤나 맨앞이 아닌 삽입, 삭제)
• 탐색, 접근 : O(N) -> 배열과 동일

벡터는 일종의 배열이다. 차이점은 동적으로 생성되는 배열이라는 점인데, 예를 들어, 알고리즘 문제 유형에서 이런 경우가 있다. 간선의 수가 m이고 컴파일시 간선의 정보가 주어진다고 했을때, 이 간선 정보를 배열에 저장을 해야한다. 이럴때 사용되는 배열의 형태가 벡터이다.

 

삽입, 삭제시 즉 컴파일에 간선정보가 작성될때마다 맨앞이나 맨뒤에 삽입, 삭제를 하면 O(1)이지만 그렇지 않다면 O(N)이 된다.

이 후 탐색, 접근은 이미 저장된 상태에서 진행되므로 배열과 동일하다.

 

 

 

3-4. 스택

정의

가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질(LIFO)를 가진 자료구조이다.

DFS 알고리즘에 사용되며 DFS알고리즘은 재귀함수를 통해 구현한다. 또한, 웹 브라우저 방문 기록(뒤로가기 버튼)등에 쓰인다.

- 후입 선출

- 생성시 배열로 생성

- 깊이 우선 탐색

 

자바

 

List<Integer> stack = new ArrayList<>();

stack.remove(array.size()-1);

stack.add(1);

 

 

시간복잡도

• 삽입, 삭제 : O(1) -> 후입선출 방식이 정해져 있어 삽입, 삭제시 맨뒤에 데이터를 삽입, 삭제하기 때문에
• 탐색, 접근 : O(N) -> 배열과 동일

 

 

 

3-5. 큐

정의

먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO)를 지닌 자료구조

BFS 알고리즘에 사용되며 큐 자료구조를 통해 구현된다.

- 선입 선출

- 생성신 큐로 생성

- 너비 우선 탐색

 

자바

List<Integer> queue = new ArrayList<>();

queue.remove(0);

queue.add(1);

 

시간복잡도

• 삽입, 삭제 : O(1) -> 삽입시 맨뒤에 삽입하고, 삭제시 맨앞에서 삭제하므로
• 탐색, 접근 : O(N) 

 

 

 

 

 

4. 비선형 자료 구조

일렬로 나열되지 않고 자료 순서나 관계가 복잡한 구조를 의미하며 일반적으로 트리나 그래프를 의미.

종류 : 그래프, 트리, 힙, 우선순위 큐, 맵, 셋, 해시테이블

 

4-1. 그래프

정의

정점, 간선(단방향, 양방향), 비용 등 으로 이루어진 자료구조를 의미

 

자바

int[][] graph = new int[3][3];

List<List<Integer>> graph = new ArrayList<>();

 

 

4-2. 트리

정의

그래프 중 하나로 정점, 간선 으로 이루어져 있지만 계층적으로 데이터가 구성된 집합을 의미, 루트노드, 내부노드, 리프노드 등으로 구성되어 있다. 또한, 항상 간선수는 노드수 - 1의 형태를 가진다.

• 루트 노드 : 가장 위에 있는 노드
• 내부 노드 : 루트노드와 리프노드 사이에 있는 노드
• 리프 노드 : 가장 아래에 있는 노드로 더 이상 자식이 없는 노드

 

• 깊이 : 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 의미.
• 높이 : 루트 노드 부터 리프 노드까지의 거리 중 가장 긴 거리를 의미.
• 레벨 : 1번 노드를 0레벨로 가정한다면 층 당 1레벨 씩 증가
• 서브 트리 : 트리 내의 부분집합

 

종류

• 이진 트리 : 한 노드당 자식의 노드 수가 두개 이하인 트리를 의미
  • 정이진 트리 : 한 노드당 자식 노드가 0개또는 두개를 의미
  • 완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진트리를 의미, 마지막 레벨을 제외하고 모든 레벨에 노드가 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져있는 트리를 의미.
  • 변질 이진 트리 : 한 노드당 자식노드가 하나밖에 없는 이진 트리
  • 포화 이진 트리 : 모든 레벨에 노드가 꽉차있는 트리
  • 균형 이진 트리 : 한 레벨당 왼쪽과 오른쪽 노드의 높이 차이가 1이하이 이진트리를 의미, map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나.

 

• 이진 탐색 트리 : 한 노드의 자식이 둘 있을 때, 왼쪽 자식 노드는 부모 노드보다 작소 오른쪽 자식 노드는 부모노드가 큰 트리.

       -> 탐색 시간 복잡도 : O(logN) or O(logN)

 

 

• AVL 트리 : 이진 탐색 트리에서 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리를 의미한다. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징을 가진다.

       -> 탐색, 삽입, 삭제 시간 복잡도 : O(logN) - 삽입, 삭제마다 균형이 안맞는 것을 맞추기 위해 트리의 일부를 왼오른쪽으로 회전.

 

 

• 레드 블랙 트리 : 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용, 모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. 라는 규칙 적용

       ->탐색, 삽입, 삭제 시간 복잡도 : O(logN)

 

 

• 신장 트리 : 모든 노드가 연결되어 있지만 사이클이 없는 트리

 

 

 

4-3. 힙

정의

완전 이진 탐색 트리 기반의 자료 구조

 

종류

• 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 크다.
• 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작다.

최대힙의 삽입

- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킨다.

 

최대힙의 삭제

- 최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고 그 이후 마지막 노드와 루트 노드를 스왑하여 또 다시 스왑 등의 과정을 거쳐 재구성된다.

 

 

 

4-4. 우선순위 큐

정의

 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조로써, 이 때, 우선순위는 보통 비용이 작을수록 우선순위가 높다고 정한다.

- 최소힙 또는 최대힙을 기반으로 구현

 

자바

PriorityQueue<List<Integer>> minHeap = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[0]));

PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(Comparator.comparingInt(arr -> -arr[0]));

 

 

4-5. 셋

정의

- 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소가 없고 오로지 희소한 값만 저장하는 자료 구조이다.

 

자바

Set+Hash : Set<String> hashSet = new HashSet<>();

Set+Hash+Linked : LinkedHashSet<String> linkedHashSet  = new LinkedHashSet<>();

 

 

4-6. 맵

정의

- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조.

- 레드 블랙 트리 자료구조를 기반으로 형성되고, 삽입되면 자동으로 정렬된다.

 

자바

Map+Hash : HashMap<Stirng, Integer> hashMap = new HashMap<>();

 

 

 

 

4-7. 해시 테이블

정의

- Map 자료구조를 구현한 자료구조로서 해시 함수를 사용하여 키를 특정 값에 매핑하는 방식으로 속도 향상

- 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간복잡도를 가진다.

 

자바

Table + hash : HashTable<String, Integer> hashTable = new HashTable<>();

 

 

 

 

HashMap vs HashTable

 

• 동기화 : HashMap은 스레드 간의 안정성을 보장하지 않는다. 즉, 동시에 여러 스레드에서 HashMap에 접근하고 수정하는 경우, 별도의 동기화 메커니즘이 필요하다. 반면에 HasbTable은 모든 메서드에 대해 스레드 동기화가 내장되어 있어 스레드 안정성을 제공한다. 따라서 멀티스레드 환경(ex Spring)에서 동시에 HahTable에 접근하는 경우에는 HashTable을 사용하는 것이 안전하다.

 

• Null 허용 여부 : HashMap은 Null값을 허용한다. 즉, null키와 null값 모두를 저장할 수 있다. 즉, 값은 Null이 허용되고 키는 Null을 키 자체로 여기는 경우이다. 반면에, HashTable은 Null 값을 허용하지 않는다. 키 또는 값으로 Null 추가시 NullPointException이 발생한다.

 

• 상속 가능 여부 : HashMap은 AbstractMap 클래스를 상속받아 구현되어 있으며, 추가적인 기능 구현이나 커스터마이징이 가능하다. HashTable은 Dictionary 클래스를 상속받아 구현되어 있으며, 확장이나 수정이 불가능하다.

 

• 성능 : HashMap은 비동기적인 방식으로 동작하므로 일반적으로 Hashtable보다 빠른 성능을 제공한다. 그러나 스레드 동기화가 필요한 경우 HashTable의 성능이 좋을 수 있다.

 

 

동기화 : 하나의 스레드만이 자료구조에 접근하게 하는 방식

주로, 자바에서는 synchronized 키워드, lock 인터페이스로 구현, 이를 통해 접근시 한 스레드만 접근 가능하게 동기화 가능

 

 

정리

HashMap은 스레드 동기화가 필요 없고 null 값을 허용하며, 상속과 커스터 마이징이 가능한 경우에 유용하며, HashTable은 스레드 동기화가 필요하고 null 값을 허용하지 않으며, 추가적인 커스터마이징이 필요하지 않는 경우에 유용하다. 일반적으로는 HashMap을 사용하는 것이 선호된다.