programmer.cwchoiit

참고자료:

배열과 같이 여러 데이터(자료)를 구조화해서 다루는 것을 자료 구조라고 한다. 

여러 형태의 자료 구조가 있지만 가장 기본이 되는 배열과 항상 이 자료구조하면 빼놓을 수 없는 Big O 표기법에 대해 다루고자 한다.

자바에서 배열을 선언할 땐 다음과 같이 선언한다.

package org.example.collection.array;

public class ArrayMain1 {

    public static void main(String[] args) {
        int[] arr = new int[5];
        
    }
}

배열의 특징은 크기가 정해져있고, 정해진 크기만큼 연속적으로 메모리에 저장된다.

연속적으로 저장되기 때문에 가져가는 이점이 있다. 바로 배열에서 자료를 찾을 때 인덱스를 사용하면 매우 빠르게 자료를 찾을 수 있다. 구체적으로 단 한번의 계산으로 자료를 찾아낼 수 있다.

근데 어떻게 단 한번의 계산으로 가능한걸까? 항상 O(1)의 시간복잡도를 가진다. 이것만 알지 그 원리를 공부하고 있지 않았던거 같다.

만약, 위 코드처럼 타입이 int고 크기가 5인 배열을 생성하면 메모리에 이렇게 할당된다.

int는 4byte를 차지한다. 그래서 하나의 메모리 공간은 크기가 4byte이다.

그럼 배열의 시작 위치인 x100부터 시작해서 자료의 크기(4byte)와 인덱스 번호를 곱하면 원하는 메모리 위치를 찾을 수가 있는것이다.

arr[0] = x100 + (4byte * 0) = x100
arr[1] = x100 + (4byte * 1) = x104
arr[2] = x100 + (4byte * 2) = x108

이 연산이 배열이 왜 단 한번의 연산으로 조회가 가능한지를 설명한다. 아 그래서 배열은 크기와 타입을 정해주는구나?를 역으로도 생각할 수 있게 된다. 그래서 배열은 굉장히 좋은 자료구조 중 하나이다.

조회뿐 아니라 삽입, 삭제도 단 한번의 연산으로 가능하다. 

• 삽입: arr[3] = 10
• 삭제: arr[3] = 0

딱 원하는 인덱스에 원하는 값을 추가하면 되고, 딱 원하는 인덱스를 찾아 값을 날리면 된다. 그래서 배열에서는 조회, 삽입, 삭제가 O(1)의 시간복잡도를 가진다. O(1)은 데이터가 아무리 많아도 1억개, 10억개, 1조개라도 단 한번의 연산이면 된다는 것을 의미한다.

근데 탐색은 O(n)이다. 왜냐하면 원하는 값을 찾기 위해선 처음부터 마지막까지 하나씩 순회를 해야만 내가 원하는 값을 찾아낼 수 있기 때문이다 배열의 크기가 N이면 연산도 N번만큼 필요하다. 

물론, 저 위 그림을 예시로 배열에서 1을 찾고 싶다고 하면 0번 인덱스가 1이기 때문에 1번의 연산으로 찾는게 가능하지만 만약 30을 찾는다고 하면 0번 인덱스부터 4번 인덱스까지 갈 동안 찾지 못했기 때문에 배열의 크기만큼 연산이 이루어진다. 그리고 만약 마지막 인덱스에 원하는 값이 있어도 N번의 연산을 수행할것이다. 그래서 O(n)이 된다. 

근데 여기서 말하는 O(1)이니 O(n), 이것들이 다 뭘까?

Big O 표기법

알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 처리해야 하는 데이터 양에 따라 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다. 정확한 실행 시간을 계산하는 게 아니고 데이터 양의 증가에 따른 성능의 변화 추세를 말한다.

• O(1) - 상수 시간을 말하고 데이터의 크기에 상관없이 일정하게 단 한번의 연산으로 처리된다.
• O(n) - 선형 시간을 말하고 입력 데이터의 크기에 비례하여 실행시간이 증가한다.
• O(n^2) - 제곱 시간을 말하고 알고리즘의 실행 시간이 입력 데이터의 크기의 제곱에 비례하여 증가한다. 예를 들면 이중 루프를 사용할 때이다.
• O(log n) - 로그 시간을 말하고 알고리즘의 실행 시간이 데이터 크기의 로그에 빌례하여 증가한다.
• O(n log n) - 선형 로그 시간을 말하고 대다수의 효율적인 정렬 알고리즘이 이렇다.

Big O 표기법은 데이터 양 증가에 따른 성능의 변화 추세를 비교하는데 사용한다. 쉽게 이야기해서 정확한 성능을 측정하는 것이 목표가 아니라 매우 큰 데이터가 들어왔을 때의 대략적인 추세를 비교하는 게 목적이다. 따라서 데이터가 매우 많이 들어오면 추세를 보는데 상수는 의미가 없어진다. 이런 이유로 Big O 표기법에서는 상수를 제거한다. 예를 들어 O(2n)이나 O(n+2), O(n/2) 모두 다 O(n)으로 표시한다.

Big O 표기법은 별도의 이야기가 없으면 보통 최악의 상황을 가정해서 표기한다. 최적, 평균, 최악의 경우로 나누어 표기하는 경우도 있다.

위 예시에서 배열을 가지고 얘기를 했는데 조회나 삽입, 삭제는 언제나 O(1)이다. 데이터가 아무리 많아도 단 한번의 수행으로 끝나니까.

탐색의 경우는 O(n)이다. 운이 좋으면 첫번째 인덱스가 원하는 값이 나올수도 있지만 최악의 경우는 가장 마지막 인덱스이거나 아예 없는 경우이기 때문에 N개의 요소를 다 확인한다.

Hash Table은 Key/Value Pair를 빠르게 저장하고 읽을 수 있는 자료구조이다.

파이썬에서 Dictionary라고 부르는 것이 이 Hash Table이다.

예를 들어, Key: Food, Value: Kimchi를 Hash Table에 저장하고자 하면 Hash Table한테 Key가 Food고 Value가 Kimchi인 이 Pair를 저장해 줘! 하고 저장을 한 다음 이후에 Food라는 Key의 Value가 어떻게 돼?라고 물어보면 Hash Table이 Kimchi입니다라고 말해주는 자료구조.

Hash Table의 구현 원리

이름 그대로 Table(배열)과 Hash Function으로 구성되어 있다.

Hash Function은 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다.

쉽게 말하면 어떤 값이던간에 이 Hash Function에 넣으면 고정된 값(예를 들어 숫자)으로 만들어준다는 것을 말한다.

다음 그림을 보자.

어떤 값을 Input으로 만들던간에 Hash Function에 넣으면 위 조건처럼 10보다 작은 숫자 뱉어낸다.

중요한 건, Input이 같은 값이라면 Output도 무조건 같은 값으로 나온다.

그래서 Hash Table의 구성은 다음과 같다.

• Size가 N인 배열(Table)
• Output이 N보다 작은 Hash Function

그래서 그림으로 보면 다음과 같다.

Hash Function, Table이 있는 Hash Table.

그래서 누군가가 Key "Food", Value "Kimchi"라는 Pair를 이 Hash Table에 저장하겠다고 한다.

1. Hash Table은 저 Key를 Hash Function에 집어넣는다. 그리고 나온 Output은 4.

2. 4라는 숫자를 가진 인덱스에 Value를 저장한다.

이게 아주 간단한 Hash Table인데 문제가 있다. 충돌의 문제.

예를 들어, 10개 이상의 값을 이 Hash Table에 넣으면 결국 Hash Function은 0 -10 사이의 숫자만을 뱉어내는 녀석이기 때문에 그 값들 중엔 중복되는 값이 생길 수밖에 없다. 

간단한 예로, 위 그림처럼 인덱스 4에 Kimchi가 저장된 상태인데 누군가가 Key "FavoriteFood" Value "Pizza"라는 Pair를 이 Hash Table에 저장하려고 시도하는데 Hash Function이 같은 4를 뱉어냈다고 생각해 보면 아래 그림처럼 된다.

그럼 아까 Food/Kimchi를 저장했던 사람이 Food에 담긴 Value뭐야? 라고 물어보면 이 Hash Table은 Pizza라는 엉뚱한 값을 뱉을 수 있게 된다. 이걸 어떻게 해결할까?

Hash Table의 Collision 해결 방법

크게 두가지 방법이 있다.

• Chaining
• Probing

Chaining

우선 첫번째 방법인 Chaining은 그냥 배열을 쓰는 게 아니라 Linked List를 사용해서 Collision이 발생할 때마다 해당 인덱스(이 예시에선 4)에 있는 Linked List에 값을 연달아서 저장하는 것. 아래 그림을 보자.

위 문제를 이런식으로 해결했다. 해당 인덱스에 Linked List로 차곡차곡 똑같이 넣는 것. 대신 이제는 Value만 넣을 순 없다. 이 Linked List에 여러 값이 들어가니까 어떤 Key에 해당하는지 알기 위해 Key/Value를 같이 넣어줘야 한다.

그래서 이제 유저가 "Key가 Food인 Value 찾아줘!" 하고 Hash Table에 요청을 하면 Hash Table은 먼저 Hash Function에 Input으로 Food를 넣어서 나온 값 4를 가진 메모리에 가면 나오는 Linked List에서 Iterator를 돌려서 원하는 값(Kimchi)을 찾아내는 것.

참고: Linked List 말고 Binary Search Tree를 사용해도 된다. 이전 포스팅에서 정리한 Binary Search Tree. 이 녀석을 사용하면 원하는 값을 찾아내는 시간 복잡도는 O(log N)이기 때문에 더 효율적일 수도 있다. 상황에 따라.

Probing

Probing도 여러 가지 방법이 있는데 그중 가장 간단한 Linear Probing을 보면 배열을 그대로 쓰고 Hash Function이 같은 값을 뽑아내면 우선 그 자리에 가보는데 값이 있을 때 그 옆을 보는 방식이다. 아래 그림을 보자.

1. Food/Kimchi라는 Pair를 Hash Table에 넣었더니 4번에 들어간 상태이다.

2. Favorite Food/Pizza라는 Pair를 Hash Table에 넣으려고 시도하는데 같은 4번이 나왔고 4번 자리를 보니 이미 값이 있어서 Hash Table이 그 옆자리에 넣었다.

이게 Linear Probing이다. 그래서 Linear Probing을 정리하자면,

• Linear Probing : 이미 자리에 값이 있으면 다음 자리에 추가한다.

근데, 이 문제의 단점이 있다. Collision이 많이 일어나면 그 주변에 병목현상이 생길 수 있다는 것.

예를 들어, 저 모양 그대로 HateFood/Coffee라는 Pair를 넣으려고 시도하는데 Hash Function이 또 4를 뱉어냈다. 그래서 4에 가보니 값이 있어서 그다음 5에 가보니 또 값이 있어서 6으로 가서야 넣게 됐다.

그래서 이 Linear Probing 문제를 또 해결하는 방법이 Quadratic Probing이다.

Quadratic Probing

다음 자리를 찾을 때 hash(x) + i가 아니라 hash(x) + i^2 자리에 넣는 방식이다. 그러니까 4가 나오면 Linear Probing은 5에 넣는 건데 Quadratic Probing은 16에 넣는다.

Hash Table의 시간 복잡도와 공간 복잡도

시간 복잡도

두 가지 케이스로 나뉠 수 있다.

• Hash Collision이 없을 때
  • 데이터 추가  
    • Key 값 해시하기 O(1)
    • 데이터 넣기 O(1)
    • O(1) + O(1) = O(1)
  • 데이터 읽기
    • Key 값 해시하기 O(1)
    • 데이터 읽기 O(1)
    • O(1) + O(1) = O(1)
• Hash Collision이 있을 때
  • 데이터 추가/읽기
    • Key 값 해시하기 O(1)
    • 최악의 경우 데이터 넣기, 읽기가 O(N)이 될 수 있음.
      • (왜냐하면, Hash Function이 잘못 만들어진 경우 계속해서 같은 Output을 만들어 내는 최악의 Hash Function이 있으면 Linked List 추가의 경우 마지막 자리를 알기 위해 1-N까지 데이터가 있을 때 처음부터 하나씩 자리를 찾아야 하고, 읽기의 경우 해당 데이터가 어디 있는지 알기 위해 N개의 노드를 다 뒤져야 할 수도 있으므로)
      • 근데, 이건 정말 최악의 경우인 거고 어지간하면 O(1)이 된다. 우선 Key 값 해시하는 건 언제나 O(1)이고 Hash Function이 문제없이 잘 만들어졌다면 바로바로 데이터를 넣거나 읽을 수 있게 된다.
  • 그래서 어지간하면 이 경우도 O(1)이 맞고, 정말 정말 잘못 만들어진 Hash Function이라면 O(N)이 될 수도 있다는 것으로 알아두면 좋을듯하다.

공간 복잡도

구분 없이 O(N). 

N개의 데이터를 넣으려면 그에 맞는 배열 사이즈가 있어야 하고(N) 해당 데이터 타입의 Byte를 가지는 메모리 공간(X) = N * X => O(N).

Binary Search Tree는 진짜 중요한 개념이다.

Binary Tree를 저번 시간에 배웠고 이 Binary Tree를 다시 상기해보면 자식이 최대 2개까지만 있는 노드로만 구성되어 있는 트리를 Binary Tree라고 했고 이 트리를 탐색하는 방법 중 대표적인 두 가지 DFS, BFS가 있다고 했다.

DFS(Depth First Search)는 깊이 우선 탐색으로 밑으로 더 내려갈 수 없을때까지 계속 아래로 찾아나가는 방식.

BFS(Breadth First Search)는 한 노드의 모든 라인을 다 검색하고 그 바로 다음 아래 라인을 다 검색해가면서 찾아내는 방식이라고 했다.

Binary Search Tree

Binary Search Tree는 Binary Tree에 특정한 룰을 추가한 트리구조이다.

어떤 룰일까? 한 노드를 기준으로 왼쪽 Sub tree는 지금 노드보다 무조건 더 작은값, 오른쪽 Sub tree는 지금 노드보다 무조건 더 큰 값으로만 구성되어 있는 구조를 Binary Search Tree라고 한다.

이 트리는 완벽한 Binary Search Tree이다. 모든 노드를 기준으로 비교해도 왼쪽 Sub tree는 본인보다 작은 값을 가지고 있고, 오른쪽 Sub tree는 본인보다 큰 값을 가지고 있기 때문.

이 구조가 왜 좋고 왜 자주 사용될까? 절반 소거법(Binary Search), 다른말로 '분할 정복 방식'이 가능하기 때문에 효율적으로 원하는 값을 찾아낼 수 있기 때문이다.

예를 들어 저 트리에서 10을 찾고 싶다고 해보자. 다음 단계를 거쳐간다.

1단계

처음 루트 노드에게 10이거나 10보다 크니? 라고 물어봐서 10이면 끝. 10이 아닌 경우 10보다 작다고 말할 테니 오른쪽으로 이동.

여기서 오른쪽으로 이동하면 5를 기준으로 왼쪽은 볼 필요가 없어진다. 이게 절반 소거법의 장점이다.

2단계

그 다음 노드인 8에게 10이거나 10보다 큰지를 물어본다. 10이라면 끝. 10이 아닌 경우 10보다 작다고 말할테니 오른쪽으로 이동.

3단계

단 세번의 질문으로 원하는 10을 찾아냈다. 여기서 세번은 트리의 깊이(Depth)를 말한다. 

5번 노드가 있는 1 Depth.

2, 8번 노드가 있는 2 Depth.

10번 노드가 있는 3 Depth.

이렇게 트리의 깊이만큼만 질문해서 원하는 답을 찾아낼 수 있다.

Binary Tree vs Binary Search Tree

Binary Search Tree

N개의 노드를 가진 꽉 찬 트리의 경우 트리의 깊이는 log N이다.

그래서 이 Binary Search Tree 구조로 원하는 값을 찾을 때 시간 복잡도는 O(log N)이다.

Binary Tree

정렬된 트리가 아니라 원하는 값을 찾기 위해 DFS 또는 BFS를 통해 찾아낸다.

결국 최악의 경우 N개의 노드를 가진 트리에서 N의 값을 찾는 시간 복잡도는 O(N)이다.

따라서 Binary Search Tree가 더 빠른 속도로 원하는 값을 찾아낼 수 있다.

Binary Search Tree 코드로 구현해보기

struct Node* find_node(struct Node* root, int findValue) {
	if (root == NULL || root->value == findValue) {
    	return root;
    } else if (root->value > findValue) {
    	return find_node(root->left, findValue);
    } else {
    	return find_node(root->right, findValue);
    }
}

위 코드가 Binary Search Tree 구조에서 원하는 값을 찾아내는 코드이다. 역시 Recursion(자기 자신 참조)을 통해 간단하게 구현할 수 있다. 순서대로 한 번 접근해보자. 

1. 10을 찾고싶다고 할때, root node인 5가 최초로 들어온다.

2. root(5)는 NULL이 아니고 root(5)가 가진 값이 10이 아니므로 다음 if로 간다.

3. root(5)가 가진 값 5가 찾고자하는 값 10보다 크지 않기 때문에 다음 else로 간다.

4. 자기 자신을 호출한다 이때 파라미터는 root(5)의 오른쪽 노드 8과 찾고자하는 값 10.

5. 역시 root(8)는 NULL이 아니고 root(8)가 가진 값이 10이 아니므로 다음 if로 간다.

6. root(8)이 가진 값 8이 10보다 크지 않으므로 다음 else로 간다.

7. 자기 자신을 호출한다. 여기서 파라미터는 root(8)의 오른쪽 노드 10과 찾고자하는 값 10.

8. root(10)은 NULL이 아니지만, root(10)의 값 10과 찾고자 하는 값 10이 같으므로 이 root를 리턴한다.

9. 7번으로 돌아온다. 호출한 자기자신이 반환한 root(10)을 리턴한다.

10. 4번으로 돌아온다. 호출한 자기자신이 반환한 root(10)을 리턴한다. 끝.

이런식으로 절반을 소거해가면서 찾아내는 방법을 Binary Search라고 하고 그 구조가 Tree일 때 Binary Search Tree라고 한다.

Binary Search가 꼭 Tree여야하나?

그럼 여기서 질문이 생긴다. Binary Search는 꼭 트리일 필요는 없을 것 같다. 왜냐하면 배열에 값을 정렬해 놓아도 Binary Search로 검색할 수 있으니까. 맞다. 똑같이 시간 복잡도는 O(log N)이다.

이러한 정렬된 배열에 중간을 잡고 물어보면 똑같다. 

1단계

정렬된 배열에 중간에 10이거나 10보다 큰지 물어본다. 10이라면 끝. 10이 아니면 10보다 작으니 오른쪽만 보면 된다.

2단계

오른쪽을 기준으로 중간에서 10이거나 10보다 큰지 물어본다. 10이라면 끝. 10이 아니면 10보다 작으니 오른쪽만 보면 된다.

3단계

그럼 뭐하러 Binary Search Tree를 사용할까? 

정렬된 배열에 값이 새로 추가되거나 제거되는 경우가 없으면 정렬된 배열이 더 좋을 수 있다.

근데, 새롭게 추가되는 값이 있을 땐 그 값을 추가한 후 다시 정렬을 해야하는 과정이 필요하다.

예를 들어보자, 저 배열에 4를 추가하고 싶다고 해보자.

그럼 정렬을 위해 2와 5사이에 넣어야하고 그럼 5부터 마지막을 뒤로 전부 밀어야한다. 이 작업의 시간 복잡도는 O(N)이다.

근데! Binary Search Tree는 이 작업도 O(log N)이다.

"왜요?" Binary Search Tree에서 N개의 노드를 가진 꽉 찬 트리의 경우 깊이는 log N이라고 했고 그래서 트리에서 원하는 값을 찾을 때 질문의 횟수는 트리의 깊이(Depth)만큼이라고 했다.

그럼 원하는 자리를 찾는데 시간 복잡도는 O(log N).

원하는 자리를 찾았으니 추가하는(지우는) 시간 복잡도는 O(1). 

두 경우를 모두 하는 시간 복잡도는 O(log N) + O(1) = O(log N)

O(N)과 O(log N)을 비교하면 압도적으로 빠른 수치다. 예를 들어, 전 세계 인구가 80억명이면 log(80억명) = 32이다.

80억개의 경우의 수를 Binary Search Tree로 만들면 내가 원하는 값을 찾는데 32번만에 가능하단 얘기다. 

근데 O(N)은...? 최악의 경우.. 80억번..?? 

근데! 여기서 하나 더, 꽉 찬 트리가 아니면?

만약, Binary Tree는 Binary Tree인데 꽉 찬 트리가 아니라 이런 모양이면 어떻게 할까?

이것도 Binary Tree다. 자식이 최대 2개를 만족하고 오른쪽은 다 자신보다 크니까.

이런 경우 트리의 Depth만큼 찾아내는 시간 복잡도는 O(log N)이 아니라 O(N)이다. 

결론부터 말하면 이런 경우는 고려하지 않아도 된다. Self-Balancing Binary Search Tree라는게 있는데 저런 모양이 나올 수 없게 새 노드가 추가되거나 삭제될 때 Binary Search Tree가 항상 Balance가 되도록 보장해준다.

Self-Balancing Binary Search Tree의 종류로 AVL Tree, Red Black Tree 이런게 있고 이런게 있다는 것 정도만 알아두자.

우선 BFS, DFS를 알기 전 Tree를 알아야 하는게 먼저더라.

Tree

트리란, 부모 자식 관계를 나타낼 수 있는 자료 구조다.

다음 그림이 트리라고 말 할 수 있다.

- 노드 하나에 한개의 Parent 노드가 있을 수 있다.

- 노드 하나에 여러개의 Child 노드가 있을 수 있다.

이런 유형의 자료구조는 실생활에서도 너무 많이 접해볼 수 있다. 

• 회사 조직도
• 가족 관계도
• File System

이런 트리 중 특별한 트리가 있는데 'Binary Tree'라는 게 있다.

Binary Tree

한 노드에 Child 노드가 최대 2개까지만 있는 트리를 Binary Tree라고 한다.

위 그림은 그럼 Binary Tree라고 할 수 없다. 왜냐하면, 한 노드(Node 1)가 Child Node를 3개까지도 가지고 있으니까.

Binary Tree는 Linked List와 굉장히 유사하게 생겼다. Linked List의 구조는 다음과 같다.

그리고 이 Linked List의 한 노드를 코드로 표현한다면 다음처럼 표현할 수 있겠다.

struct Node {
    int value;
    struct Node *next;
}

그럼 바이너리 트리는 여기에 자식이 하나씩 더 있을 수도 있는것뿐.

다음 그림이 Binary Tree라고 표현할 수 있다.

이 Binary Tree의 한 노드를 코드로 표현한다면 다음처럼 작성할 수 있다.

struct Node {
    int value;
    struct Node *left_child;
    struct Node *right_child;
}

그래서, 이 바이너리 트리 구조를 메모리 상에서 어떻게 표현될지를 봐보자.

하나에 4 Byte 메모리 구조를 보자. 

Node 1은 값으로 1을 가지고 있고, left_child, right_child에 대한 각각의 주소를 가리키는 포인터를 가지고 있다.

Node 1의 left_child가 가리키는 주소를 따라가면 Node 2가 가진 값 2가 나온다. 

Node 1의 right_child가 가리키는 주소를 따라가면 Node 3가 가진 값 3이 나온다. 

Node 3은 자식이 없기 때문에 가리키는 포인터도 없다.

Node 2는 하나의 자식을 left_child가 가리키고 있고 그 주소를 따라가면 Node 4가 가지고 있는 값 4가 나온다.

Node 4도 자식이 없기 때문에 가리키는 포인터도 없다.

Tree, Binary Tree 둘 다 뭔지 알겠다. 그럼 이 트리를 어떻게 탐색할까? 이 탐색하는 방법이 앞에서 말한 DFS, BFS가 된다.

DFS (Depth First Search)

트리를 탐색하는 가장 일반적인 방법 중 하나인 깊이 우선 탐색(DFS)가 있다.

다음 트리를 보자.

DFS는 깊이 우선 탐색, 즉 한쪽 방향으로 탐색을 시작했으면 더 내려갈 수 없을때까지 아래로 내려가서 확인하는 것을 말한다.

그래서 Node1 부터 탐색을 시작하고 왼쪽 또는 오른쪽으로 하나 방향을 잡은 후 그 방향의 가장 하단까지 쭉 검색하고 다시 반대편으로 돌아오는 방식이라고 생각하면 된다. 

예시

1단계

2단계

3단계

3단계가 끝나고 더 내려갈 수 없을 만큼 내려왔으니 다시 Node 1으로 가서 왼쪽을 다 털었으니 오른쪽으로 털기 시작한다.

4단계

5단계

6단계

Node 3을 기준으로 왼쪽 끝까지 갔으니 이제 다시 Node 3의 오른쪽을 털면 된다.

7단계

그럼, DFS는 코드로 어떻게 구현할 수 있을까?

DFS 코드로 구현하기

DFS(Depth First Search)는 Recursion(자기 자신 참조)으로 간단하게 구현할 수 있다. 

난 JAVA를 좋아하니까 JAVA로 구현해보겠다.

TreeNode

package dfs.binarytree;

public class TreeNode {
    private final int value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

BinaryTree

package dfs.binarytree;

public class BinaryTree {
    public static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.println("node Value = " + root.getValue());

        dfs(root.getLeft());
        dfs(root.getRight());
    }
}

Main

package dfs.binarytree;

public class Main {
    public static void main(String[] args) {

        TreeNode nodeOne = new TreeNode(10);
        TreeNode nodeTwo = new TreeNode(20);
        TreeNode nodeThree = new TreeNode(30);
        TreeNode nodeFour = new TreeNode(40);
        TreeNode nodeFive = new TreeNode(50);
        TreeNode nodeSix = new TreeNode(60);
        TreeNode nodeSeven = new TreeNode(70);

        nodeOne.setLeft(nodeTwo);
        nodeOne.setRight(nodeThree);

        nodeTwo.setLeft(nodeFour);

        nodeThree.setLeft(nodeFive);
        nodeThree.setRight(nodeSix);

        nodeFive.setLeft(nodeSeven);

        BinaryTree.dfs(nodeOne);
    }
}

실행결과:

node Value = 10
node Value = 20
node Value = 40
node Value = 30
node Value = 50
node Value = 70
node Value = 60

코드를 보면 굉장히 간단하지만 이 코드가 DFS를 구현한 코드이다.

아래 그림을 가지고 위 코드를 돌려보는 시뮬레이션을 해보자.

1. [root = Node 1], root는 NULL이 아니니까 다음 라인으로 가서 printf호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

2. [root = Node 2], root는 NULL이 아니니까 다음 라인으로 가서 printf호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

3. [root = Node 4], root는 NULL이 아니니까 다음 라인으로 가서 printf호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

4. [root = NULL], root가 NULL이므로 return

5. 3으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

6. [root = NULL], root가 NULL이므로 return

7. 3번으로 돌아옴 모든 라인이 끝났으니 return

8. 2번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

9. [root = NULL] root가 NULL이므로 return

10. 2번으로 돌아옴. 모든 라인이 끝났으니 return

11. 1번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

12. [root = Node 3], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

13. [root = Node 5], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

14. [root = Node 7], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child. 

15. [root = NULL], root가 NULL이므로 return

16. 14번으로 돌아옴 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

17. [root = NULL], root가 NULL이므로 return

18. 14번으로 돌아옴. 모든 라인이 끝났으니 return

19. 13번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

20. [root = NULL], root가 NULL이므로 return

21. 13번으로 돌아옴. 모든 라인이 끝났으니 return

22. 12번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

23. [root = Node 6], root는 NULL이 아니니까 다음 라인으로 가서 printf 호출 후 자기 자신을 호출하는데 주는 파라미터가 왼쪽 Child.

24. [root = NULL], root가 NULL이므로 return

25. 23번으로 돌아옴. 자기 자신을 호출하는데 주는 파라미터가 오른쪽 Child.

26. [root = NULL], root가 NULL이므로 return

27. 23번으로 돌아옴. 모든 라인이 끝났으니 return 

28. 12번으로 돌아옴. 모든 라인이 끝났으니 return

29. 1번으로 돌아옴. 모든 라인이 끝났으니 return

끝

이렇게 Recursion을 통해 DFS를 구현할 수 있다. 이제 BFS를 알아보자.

BFS (Breadth First Search)

BFS(Breadth First Search)는 넓이 우선 탐색으로 이것 역시 트리를 검색하는 방법 중 대표적인 하나이다.

이건 DFS랑 어떻게 다른지 그림을 통해 알아보자.

0단계

가장 최상위 노드인 Node 1을 검색한 후 다음 한 칸 밑에 있는 모든 노드를 쭉 털고, 그 다음 한 칸 밑에 있는 모든 노드를 쭉 털고, 이렇게 한 라인을 쭉 터는식으로 검색하는 방식이다.

1단계

2단계

3단계

4단계

5단계

6단계

이렇게 트리의 한 라인 한 라인을 쭉 터는 방식으로 검색하는게 BFS라고 생각하면 된다.

이 BFS는 코드로 어떻게 구현할까?

BFS 코드로 구현하기 

BFS(Breadth First Search)는 Queue로 간단하게 구현할 수 있다.

Queue는 저번 포스팅에서 배웠지만 FIFO구조. 그리고 Queue는 처음과 끝을 알아야하는 자료구조이다. 

코드로 어떻게 구현하는지 살펴보자.

void bfs(struct Node* root) {
	if (root == NULL) {
    	return;
    }
    
    struct TreeNode* queue[10000];
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front != rear) {
    	struct TreeNode* curr = queue[front++];
        printf("%d ", curr->val); // 실제 작업을 여기서 하면됨, 지금은 예제니까 출력을 함
        if (curr->left != NULL) {
        	queue[rear++] = curr->left;
        }
        if (curr->right != NULL) {
        	queue[rear++] = curr->right;
        }
    }
}

예제에서 Queue 사이즈는 어느정도 크게 설정했다. 어떤 문제를 푸냐에 따라 달라지겠지만 지금으로선 10000으로 충분하기 때문에.

이것도 그림과 같이 한단계씩 알아보자.

[root = Node 1]. root는 NULL이 아니다.

- queue를 만든다.

- Queue를 만들고 rear에 root(Node1)를 넣고 rear를 하나 추가한다. 

- front와 rear는 같지 않기 때문에 while 루프를 돌기 시작한다.

- 여기서 queue의 front값인 Node1을 curr에 넣고, front를 하나 추가한다.

- curr의 값 1을 찍는다. 

- Node1의 left child(Node2)가 NULL이 아니니까 rear 자리에 left child를 넣고 rear를 하나 추가한다.

- Node1의 right child(Node3)가 NULL이 아니니까 rear자리에 right child를 넣고 rear를 하나 추가한다.

- 루프가 끝나고 역시 front와 rear는 다르니까 계속 돈다.

- curr에 front가 가리키는 Node2를 넣고 front를 하나 추가한다.

- curr의 값 2를 찍는다.

- Node2의 left child(Node4)가 NULL이 아니니까 rear 자리에 left child를 넣고 rear를 하나 추가한다.

- Node2의 right child는 NULL이니까 아무것도 하지 않고 루프가 끝난다.

- front와 rear가 다르니까 루프는 계속된다.

- 현재 front의 node(Node3)를 curr에 넣고 front를 하나 추가한다.

- curr의 값 3을 찍는다.

- Node3의 left child(Node5)가 NULL이 아니니까 rear에 left child를 넣고 rear를 추가한다.

- Node3의 right child(Node6)가 NULL이 아니니까 rear에 right child를 넣고 rear를 추가한다.

- 루프가 끝나고 다시 front와 rear는 다르기 때문에 또 돈다.

- 현재 front가 가리키는 Node4를 curr에 집어넣고 front를 하나 추가한다.

- curr의 값 4를 찍는다.

- curr의 left child와 right child모두 NULL이니까 아무것도 하지 않고 다음 루프로 간다.

- front와 rear는 다르니까 루프가 계속된다.

- 현재 front에 담긴 Node5를 curr에 담고 front를 하나 추가한다.

- curr의 값 5를 찍는다.

- curr의 left child(Node7)는 NULL이 아니니까 rear에 넣고 rear를 하나 추가한다.

- curr의 right child는 NULL이니까 다음 루프로 간다.

- 여전히 front와 rear는 다르니까 루프는 계속된다.

- 현재 프론트에 담긴 Node6을 curr에 담고 front를 하나 증가시킨다.

- curr의 값 6을 찍는다.

- curr의 left, right child가 모두 NULL이므로 아무것도 하지않고 다음 루프로 간다.

- 여전히 front와 rear는 다르기 때문에 루프는 계속된다.

- 현재 front가 가리키는 Node7을 curr에 넣고 front를 하나 추가한다.

- curr의 값 7을 찍는다.

- curr의 left, right child 모두 NULL이니까 루프가 끝난다.

- 루프의 조건 front != rear를 만족하지 않으므로 루프는 끝난다. 

정리

DFS, BFS 모두 트리를 탐색할 때 방법 중 하나이다. DFS(Depth First Search)는 깊이 우선 탐색, BFS(Breadth First Search)는 넓이 우선 탐색의 줄임말로 둘 다 어떻게 탐색하는지 꼭 알아두면 좋을것같다.

Stack은 위에만 구멍이 뚫린 박스라고 생각하면 된다.

이 그림이 Stack 구조이다.

먼저 들어간 데이터가 가장 마지막에 나온다.

가장 마지막에 들어간 데이터가 가장 먼저 나온다. LIFO.

Stack은 중간에 데이터를 넣는것도 불가능하고 맨위에 데이터를 새로 넣거나 맨위에 있는 데이터를 빼거나해야 한다.

코드적으로 접근해보기

Stack은 보통 이러한 메서드들을 가지고 있다.

• pop(): 가장 최근에 추가된 데이터 빼기
• push(item): 데이터 새로 추가하기
• peek(): 가장 최근에 추가된 데이터 읽기
• isEmpty(): Stack이 비어있는지 확인하기

다음 그림과 같이 사이즈가 7인 Stack이 있다고 해보자.

1. 이 상태에서 push(8)을 하면 다음 그림이 된다.

2. 이 상태에서 또 push(10)을 하면 다음 그림이 된다.

3. 이 상태에서 peek() 메서드를 호출하면 10을 반환한다. 가장 마지막에 넣은 녀석을 가져오는 메서드니까.

4. 이 상태에서 isEmpty() 메서드를 호출하면 false를 반환한다.

5. 이 상태에서 pop()을 호출하면 10이 나온다.

6. 이 상태에서 pop()을 한번 더 호출하면 8이 나온다.

7. 여기서 isEmpty()를 호출하면 true가 나온다.

그래서 Stack의 특징은 맨 위(가장 마지막)만 알면 모든 처리가 가능하다.

Stack의 예시 코드

#define MAX_SIZE 100

typedef struct {
	int stack[MAX_SIZE];
    int pop;
} Stack;

void initialize(Stack* s) {
	s->top = -1; // 최초에는 아무 데이터도 들어가지 않으니까 -1
}

int pop(Stack* s) {
	if (isEmpty(s)) {
    	printf("Stack Underflow: Cannot pop element from the stack.\n");
        return -1;
    }
    
    int item = s->stack[s->top--];
    return item;
}

void push(Stack* s, int item) {
	if (s->top == MAX_SIZE -1) {
    	printf("Stack Overflow: Cannot push element onto the stack.\n");
        return;
    }
    
    s->stack[++s->top] = item;
    printf("%d pushed onto the stack.\n", item);
}

int peek(Stack* s) {
	if (isEmpty(s)) {
    	printf("Stack is empty.\n");
        return -1;
    }
    
    return s->stack[s->top];
}

bool isEmpty(Stack* s) {
	return (s->top == -1);
}

Stack test

int main() {
    Stack stack;
    initialize(&stack);
    ...
}

여기까지 하면 이런 그림이 된다.

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    ...
}

여기까지 하면 이런 그림이 된다.

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    ...
}

여기까지 하면 이런 그림이 된다.

이 상태에서 peek()메서드를 호출하면? 30을 반환한다.

다음과 같이 pop()메서드를 호출하면 어떻게 될까?

int main() {
    Stack stack;
    initialize(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    
    pop(&stack);
    ...
}

이런 그림이 된다.

정리

이런 자료구조를 Stack이라고 한다. 그럼 자주 들어봤던 Stack Overflow는 어떤 순간에 발생하는걸까?

일단 Overflow니까 꽉 차서 더 못넣는다는 얘기인데, 자바 메모리 구조를 생각해보면 항상 실행하는 메서드를 순차적으로 Stack에 집어넣게 되어 있다.

최초의 main() 메서드가 실행되고 main()에서 A()라는 메서드를 호출하고 A()메서드가 B()라는 메서드를 호출하면 처리하는 순서는 B -> A -> main이 된다. 이게 정확하게 Stack의 구조다.

그래서 이 Stack에 계속해서 쌓이는 무언가가 Stack Overflow를 일으키는데 대표적인 예시가 자기 자신을 무한하게 호출하는 경우가 그렇다. 자기가 자기 자신을 계속 호출 호출 호출 무한루프에 빠지는거지. 그럴때 이제 더 이상 Stack에 넣을 자리가 없어서 Stack Overflow가 발생한다.

이번엔 Queue를 정리해보자.

Queue는 위 아래 모두 구멍이 있는 박스라고 생각을 하면 된다.

그림을 보면 데이터는 위에서만 넣을 수 있고 빠지는 건 아래에서부터 빠진다.

이런 구조라면 먼저 들어간 데이터가 먼저 나오는 구조가 된다.

Queue는 FIFO(First In First Out) 구조이다.

코드적으로 생각해보기

Queue가 가지고 있는 보통의 대표적인 메서드는 다음과 같은 것들이 있다.

• enqueue(item): 데이터 추가하기
• dequeue(): 가장 오래된 데이터 빼기
• peek(): 가장 오래된 데이터 보기
• isEmpty(): Queue가 비었는지 확인하기

비어있는 사이즈가 7인 큐가 있다.

1. 이 상태에서 데이터 1을 넣으면 다음 모양이 된다.

2. 그리고 데이터 2를 또 추가적으로 넣는다면 이런 모양이 된다.

이 상태에서 peek() 메서드를 호출하면 결과는 1이다.

가장 먼저 넣은 데이터가 가장 오래된 데이터.

이 상태에서 isEmpty() 메서드를 호출하면  결과는 false다.

3. 데이터를 빼보자. 가장 먼저 들어간 1이 나온다.

4. 또 빼보자. 그 다음으로 들어간 2가 나온다.

이런 구조가 큐이고 가장 먼저 들어간 녀석을 빼는 작업과, 비었는지 안 비었는지를 확인할 수 있으려면 큐 구조는 시작과 끝을 알고 있어야 한다.

struct Queue

#define MAX_SIZE = 100

struct queue {
	int data[100];
    int front, rear;
}

void init_queue(struct queue *q) {
	q->front = q->rear = 0;
}

void enqueue(struct queue *q, int value) {
	if (q->rear == 100) {
    	printf("Queue is full.\n");
        return;
    }
    q->data[q->rear++] = value;
}

int dequeue(struct queue *q) {
	if (q->front == q->rear) {
    	print("Queue is empty\n");
        return -1;
    }
    return q->data[q->front++];
}

int is_empty(struct queue *q) {
	return q->front == q->rear;
}

int peek(struct queue *q) {
	if (q->front == q->rear) {
    	printf("Queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}

Queue test

int main() {
    struct queue q;
    init_queue(&q);
	...
}

이 코드를 수행하면 다음과 같은 그림이 된다.

int main() {
    struct queue q;
    init_queue(&q);
    enqueue(&q, 1);
    ...
}

이 코드를 수행하면 큐에 1을 넣는다. 그러면 가장 오래된 데이터를 가르키는 위치와 다음에 넣을 수 있는 위치에 대한 정보가 변한다.

다음 그림처럼.

int main() {
    struct queue q;
    init_queue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    ...
}

이렇게까지 코드가 수행되면 다음 그림이 된다.

int main() {
    struct queue q;
    init_queue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    int value = dequeue(&q);
    ...
}

이제 dequeue() 메서드를 호출한다. 가장 오래된 데이터(1)가 나오게 된다. 그리고 가장 오래된 데이터를 큐에서 뺐으니 가장 오래된 데이터를 가르키는 포인터는 변경된다.

만약 이 상태에서 peek() 메서드를 호출하면 나오는 값은 2가 된다. 현재 front가 가르키는 값이 2니까.

만약 이 상태에서 is_empty() 메서드를 호출하면 결과는 false다.

이런것을 큐라고 한다.

큐에서 발생할 수 있는 문제점

다음 그림을 보자.

이렇게 사이즈가 7인 큐에 값을 계속 넣었고 마지막 자리까지 넣었다. 그럼 꽉 찬 상태라 더 넣을 수 없다. 

이 모양일 때 dequeue()를 2번 수행했다고 해보자.

이런 그림이 될 것이다. 그럼 큐는 이제 꽉 차지 않았다. 이때 큐에 넣을 수 있을까? rear가 마지막 자리라 넣을 수가 없다. 

이런 문제를 어떻게 해결할까? Circular Queue.

Circular Queue는 이 문제를 어떻게 해결할까? rear 포인터가 밖으로 벗어나면 맨 앞으로 다시 가져오는 방법이다.

이런 그림이 될 수 있도록.

그렇게 또 다시 채울 수 있게 되고 두번을 더 채우다 보면 다음 그림이 된다.

이렇게 다시 front, rear 포인터가 같은 자리를 가르키면 꽉 찼다는 걸 알 수 있게 된다.

rear, front를 다시 회전시키는 방법은 간단하다.

rear = (rear + 1) % queue_size
front = (front + 1) % queue_size

rear 포인터가 6이 되어서 더 채울 수 없는 공간까지 오면 rear + 1은 7이 된다.

그걸 큐의 사이즈(7)로 나눈 나머지는 0이니까 다시 0을 가리키게 된다.

front 포인터도 같은 방식.

Queue 활용

그래서 큐는 대표적으로 Graph / Tree에서 BFS할 때 사용한다.

오늘부터 자료구조에 대한 내용을 하나씩 정리하기로 했다.

기록을 하지 않으면 알아도 금방 까먹기 때문에 까먹더라도 다시 돌아갈 수 있게.

Array

배열은 메모리에 정해진 사이즈만큼 공간이 만들어져서 데이터를 저장하는 방식이다.

그래서 데이터는 연속적으로 위치한 메모리에 저장되어 있다.

장점

• 연속적으로 메모리에 위치해있기 때문에 인덱스를 통해 빠르게 내가 원하는 값을 찾아낼 수 있다.

단점

• 사이즈가 정해졌기 때문에 정해진 사이즈 이상으로 데이터를 저장할 수 없다.

Linked List

Linked List는 사이즈가 동적으로 할당된다.

메모리 상에 여기저기 흩뿌려져 있는 공간에 원하는 만큼 데이터를 넣을 수 있는 방식이다.

각 데이터는 다음 데이터의 주소를 알고 있는 포인터가 있어서 연결되어 있다.

장점

• 사이즈가 정해진게 아니기 때문에 원하는 만큼 데이터를 추가할 수 있다.

단점

• 메모리 상에 여기저기 흩뿌려져 있기 때문에 데이터를 찾아내려면 처음부터 하나씩 연결된 정보를 찾아 찾아가야 한다.

정리

그래서 둘을 비교하자면 속도 측면에서는 Array가 유리할 수 있다.

저장되는 위치가 연속적이기 때문에 인덱스로 바로 찾아낼 수 있기 때문.

데이터를 동적으로 계속해서 저장하기엔 Linked List가 유리할 수 있다.

사이즈가 고정적이지 않기 때문.

각 장단점을 파악한 후 적절하게 쓰임새에 맞게 사용하면 될 것 같다.

시간복잡도와 공간복잡도

Arrays의 시간 복잡도

• Read: O(1) (특정 인덱스 값을 한번 읽으면 끝)
• Write: O(1) (특정 인덱스에 값을 한번 추가하면 끝)

Arrays의 공간 복잡도

• 배열에 N개의 엔트리가 있다고 했을 때
  • 메모리 사용량
    • 저장하는 타입의 메모리 크기를 C라고 했을 때 C * N = O(N)

Linked List의 시간 복잡도

• Read: O(N) (N번째 원소를 읽기 위해서 시작부터 하나씩 읽어 나가 N번을 찾아야 한다)
• Write: O(N) (마지막에 원소를 넣어야하고 마지막을 찾기 위해 역시나 시작부터 하나씩 읽어가 마지막에 가서 쓰기를 해야한다 마지막 원소를 찾아내는데 O(N), 쓰기 O(1) 따라서 O(N)

Linked List의 공간 복잡도

각 노드가 데이터+포인터를 가지므로 하나의 노드엔 데이터 + 포인터의 공간을 차지. 따라서 N개의 노드를 가진 Linked List는 O(N).

참고: Linked List가 이중 연결 리스트(앞과 뒤 모두 포인터가 있는)여도 O(N). 왜냐하면 노드 수에 비례하기 때문.