[면접을 위한 CS 전공 지식 노트] 5장 자료구조

1. 복잡도

1.1. 시간 복잡도

1.1.1. 빅오 표기법

시간 복잡도란 "입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간"을 의미한다.

빅오 표기법은 입력 범위 n을 기준으로 실행되는데 가장 오래 걸리는 시간(최악의 경우)을 의미한다. O(n**2)

 

1.1.2. 시간 복잡도의 존재 이유

효율적인 코드로 개선하기 위해 알고리즘의 수행시간을 측정하여 비교하기 위함이다.

시간 복잡도 속도 비교

자료구조 별 평균/최악 시간 복잡도

 

1.2. 공간 복잡도

공간 복잡도는 프로그램을 실행시켰을 때 필요로하는 메모리 공간의 양을 의미한다. 

int a[1004];

 

int는 4byte를 차지하는데, 이때 배열 크기인 1004*4byte가 필요하게 된다. 

1.2.1. C언어의 자료형

c언어의 데이터 타입(자료형)에 따른 바이트 크기

1.2.2. JAVA의 자료형

 

2. 선형 자료 구조

선형 자료 구조란 요소가 일렬로 나열되어있는 자료구조이다.

대표적인 예로, 연결 리스트, 배열, 벡터, 스택, 큐 가 있다. 

 

특징: 데이터 삽입 및 삭제 시 기존 순서가 유지, 배열은 고정 크기지만, 연결 리스트는 동적으로 크기 확장이 가능

장점: 데이터가 순차적으로 배치되어 있어, 순차 탐색이나 처리 작업이 가능하여 정렬 및 탐색 구현이 편함

단점: 중간 요소의 비효율적인 삽입/삭제, 배열의 경우 고정된 크기 때문에 메모리 낭비가 가능하며, 연결리스트 또한 포인터를 저장하므로 추가적인 메모리 소요가 필요하다. 

2.1. 연결 리스트

 

 

맨 앞단 노드: head / 맨 뒷단 노드: tail

 

싱글(단순) 연결리스트: next 포인터만 가짐.

이중 연결 리스트: next 포인터와 prev 포인터를 가짐.

원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next포인터가 헤드 노드를 가르킴.

 

 

• 특징: 동적 크기, 포인터를 이용한 데이터 연결.
• 활용: 삽입/삭제가 빈번한 경우.

 

2.2.  배열

배열에는 같은 자료형의 변수들을 모아 놓은 것이다. 크가가 정해져 있으며, 인접한 메모리 위치에 있는 데이터들을 모아 놓은 집합이므로 순서가 존재한다. 

 

• 특징: 고정 크기, 인덱스를 이용한 빠른 접근.
• 활용: 데이터 저장, 정렬, 탐색.

2.2.1. 랜덤 접근과 순차적 접근

 

 

직접 접근이라고도 하는 랜덤접근은 인덱스로 접근하는 것을 의미한다.

 

2.2.2. 배열과 연결 리스트 비교

배열은 인덱스 번호만 알아도 해당 값을 얻어 낼 수 있는 있는 반면, 연결 리스트는 순차 접근이 불가능하여 찾고자하는 해당 위치까지 탐색을 해야한다.

 

즉, 배열은 참조나 탐색하기엔 연결리스트 보단 빠르다. 다만 삽입, 삭제에서는 연결리스트에서는 next, prev 선만 변경하면 가능하므로 이부분은 연결리스트를 선택하는 것이 좋다.

2.3.  벡터

벡터는 동적으로 요소를 할당할 수 있는 동적 배열이다. 만약, 컴파일 시점에 할당해야할 개수를 모르면 벡터를 사용한다. 

 

 

사진과 같이 뒤에서 삽입 하면 필요한 만큼 증가하는게 아니라 2**k 승 만큼 증가하게 된다. 

 

2.4.  스택

스택

스택은 LIFO (Last In First Out)의 성질을 띈다. 재귀 함수, 웹브라우저의 방문 기록등에 사용된다.

• 특징: LIFO(Last In First Out) 구조.
• 활용: 함수 호출 스택, 괄호 검사 등.

2.5.  큐

큐는 먼저 집어 넣은 데이터가 먼저 나오는 성질인 FIFO 인 자료구조이다.

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, BFS, 캐시 등에서 사용된다.

즉, 무언가를 기다릴 때 순차적으로 처리하는 과정에서 사용된다. 

 

 

• 특징: FIFO(First In First Out) 구조.
• 활용: 작업 스케줄링, 대기열 처리 등

 

3. 비선형 자료 구조

비선형 자료 구조란 일렬로 나열되어 있지 않고, 계층적, 비연속적인 구조로 배치 되는 자료구조를 의미한다. 

종류로는 그래프, 트리, 힙, 우선순위 큐, 맵, 셋, 해쉬 테이블이 있다.

 

3.0 비선형 자료구조의 특징

1. 계층적 또는 네트워크 형태
   • 데이터가 계층적으로 배치되거나, 복잡한 연결 관계를 가짐.
   • 예: 트리는 계층 구조, 그래프는 네트워크 구조.
2. 효율적인 데이터 표현
   • 데이터 관계를 구조적으로 표현할 수 있음.
   • 예: 조직도, 도로망, 소셜 네트워크 등의 복잡한 관계 표현 가능.
3. 동적 크기와 유연성
   • 데이터를 동적으로 추가하거나 삭제하기 쉬움.
4. 복잡한 데이터 접근
   • 데이터를 순회하거나 접근하는 방식이 배열보다 복잡하며, 다양한 알고리즘이 필요.

 

3.1. 그래프

• 특징:
  • 노드(Vertex)와 간선(Edge)으로 구성된 네트워크 구조.
  • 간선으로 노드 간의 관계를 표현.
  • 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨.
• 종류:
  • 가중치 그래프 (Weighted Graph): 간선에 가중치가 있음.
  • 방향 그래프 (Directed Graph): 간선에 방향이 있음.
  • 비방향 그래프 (Undirected Graph): 간선에 방향이 없음.
  • 순환 그래프 (Cyclic Graph): 순환 경로가 존재.
  • 비순환 그래프 (Acyclic Graph): 순환 경로가 없음.
• 활용:
  • 도로망, 소셜 네트워크, 네트워크 라우팅, 최단 경로 탐색(다익스트라 알고리즘 등).

 

3.2. 트리

트리는 그래프 중 하나로 그래의 특징처럼 정점과 간선으로 이루어져있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 루트노드, 내부 노드, 리프 노드 등으로 구성된다. 

 

• 특징:
  • 계층적 구조로, 루트 노드(Root)에서 시작하여 하위 노드(Child)로 확장.
  • 각 노드는 부모(Parent)와 자식(Child) 간의 관계를 가짐.
  • 노드 간의 고유한 경로가 존재하며, 반드시 한쪽 노드에서 다른 노드까지 갈 수 있다.
• 종류:
  • 이진 트리 (Binary Tree): 각 노드가 최대 2개의 자식을 가짐.
  • 이진 탐색 트리 (Binary Search Tree): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값.
  • 힙 (Heap): 완전 이진 트리로, 최소/최대 우선순위를 유지.
  • AVL 트리, 레드-블랙 트리: 균형 트리 구조.
• 활용:
  • 데이터 탐색, 정렬, 트리 기반 데이터 저장소(예: 파일 시스템, 데이터베이스).

 

3.2.1. 트리의 높이와 레벨

깊이: 루트 노드부터 해당 노드까지 최단 거리로 갔을 때의 거리. 4번 노드의 레벨은 2이다. (1부터 시작)

높이: 루트 노드부터 리프 노드깢의 거리 중 가장 긴 거리. 위의 높이는 3이다.  (1부터 시작)

레벨: 깊이와 같은 의미이지만 보통 0부터 시작한다.

서브트리: 트리내의 하위 집합

 

3.2.2. 이진 트리

이진 트리는 자식 노드의 개수가 최대 2개로만 이루어진 트리구조. 

 

이진 트리의 종류

• 정이진 트리(full binary tree): 자식 노드가 0 또는 두 개인 이진 트리
• 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진트리. 마지막 레벨의 경우 왼쪽부터 채워져 있다
• 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리
• 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리(balanced binary tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진트리 map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나이다.

이진 탐색 트리(BST)

BST는 오른쪽 하위 트리에는 '노드 값보다 큰값'이 있는 노드만 존재하고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어있는 트리이다.

왼쪽 및 오른쪽 하위 트리 해당 특성을 가지며, 이로 인해 검색이 용이하다.

 

왼쪽에는 작은 값으로, 오른쪽에는 큰 값이 정해져 있기 때문에 10을 찾으려고 한다면 25의 왼쪽 노드들만 찾으면 된다.

 

 

보통 탐색시에는 O(logn)이지만 최악의 경우 O(n)이 걸린다. 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 때문이다.

 

 

AVL 트리

AVL 트리(Adelson-Velsky and Landis tree)는 선형적 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 난다.

 

탐색, 삽입, 삭제: O(logn)

BST와 달리 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 

수행한다. 

 

 

레드 블랙 트리

균형 이진 탐색 트리라고도 한다. 

탐색, 삽입, 삭제: O(logn)

각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장
삽입 및 삭제 중 트리가 균형을 유지하도록 사용됨

"모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다"등의 규칙을 기반으로 균형을 잡는 트리

 

3.3. 힙

힙은 완전 이진 트리 기반의 자료 구조이다. 최소힙과 최대힙 두가지가 있다.

 

특징:

1. 완전 이진 트리:
   • 마지막 레벨을 제외한 모든 레벨이 가득 차 있으며, 마지막 레벨은 왼쪽부터 채워짐.
2. 부모-자식 관계:
   • 최대힙(Max-Heap): 부모 노드 ≥ 자식 노드. (루트에 가장 큰 값)
   • 최소힙(Min-Heap): 부모 노드 ≤ 자식 노드. (루트에 가장 작은 값)

시간 복잡도:

• 삽입, 삭제: O(log n) (트리 높이에 비례)
• 루트 값 접근: O(1)

3.3.1. 최대힙의 삽입

 

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

 

3.3.2. 최대힙의 삭제

최댓값은 루트 노드이므로 루트 노드가 삭제되고 마지막 노드와 루트 노드를 스왑하며 재구성함.

 

3.4. 우선순위 큐

우선순위 큐는 큐의 특수한 형태로, 각 요소가 우선순위를 가지고 있으며, 높은 우선순위를 가진 요소가 먼저 처리됩니다.
일반적인 큐(FIFO)와는 달리, 우선순위에 따라 데이터가 처리된다. 

 

특징:

1. 요소는 우선순위에 따라 자동 정렬됨.
2. 삽입, 삭제 시 우선순위 비교를 통해 정렬 상태 유지.

구현 방식:

• 배열/리스트:
  • 단순 구현 가능하나, 삽입/삭제 시 정렬에 시간이 소요됨.
• 힙(Heap):
  • 효율적인 구현 방식으로, 최소힙 또는 최대힙을 사용해 O(log n) 시간 복잡도로 정렬 상태 유지.

활용:

• 작업 스케줄링, 다익스트라 알고리즘, 허프만 코딩 등.

 

3.5. 맵(Map)

맵(Map)은 키-값(key-value) 쌍으로 데이터를 저장하고, 키를 이용해 값을 빠르게 검색할 수 있는 자료 구조이다.

특징:

1. 고유한 키:
   • 각 키는 유일하며, 중복이 허용되지 않음.
2. 빠른 검색, 삽입, 삭제:
   • 일반적으로 O(1) 시간 복잡도(해시 테이블 기반).
3. 키와 값:
   • 키는 데이터를 식별하고, 값은 키에 매핑된 데이터.

구현 방식:

• 해시 테이블(Hash Table): 대부분의 언어에서 기본 구현으로 사용.
• 트리(Map Tree): 키를 정렬된 상태로 저장(예: 레드-블랙 트리).

활용:

• 데이터베이스 인덱싱, 캐시, 설정 값 저장.

3.6. 셋(set)

**셋(Set)**은 중복되지 않는 고유한 데이터를 저장하는 자료 구조입니다.

특징:

1. 중복 허용 X:
   • 동일한 요소가 두 번 저장되지 않음.
2. 빠른 검색, 삽입, 삭제:
   • 일반적으로 O(1) (해시 테이블 기반) 또는 O(log n) (트리 기반).
3. 정렬 여부:
   • 정렬되지 않은 셋: 삽입 순서와 관계없이 저장.
   • 정렬된 셋: 저장된 데이터가 정렬된 상태로 유지.

구현 방식:

• HashSet: 해시 테이블 기반.
• TreeSet: 이진 탐색 트리 기반.

활용:

• 중복 제거, 집합 연산(합집합, 교집합, 차집합) 구현.

 

3.7. 해쉬 테이블

해시 테이블(Hash Table)은 키-값 쌍을 저장하며, 데이터를 빠르게 검색, 삽입, 삭제할 수 있는 자료 구조이다.
키를 해시 함수(hash function)를 통해 해시 값으로 변환하고, 이를 기반으로 데이터를 저장.

무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한다.

특징:

1. 빠른 데이터 접근:
   • 평균 O(1) 시간 복잡도로 검색 가능.
2. 충돌 처리:
   • 두 키가 같은 해시 값을 가지는 경우를 처리해야 함.
   • 방법:
     • 체이닝(Chaining): 같은 해시 값에 여러 값을 연결 리스트로 저장.
     • 오픈 어드레싱(Open Addressing): 빈 슬롯을 찾아 데이터를 저장.
3. 키의 고유성:
   • 각 키는 고유하며, 중복되지 않음.

활용:

• 데이터베이스 인덱싱, 캐시, 집합(Set), 맵(Map) 구현의 기반.

장점:

• 검색, 삽입, 삭제 속도가 빠름.
• 대규모 데이터 처리에 적합.

단점:

• 해시 함수의 품질에 따라 성능이 달라짐.
• 충돌이 많으면 성능 저하.

 

3.8. 요약

• 힙: 완전 이진 트리 기반 자료구조로, 최대/최소 값을 빠르게 처리.
• 우선순위 큐: 데이터의 우선순위에 따라 처리 순서를 결정.
• 맵: 키-값 쌍으로 데이터 저장, 검색 속도 빠름.
• 셋: 중복 없이 데이터 저장, 집합 연산 가능.
• 해시 테이블: 해시 함수를 사용해 키-값 쌍을 저장, 빠른 접근 속도.