[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day3) : 자료구조(트리, 힙, 세그먼트 트리, 인덱스 트리)

자료구조 (Data Structure)

• 자료구조란 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법.
• 저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분된다.
  • 선형 자료구조 : 데이터가 일렬로 나열되어 있음
    • 배열, 연결 리스트, 스택, 큐
  • 비선형 자료구조 : 데이터가 특정한 형태를 띄고 있음
    • 트리, 그래프

 

1. 배열 (Array)

• 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조
• 배열의 특징
  • 데이터 접근이 용이하다. (O(1)의 시간복잡도를 가짐)
  • 데이터 삽입/삭제가 어렵다. (O(N)의 시간복잡도를 가짐)
    • 중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동해야 한다.
  • 구조가 간단하여 프로그램 작성이 쉽다.

1) 배열 []

int[] arr = new int[5];
arr[0] = 1;
arr[1] = 2;

 

2) ArrayList

• 배열의 단점을 보완하면서도 배열의 장점을 유지하는 데이터 구조.
• 내부적으로 배열을 사용하지만, 크기를 동적으로 조절할 수 있다.
• 생성 시, 기본으로 n개의 배열을 생성하며, 요소가 추가됨에 따라 내부 배열의 크기가 현재 사이즈의 2배가 되는 배열을 생성한다. 그래서 생성 시, 사이즈를 알고 있다면 사이즈대로 생성하는 것이 좋다.

// ArrayList 생성
ArrayList<Integer> list = new ArrayList<>();

// 요소 추가
list.add(1);
list.add(2);

// 요소 접근
System.out.println(list.get(0)); // 출력: 1

// 요소 삭제
list.remove(1); // 1번 인덱스 요소 삭제

// 요소 크기 확인
System.out.println(list.size()); // 출력: 2

// 요소 포함 여부 확인
System.out.println(list.contains(3)); // 출력: true

// 전체 요소 출력
for (int i : list) {
    System.out.println(i);
}

 

 

2. 연결 리스트 (Linked List)

• 각 노드가 데이터와 포인터를 가지고 일렬로 연결되어있는 방식으로 데이터를 저장하는 자료구조
• 연결리스트의 특징
  • 배열과 반대되는 특징을 가진다.
  • 데이터의 접근이 느리다. (O(N)의 시간복잡도를 가진다. 다만 맨 앞과 맨 뒤는 O(1)이 소요된다.)
  • 데이터 삽입/삭제 연산이 용이한다. (그래서 Queue 생성시 Linked List를 사용한다.)
  • 포인터를 위한 추가 공간이 필요하깅 프로그램 작성이 어렵다.

LinkedList list = new LinkedList();
list.add(1);
list.add(2);
list.printList(); // 1 2

 

 

*ArrayList와 LinkedList를 선언할 때, 아래와 선언하는 것이 좋다.

List<Integer> arryList = new ArrayList();
List<Integer> linkedList = new LinkedList();

 

이렇게 선언하면 추후 ArrayList를 LinkedList로, LinkedList를 ArrayList로 바꿀 수 있다.

다만, 이렇게 포괄적으로 선언을 하면 해당 리스트의 특화 메서드는 사용할 수 없다.

 

3. 스택 (Stack)

• 삽입, 삭제가 한 방향에서 이루어지는 선형 자료구조.
• LIFO(Last In First Out) 원칙을 따르는 데이터 구조.
• 스택에 데이터가 삽입될 위치를 Top이라고 한다.

 

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2
System.out.println(stack.peek()); // 1, top을 출력

 

 

4. 큐 (Queue)

• 한 방향에서는 삽입, 반대편에서는 삭제가 이루어지느 ㄴ자료구조
• FIFO(First In First Out) 원칙을 따르는 데이터 구조
• 데이터가 삭제될 위치를 Front / Head, 마지막 데이터가 삽입된 위치를 Rear / Tail 이라 부른다.
• 양 방향에서 삽입과 삭제가 모두 이루어지는 큐를 덱(Deque)라고 한다.

 

 Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
System.out.println(queue.remove()); // 1
System.out.println(queue.peek()); // 2

 

---

트리

• 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식 관계로 표현된다.
• 트리는 1개 이상의 노드를 갖는 집합으로 다음의 조건을 만족한다.
  • 루트(root) 노드가 존재한다.
  • 트리의 부분트리(sub tree) 또한 트리 구조를 따른다. (사이클이 없는 구조)

 

트리의 용어

1. 루트 노드 (Root Node)

• 트리의 최상위 노드, 유일하다.

 

2. 깊이 (Depth)

• 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수 (ㄱㄱ으로 기억하기)
• 루트 노드는 자기 자신까지 도달하는 간선의 개수가 0이므로 루트 노드의 깊이는 0이다.
• E의 깊이 : 2

3. 높이 (Height)

• 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수 (ㄴㄴ라고 기억하기)
• 노드 중 가장 높이가 높은 노드의 높이를 트리의 높이라고 한다.
• E의 높이 : 3

 

4. 레벨

• 노드의 깊이 + 1

 

5. 부모 노드 (Parent Node)

• 부모 자식 관계에서 상위 계층에 있는 노드
• 상위 계층에 있을수록 노드의 깊이와 레벨이 낮다.

 

6. 자식 노드 (Child Node)

• 부모 자식 관계에서 하위 계층에 있는 노드

 

7. 형제 노드 

• 부모가 동일한 노드

 

8. 조상 노드

• 해당 노드의 부모 노드로부터 루트 노드까지 가는 경로에 존재하는 노드들을 그 노드의 조상 노드라고 한다.
• 자신 노드의 윗 노드

 

9. 후손 노드

• 해당 노드를 루트로 하는 서브트리에 있는 모든 노드를 그 노드의 후손 노드라고 한다.
• 자신 노드의 아래 노드

 

10. 노드의 차수 (노드의 분지수, Degree)

• 노드의 자식 수
• A의 차수 : 3

 

11. 트리의 차수 (트리의 분지수)

• 해당 트리 내 모든 노드의 분지 수 중 최댓값
• 위 트리의 분지 수 : 3

 

12. 내부 노드 (internal node)

• 자식이 있는 노드

 

13. 단말 노드 (외부 노드, 잎새 노드, leaf/external/terminal node)

• 자식이 없는 노드

 

이진 트리(Binary Tree)

• 트리의 분지 수가 2이하인 트리
• 대부분의 트리 자료구조는 이진 트리 형태에서 나온다.
• 이진 트리의 특징
  • 자식이 최대 2개이기 때문에 자식을 왼쪽 자식과 오른쪽 자신으로 구분한다.
  • 높이가 N인 이진 트리의 최대 노드 개수는 2^n - 1 개이다.

 

이진 트리의 종류

이진 트리의 종류

• 정 이진 트리 (Full Binary Tree)
  • 모든 노드의 차수가 0 또는 2인 이진 트리

• 포화 이진 트리 (Perfect Binary Tree)
  • 정 이진 트리에서 모든 단말 노드의 깊이가 같은 이진 트리
  • 높이가 H인 포화 이진 트리의 노드 개수는 2^H - 1 개이다. (H = 3, 노드 개수 = 7개)
  • 반대로 노드가 N개인 포화 이진 트리의 높이는 log(N + 1)
  • 깊이가 D인 포화 이진 트리의 단말 노드 개수는 2^D개이다. (D = 2, 단말 노드 개수 = 4개)

• 완전 이진 트리 (Complete Binary Tree)
  • 마지막 레벨은 노드가 왼쪽에 몰려있고 마지막 레벨을 제외하면 포화 이진 트리 구조를 띄고 있는 이진 트리.

• 사향 이진 트리 (Skewed Binary Tree)
  • 연결 리스트 처럼 한 줄로 연결되어 있는 형태의 이진 트리

 

이진 트리의 표현

일차원 배열을 이용한 구현

• 배열에 트리 노드를 레벨 순서대로 왼쪽에서 오른쪽으로 저장한다. 완전 이진 트리로 가정하고 배열의 1번 위치부터 저장을 시작한다고 가정했을 때, i번 노드의 부모, 왼쪽 자식, 오른쪽 자식을 구하는 방법은 다음과 같다.
• parent = i / 2
• left child = i * 2
• right child = i * 2 + 1

 

 

이진 트리의 순회

• 트리는 비 선형 자료구조이기 때문에 모든 노드를 for문 한번으로 방문이 불가능하다. 이런 트리 구조에서 모든 노드를 방문하기 위한 과정을 트리의 순회라고 한다.
• 특히 이진 트리의 순회는 왼쪽 자식 탐색, 오른쪽 자식 탐색, 현재 노드 방문의 세가지 주요 과정을 통해 진행되며, 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나뉜다. (현재 노드가 어디서 방문하느냐에 따라 전,중,후위가 나뉜다)
• 모든 순회는 루트노드에서 시작한다.

순회 순서

• 전위 순회 (pre-order)
  
  1. 현재 노드 방문
  2. 왼쪽 자식 탐색
  3. 오른쪽 자식 탐색

• 중위 순회 (in-order)
  1. 왼쪽 자식 탐색
  2. 현재 노드 방문
  3. 오른쪽 자식 탐색
• 후위 순회 (post-order)
  1. 왼쪽 자식 탐색
  2. 오른쪽 자식 탐색
  3. 현재 노드 방문

 

힙 (Heap)

• 완전 이진 트리리 형태의 자료구조
• 힙 조건을 만족한다. (조건 예시 : 각 노드의 키 값은 자식 노드의 키 값보다 더 크다.)
• 일차원 배열로 구현한다.
• 일반적으로 그룹을 정렬(Heap Sort)하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다.
• 데이터의 삽입과 삭제가 빠르며 각각의 수행시간이 O(logN)이다.

 

최소 힙과 최대 힙

• 최소 힙과 최대 힙은 각각 다음 힙 조건을 가지는 대표적인 유형의 힙이다.
• 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
• 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.
• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 큰 관계가 유지되므로 트리 내에서 가장 작은(큰) 키 값을 가진 노드는 항상 루트 노드가 된다. 

Max Heap 예시

 

힙의 구현

- 삽입 연산

1. 트리의 가장 마지막 위치에 노드를 삽입한다.
2. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.
3. 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.
4. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2 ~ 3을 반복한다.

• 완전 이진 트리의 리프 노드부터 루트 노드까지 연산을 한다. 노드가 N개일 때 수행시간은 O(logN)이다.

- 삭제 연산

1. 힙의 삭제 연산은 항상 루트 노드를 삭제한다.
2. 트리의 가장 마지막 노드를 루트 자리로 삽입한다.
3. 바꾼 위치의 노드가 힙 조건을 만족하는지 확인한다.
4. 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.
5. 조건을 만족하거나 리프 노드에 도달할 때까지 3 ~ 4를 반복한다.

• 완전 이진 트리의 루트 노드부터 리프 노드까지 연산을 한다. 노드가 N개일 때 수행시간은 O(logN)이다.

 

Heap 예제 문제

백준 1927번 : 최소 힙

https://www.acmicpc.net/problem/1927

 

힙의 삽입, 삭제 연산을 직접 구현해보면서 과정을 이해한다.

 

자세한 풀이는 아래 링크를 참고해주세요.

[코테] 백준 1927번 : 최소 힙 (java)

 

 

---

인덱스 트리(= 세그먼트 트리)

• 포화 이진트리 형태의 자료구조
• 각 노드가 다음과 같은 의미를 가진다.
  • 리프 노드 : 배열에 적혀있는 수
  • 내부 노드 : 왼쪽 자식과 오른쪽 자식의 합
• 리프 노드의 개수가 N개 이상인 포화 이진 트리는 높이가 최소 logN이다.
• 리프 노트의 개수가 N개보다 많아 비어있는 공간이 발생할 경우, 구조에 지장이 가지 않도록 초기값을 설정한다.(구간합일 때는 0, 구간곱일때는 1 과 같이 영향이 가지 않는 값으로 설정한다.)
• 구간의 합, 최솟값, 최댓값 등과 같은 구간 쿼리를 효율적으로 처리하기 위해 사용되는 트리 자료 구조이다.

 

인덱스 트리 생성 -  init

인덱스 트리의 리프 노드에 배열을 담아야 하므로 리프 노드가 시작하는 인덱스 번호를 알아야한다.

리프 노드의 개수를 S로 표현하고 S는 N 이상의 2^n으로 표현 가능한 수여야 한다.

따라서 S 는 아래와 같이 구한다. (N은 주어진 배열의 크기)

S = 1;
while (S < N) {
    S *= 2;
}

 

리프 노드에 배열에 적혀있는 수를 넣기위해 S번째부터 넣는다.

그 외 내부 노드는 S - 1번째부터 자식 노드(왼쪽, 오른쪽) 합을 대입한다.

private static void init() {
    // leaf노드 채우기
    for (int i = 0; i < N; i++) {
        tree[S + i] = nums[i];
    }

    // 내부노드 채우기
    for (int i = S - 1; i > 0; i--) {
        tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
}

배열로 나타낸 인덱스 트리

 

 

인덱스 트리 query 수행

• 예를 들어 3 ~ 7 구간의 합을 구하는 쿼리를 날린다고 가정한다.

1. 루트 노드에서 시작해서 트리를 전위 순회하는 방식으로 탐색한다.
2. 현재 노드가 구하고자하는 구간에 완전히 속해있으면 그 노드의 결과값을 반환한다.
3. 왼쪽 자식에서 반환된 값과 오른쪽 자식에서 반환된 값을 더해서 반환한다.

• 색칠된 노드를 찾기 위해 루트 노드에서 리프 노드까지 탐색하므로 수행 시간은 O(logN)이다.
• queryLeft와 queryRight는 카운팅 쿼리가 아니면 변하지않고 그대로 넘긴다.

인덱스 트리 query

 

구간 판별은 아래와 같이 그림으로 기억하면 좋다.

query 구간 판별

 

 

인덱스 트리 update 수행

1. 해당 노드 위치의 값을 수정한다.
2. 부모를 따라 올라가면서 결과값을 수정한다.
3. 3번 위치의 데이터가 3으로 바뀐다면 다음 색칠한 노드들이 수정된다.

update 시 주의할 점은 update 값을 그대로 넘기는 것이 아니라, target의 value와 차이나는 값을 넘긴다.

예를 들어, target인 3번 노드의 값을 2로 바꾼다고 했을 때 현재 value가 4이므로 target과 차이나는 값만큼 부모 노드에게 더해줘야한다.

 

인덱스 트리 update

update 구간 판별

 

 

예제 문제

백준 2042번 : 구간 합 구하기

https://www.acmicpc.net/problem/1927

 

인덱스 트리(= 세그먼트 트리)로 풀어볼 수 있는 기본적인 문제이다.

문제 레벨은 골드이지만, 인덱스 트리 개념을 알면 쉬운 문제이다.

 

자세한 풀이는 아래 링크를 참고해주세요.

[코테] 백준 2042번 : 구간 합 구하기 (java)

 

 

백준 2243번 : 사탕상자

https://www.acmicpc.net/problem/2243

세그먼트 트리에서 query를 조건에 맞춰 다르게 날리는 문제이다.

 

자세한 풀이는 아래 링크를 참고해주세요.

[코테] 백준 2243번 : 사탕상자 (java)