4.1~4.3 복잡도, 선형 자료구조, 비선형 자료구조

CS공부/자료구조

4.1~4.3 복잡도, 선형 자료구조, 비선형 자료구조

Jaemin0604 2025. 1. 20. 14:48

4.1.1 복잡도와 빅오 표기법

알고리즘을 수행하면 시간과 메모리 공간 등의 자원이 사용됨 -> 자원을 낭비하지 않으려면 효율적인 알고리즘 필요
효율적인 알고리즘을 정량화 하기 위한 개념 -> 시간 복잡도/공간 복잡도
시간 복잡도 - 알고리즘의 실행 시간을 정량화하는 것
공간 복잡도 - 실행하는 데 필요한 메모리 사용량을 정량화하는 것
알고리즘의 복잡도는 주로 빅오 표기법(big-O notation)으로 나타냄
빅오 표기법 - 입력 값(n)에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도

점근적 표기법 - 알고리즘의 복잡도를 나타낼 때 계수, 상수항 등 중요하지 않은 항목을 무시하고 표현하는 것
- 최악의 경우: 빅오 표기법
- 평균의 경우: 빅세타 표기법
- 최선의 경우: 빅오메가 표기법

4.2.1 배열(Array)

배열 - 정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조
각 데이터를 배열의 요소
데이터를 가리키는 번호를 인덱스
- 접근 - 배열에서 특정 인덱스의 데이터에 접근하는데 걸리는 시간 복잡도 O(1)
- 검색 - 배열에서 데이터를 검색하는데 걸리는 시간 복잡도 O(n)
- 삽입 - 배열에서 특정 위치에 새로운 데이터를 삽입하는데 걸리는 시간 복잡도 O(n)
- 삭제 - 배열에서 특정 인덱스의 데이터를 삭제하는데 걸리는 시간 복잡도 O(n)

4.2.2 연결 리스트(Linked list)

연결 리스트 - 크기가 정해져 있지 않은 동적 자료구조
여러 개의 노드로 구성
헤드 포인터와 테일 포인터로 시작과 끝을 알 수 있음
첫 번째 노드는 헤드 포인터가 가리키고, 마지막 노드는 가리킬 다음 노드가 없음
마지막 노드가 가리키는 주소 값은 NULL, 마지막 노드는 테일 포인터가 가리킴
- 검색 - 연결 리스트에서 특정 데이터를 검색하는데 드는 시간은 시간 복잡도 O(n)
- 추가 - 연결 리스트에서 데이터를 추가하는 연산은 O(1) -> 가리키는 노드의 주소 값만 변경
- 삭제 - 연결 리스트에서 첫 번째 데이터를 삭제하는 경우 O(1)/ 나머지 데이터를 삭제하는 경우 최대O(n)

4.2.3 스택(Stack)

스택 - 데이터를 쌓는 형태
마지막에 들어온 데이터가 먼저 나가는 LIFO(Last In First Out) 형태의 자료구조
데이터를 삽입하는 연산 - push
데이터를 삭제하는 연산 - pop
push, pop의 시간 복잡도 - O(1)
스택을 구현할 때 배열과 연결 리스트를 이용

4.2.4 큐(Queue)

큐 - 데이터가 순차적으로 들어오는 형태
먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형태의 자료구조
큐의 맨 앞을 front
큐의 맨 뒤를 rear
큐에 데이터를 추가하면 큐의 맨 뒤에 데이터가 삽입됨 - 인큐(enqueue)
큐에서 데이터를 삭제하면 큐의 맨 앞에서 삭제됨 - 디큐(dequeue)
배열과 연결 리스트를 이용해 구현

4.3.1 그래프(Graph)

그래프 - 데이터를 포함하는 정점과 정점을 잇는 간선으로 구성된 자료구조
정점은 일반적으로 노드라고 부름
G = (V, E)
- 인접 - 두 정점이 간선으로 연결되어 있으면 인접하다고 함
- 차수 - 정점에 연결된 간선의 수
- 진입 차수 - 해당 정점으로 향하는 간선의 수
- 진출 차수 - 해당 정점에서 나가는 간선의 수
- 경로 - 한 정점에서 다른 정점으로 이어지는 정점들의 리스트
- 경로 길이 - 경로를 구성하는 간선의 수
- 단순 경로 - 모두 다른 정점으로 구성된 경로를 의미
- 사이클 - 한 정점에서 시작해 같은 정점으로 돌아올 수 있는 경로를 의미
종류
- 무방향 그래프(undirected graph) - 간선에 방향이 없는 그래프
  - 정점의 개수가 n개일 때 최대 간선의 개수는 n*(n-1)/2
- 방향 그래프(directed graph) - 간선에 방향성이 있는 그래프
  - 두 정점이 연결되어 있을 때 A에서 B로 향하는 간선을 <A,B>로 표기
  - 따라서 <A,B>와 <B,A>는 다른 간선을 의미
  - 정점의 개수가 n개일 때 최대 간선의 개수는 n*(n-1)

경로 탐색
- 너비 우선 탐색(BFS, Breadth-First Search) - 탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식
  - 먼저 발견한 정점과 인접한 정점들을 탐색하면서 큐에 삽입
  - 탐색한 정점을 큐에 넣기 전 이전에 방문했는지 확인 필수
- 깊이 우선 탐색(DFS, Depth-First Search) - 시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색
  - 최대 깊이인 정점에 도달했다면 방문한 정점들을 역순으로 재방문하면서 탐색 가능한 정점이 있는지 확인
  - 탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이 정점까지 탐색을 진행
  - 재귀 호출 또는 스택으로 구현

4.3.2 트리(Tree)

트리 - 그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현
- 루트 노드 - 부모 노드가 없는 노드, 트리에는 하나의 루트 노드가 존재
- 부모 노드 - 루트 노드 방향으로 연결된 노드
- 자식 노드 - 루트 노드의 반대 방향으로 연결된 노드
- 단말 노드 - 자식 노드가 없는 노드
- 형제 노드 - 부모 노드가 같은 노드
- 레벨 - 루트 노드로부터 노드의 상대적 위치를 의미
- 높이 - 트리의 최대 레벨 +1
- 차수 - 자식 노드의 개수
이진 트리(binary tree) - 자식 노드가 최대 2개인 트리
- 완전 이진 트리(complete binary tree)
  - 트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며, 마지막 레벨은 왼쪽부터 채워져있는 트리
- 포화 이진 트리(perfect binary tree)
  - 트리의 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리
- 이진 탐색 트리(BST, Binary Search Tree)
  - 한 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성
  - 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성
  - 균형 잡힌 이진 탐색 트리에서는 값을 검색하는 데 O(log n)이 소요됨

4.3.3 우선순위 큐(Priority queue)

우선순위 큐 - 우선순위가 높은 데이터가 먼저 나오는 자료구조
데이터 삭제 연산을 수행하면 우선순위가 가장 높은 데이터를 얻을 수 있음
배열, 연결 리스트, 완전 이진 트리로 구현할 수 있음

4.3.4 힙(Heap)

힙 - 완전 이진 트리
최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조
최대 힙 - 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진트리

최소 힙 - 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진트리

4.3.5 해시 테이블(Hash table)

해시 테이블 - 하나의 키에 대해 하나의 값을 저장하는 형태의 자료구조
키는 해시 함수를 사용해 해시를 얻을 수 있음
해시는 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값
연산은 평균적으로 O(1)의 시간 복잡도를 가짐

해시 충돌 - 서로 다른 키에 대해 같은 해시가 도출되는 것
- 체이닝 - 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식
  - 연결 리스트에 노드를 저장하므로 저장 공간에 대한 제약이 적음
  - 하나의 해시에 노드가 물릴 수 있음
- 개방 주소법 - 해시 충돌이 일어났을 때 해당 해시가 아닌 비어있는 공간에 값을 저장하는 방식
  - 선형 조사법 - 충돌이 일어나면 다음 인덱스에 데이터를 저장
    - 특정 인덱스에 데이터가 몰리는 군집화 현상이 나타날 수 있음
  - 이차 조사법 - 충돌이 일어나면 거듭제곱한 인덱스만큼 이동하고 빈 공간을 찾으면 데이터를 저장
    - 어느 정도의 군집화 현상 발생
  - 이중 해싱 - 충돌이 발생하면 다른 해시 함수를 한 번 더 적용하는 방법