스파르타 인강 - 자료 구조, 알고리즘 4주차

병아리의최후·2022년 11월 28일

스파르타 인강

목록 보기

9/11

01. 트리 - 1

트리란?

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조.

큐(Queue), 스택(stack)은 선형구조라고 하는데 트리는 비선형 구조이다.

비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다.

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,

비선형구조는 표현에 초점이 맞춰져 있다.

트리에서 나오는 용어들

Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level

트리의 종류

다양한 종류가 있지만 이번에는 이진 트리와 완전 이진 트리만 소개하겠다.

이진 트리(Binary Tree)의 특징은 바로
각 노드가 최대 두 개의 자식을 가진다는 것

      o      Level 0 
    o o o    Level 1
   o  o  o   Level 2 # 이진 트리(X)

      o      Level 0 
    o   o    Level 1
   o o o     Level 2 # 이진 트리(O)

완전 이진 트리(Complete Binary Tree)의 특징은 바로
노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것!

      o      Level 0
    o   o    Level 1
     o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

      o      Level 0
    o   o    Level 1
   o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

02. 트리 - 2

완전 이진 트리를 배열로 표현

트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않는다.
그래서 None 값을 배열에 넣고 시작 [None]

      8      Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
    6   3    Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
   4 2 5     Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 된다.

현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
현재 인덱스 // 2 -> 부모의 인덱스

완전 이진 트리의 높이

트리의 높이(Height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이

      o      Level 0  # 루트 노드
    o   o    Level 1
   o o o     Level 2  # 가장 아래 리프 노드

이 트리의 높이는 ? 2 - 0 = 2!

레벨을 k라 한다면 2^k개는 각 레벨이 최대로 들어갈 수 있는 노드의 개수

Q. 만약 높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면 모든 노드의 개수는 몇개?

1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h

즉, 이를 수식으로 표현하면 2^(h+1) - 1

(그냥 Tip. 이진 트리의 높이는 최대로 해봤자 O(log(N)) )

03. 힙

힙이란?

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조

최댓값이 맨 위인 힙을 Max 힙,
최솟값이 맨 위인 힙을 Min 힙

맥스 힙에 원소 추가

원소를 맨 마지막에 넣는다.
그리고 부모 노드와 비교. 만약 더 크다면 자리를 바꿔주자.
부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복

Q. 맥스 힙은 원소를 추가한 다음에도 맥스 힙의 규칙을 유지해야 한다.
맥스 힙에 원소를 추가하시오.

우선 전체 배열에 값을 추가하신 다음에
그 원소의 인덱스인 len(self.items) - 1 부터 시작. (맨 마지막에 넣었으니 맨 뒤)

그 인덱스부터 부모 노드의 인덱스의 노드와 값을 비교.
만약 더 크다면 값을 교체하고 cur_index 에 parent_index 를 넣는다.

이 과정을 cur_index 가 제일 꼭대기 칸, 1이 되기 전까지 반복

시간 복잡도 : 맥스 힙의 원소 추가는 $O(log(N))$ 만큼의 시간 복잡도를 가진다

맥스 힙의 원소 제거

최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것

delete함수의 시간 복잡도는 O(log(N))

04. 그래프

그래프란?

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조. [천재학습백과]

그래프에서 사용되는 용어 정리

노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

예시를 들어보자.

            로제 - 사나
             ⎜       
      제니 - 르탄

르탄이는 연결 관계를 가진 데이터, 노드
르탄과 제니는 간선으로 연결
르탄과 로제는 인접 노드

그래프에는 유방향 그래프와 무방향 그래프 두가지가 있는데, 이번에는 무방향 그래프에서만 배워보자.

유방향 그래프(Directed Graph): 방향이 있는 간선을 갖습니다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행.
무방향 그래프(Undirected Graph)는 방향이 없는 간선을 갖는다.

그래프의 표현 방법

1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

ex) 제니를 0, 르탄을 1, 로제를 2, 사나를 3이라고 해보자.

          2 - 3
          ⎜       
      0 - 1

1. 이를 인접 행렬, 2차원 배열로 표현
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

이걸 배열로 표현
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

2. 이번에는 인접 리스트로 표현
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현해보자
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

이 두방식의 차이는 시간 vs 공간

인접 행렬은 O(노드^2)만큼의 공간 사용

인접 리스트는 최대 O(간선)만큼의 시간을 사용. O(노드 + 간선) 만큼의 공간을 사용