개발옹

1. 모노톤 스택(Monotone stack) 이란?

스택(Stack)은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 후입선출(LIFO:Last In, First Out) 형태의 자료구조 입니다.
즉, 가장 먼저 들어온 데이터가 가장 마지막에 나가고, 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.

• 모노톤 스택(Monotone stack)은 특정한 순서를 유지하면서 데이터를 관리하는 스택 자료구조 입니다.
  • Monotone은 증가하거나 감소하는 등의 일정한 경향이 보임을 의미합니다.
• 모노톤 스택(Monotone stack)은 증가하거나 감소하는 일정한 경향을 가진 스택입니다.
• 모노톤 스택(Monotone stack)은 특정 문제에 대해 시간 복잡도를 O(N)으로 줄여주는 매우 효율적인 해결책을 제공합니다.
  • 다음/이전 데이터의 최댓값/최솟값을(Nearest Greater/Smaller Element) 찾는 문제에 유용하게 쓰입니다.

2. 모노톤 스택(Monotone stack)의 종류 및 구현

스택은 LIFO(Last In, First Out) 자료 구조이기 때문에 모노톤 스택의 최상위 요소를 제거하면서 단조 증가/감소 순서를 유지합니다. 새로운 요소는 항상 최상위에 추가됩니다.

1) 단조 증가 스택(Monotone Increasing Stack)

• 스택의 요소들이 오름차순으로 정렬되는 스택
  • 오름차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 커진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 내려갈수록 값이 작아짐

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 크거나 같은 경우를 유지하는 스택
  
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 작거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 항상 특정 순서(오름차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

2) 단조 감소 스택(Monotone Decreasing Stack)

• 스택의 요소들이 내림차순으로 정렬되는 스택
  • 내림차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 작아진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 갈수록 값이 커짐

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 작거나 같은 경우를 유지하는 스택
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 크거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 특정 순서(내림차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 작거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() <= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 클 때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

3. 모노톤 스택(Monotone stack) 구현 - 예시로 확인

개인적으로 모노톤 스택의 종류에 대해 이해하는데에 조금 시간이 걸렸습니다. 단조 증가 스택과 단조 감소 스택의 정렬 순서가 어디부터 시작하는지에 대한 정확한 이해를 못하고 무작정 이해하려고 하다보니 헷갈렸습니다. 

그래서 마지막으로 배열 예시를 정리하면서 아직은 조금 헷갈리는 부분을 정리해보겠습니다.

public static void main(String[] args) {
    int[][] testArrays = {
        {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
        {10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
        {5, 5, 4, 4, 3, 3, 2, 2, 1, 1},
        {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}
    };

    for (int[] arr : testArrays) {
        System.out.println("Monotonic Stack for array: " + Arrays.toString(arr));
        incresing(arr);
        decresing(arr);
        System.out.println();
    }
}

테스트 배열을 위와 같이 4가지 정도로 생성해두고 단조 증가 스택과 단조 감소 스택을 출력해보았습니다.

*각 스택은 2번 목차의 코드를 수행해서 생성

위 코드에 대한 출력 결과는 아래와 같습니다.

Monotonic Stack for array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Monotonic Increasing Stack: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
Monotonic Decreasing Stack: 10, 

Monotonic Stack for array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 

Monotonic Stack for array: [3, 6, 1, 9, 4, 7, 2, 8, 5, 10]
Monotonic Increasing Stack: 10, 5, 2, 1, 
Monotonic Decreasing Stack: 10,

단조 증가 스택은 요소들이 오름차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

단조 감소 스택은 요소들이 내림차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

인 점을 머리속에 꼭 담아두고 출력 결과를 확인해보면, 제대로 출력되는 것을 알 수 있습니다.

코드 구현시 중복 값은 허용하지 않았기 때문에 3번 예시처럼 중복 값이 없는 것을 확인할 수 있습니다.

만약 중복을 허용한다면 아래와 같은 결과가 출력됩니다.

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 1, 
Monotonic Decreasing Stack: 1, 1, 2, 2, 3, 3, 4, 4, 5, 5,

단조 증가 스택 함수는 아래와 같을때 마지막 예시인 {3, 6, 1, 9, 4, 7, 2, 8, 5, 10} 에 대한 단조 증가 스택 생성 과정을 구체적으로 보겠습니다.

public static void incresing(int[] arr) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i=0; i<arr.length; i++) {
        // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
        while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
        	stack.removeFirst();
        }
        // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
        stack.offerFirst(arr[i]);
    }
}

• 배열: {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}

최종적으로 스택을 출력하면 [10, 5, 2, 1] 이 출력됩니다.

스택의 맨 위 요소가 현재 배열 요소보다 크거나 같으면 스택에서 제거하고, 현재 요소를 스택에 추가하면서 단조성을 유지할 수 있는 것입니다.

4. 모노톤 스택(Monotone stack) 관련 문제

• 백준 - 탑 보기

참고 링크

지난번에 트라이를 공부하고 포스팅으로 정리했는데, 아래 포스팅에서는 Map Interface로 구현을 했었습니다.

그런데 백준 - 전설(19585)을 트라이 자료구조로 풀어도 시간 초과가 나길래 더 찾아보니 Array로 구현하는 방식도 있어서 이번에는 Array 방식으로 구현한 트라이도 추가했습니다.

트라이(Trie)란?

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조로, 자세한건 지난번 포스팅을 참고해주세요.

트라이(Trie) 구현 방식

트라이(Trie)는 두 가지 방식으로 구현할 수 있습니다.

1. Array를 이용하여 구현
2. Map Interface를 이용하여 구현

Array로 구현할 경우, 빠른 저장과 탐색을 할 수 있다는 장점이 있지만 필요한 메모리의 크기가 너무 크다는 것이 단점입니다.

Map Interface로 구현할 경우, 메모리를 동적으로 할당하여 필요 노드만 메모리를 할당할 수 있다는 장점이 있지만 메모리 제한이 있는 경우 최적화 작업이 꽤 까다롭다는 단점이 있습니다.

1. Array로 구현

Array로 구현할 경우, Trie의 Node별 자식 노드를 Node형 배열로 구현합니다. 

이때, Trie Node에 들어가는 단어는 영어 소문자만 있다고 가정하며, 각 노드는 영어 소문자를 정수형(int)으로 변환하여 인덱스로 사용합니다.

* 자세한 설명은 이전 포스팅을 참고해주세요.

Node 클래스 생성

Map으로 구현한 Trie 의 Node와 다르게 자식 노드를 Node[] 로 초기화합니다.

childNode의 인덱스에 영어 소문자를 정수형(int)로 변환한 값이 들어가게 됩니다.

그리고 자식 노드의 수(childCnt)와 해당 노드의 문자(val)도 저장해줍니다.

static final int SIZE = 26; // 영어 소문자는 26자
private class Node {
    Node[] childNode = new Node[SIZE]; // 자식 노드: 영어 소문자를 인덱스화 하여 저장
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
    int childCnt = 0; // 자식 노드 수
    char val; // 노드의 문자
}

트라이(Trie) 자료구조 클래스 생성

public class TrieArray {
    private Node rootNode;
    public TrieArray() {
    	rootNode = new Node();
    }
}

기본 메서드

1) 노드 추가(insert)

문자열의 문자를 순회하면서 해당 문자가 자식노드로 있는지 확인하여 노드를 추가하는 메서드입니다. 

Map으로 구현했을때와는 다르게 현 노드의 자식 노드가 null 이 아닌지, 즉, 생성되어있는지를 확인하여, 없다면 생성합니다. 

생성시에는 자식 노드를 추가하고, 자식 노드의 문자를 할당해주고, 현 노드의 자식 노드 수를 증가시킵니다.

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드 확인
    for (int i=0; i < word.length(); i++) {
        char c = word.charAt(i);
        // 단어의 특정 문자를 인덱스(int)로 변환
        int intVal = charToInt(c);
        // 현 노드에 인덱스로 변환한 문자가 자식노드로 있는지 확인
        if (node.childNode[intVal] == null) {
            // 자식 노드에 없는 문자라면 새로 생성
            node.childNode[intVal] = new Node();
            node.childNode[intVal].val = c;
            node.childCnt++;
        }
        // 다음 탐색 노드를 자식노드로 변경
        node = node.childNode[intVal];
    }
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

2) 포함 여부 확인(contains)

문자열이 트라이에 있는지 확인하는 메서드로, 배열 방식에 맞게 구현해주면 됩니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        int intVal = charToInt(c); // 문자를 인덱스로 변환
        if (node.childNode[intVal] == null) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode[intVal];
    }
    return node != null && node.endOfWord; // 마지막 문자 여부를 반환
}

3) 노드 삭제(delete)

트라이에 존재하는 문자열을 삭제하는 메서드로, 삭제 조건에 맞춰 배열 방식에 맞게 구현해주면 됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
public void delete(Node node, String word, int idx) {
    // 단어의 마지막인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    } else {
        if (node.childCnt == 0) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    }

    char c = word.charAt(idx); // 현재 확인해야하는 문자
    int intVal = charToInt(c); // 문자를 인덱스로 변환

    Node child = node.childNode[intVal]; // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 삭제되었다면, 현 노드의 자식 노드 수 1 차감
    if (node.childNode[intVal] == null) node.childCnt--;
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childCnt == 0 && !node.endOfWord) node = null;
}

🧪 구현 테스트

구현 테스트는 Map 방식과 동일하니, 해당 포스팅을 참고해주세요 :)

💡 전체 코드(Array로 구현)는 아래 링크에서 확인해주세요.

2. Map Interface로 구현

아래 코드는 Map Interface로 구현한 코드이며, 자세한 설명은 이전 포스팅을 참고해주세요.

💡 Trie를 Map, Array로 구현한 코드는 아래 링크에서 확인해주세요.

Reference

1. 트라이(Trie)란?

원하는 요소를 찾기위해 자주 사용되는 이진 검색 트리 등에서는 타겟 요소를 찾는데에 O(logN)의 시간이 걸립니다.
하지만 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에,
원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸립니다.
따라서 이 작업을 여러번 수행한다면 시간이 오래 걸리게 됩니다. 
이러한 문자열 검색시의 단점을 해결하기 위해 나온 자료구조가 트라이(Trie)입니다.

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 구글이나 네이버 등에 검색어를 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 합니다.
• 래딕스 트리(Radix Tree)나 접두사 트리(Prefix Tree), 탐색 트리(Retrieval Tree)라고도 합니다
  • 트라이(Trie)는 Retrieval Tree에서 나온 단어

예를 들어 'Tistory'라는 단어를 검색하기 위해 제일 먼저 'T'를 찾고, 다음에 'i', 's', 't', ... 의 순대로 찾으면 됩니다.

이런 개념을 적용한 자료구조가 트라이(Trie)입니다.

2. 트라이(Trie)의 작동 원리

다음 그림은 문자열 집합 {"apple", "app", "dad", "dream", "age"}를 트라이로 구현한 것입니다.

*트라이(Trie)는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리입니다.

[공통 접두어]

"apple"과 "app"은 "app"라는 공통 접두어가 있으므로 같은 서브 트리에 표시됩니다.

즉, "a"라는 공통 접두어를 가진 "apple", "app", "age"는 Head의 자식 노드 'a'에,

"d"라는 공통 접두어를 가진 "dad", "dream"은 Head의 자식 노드 'd'에 표시됩니다.

[Leaf Node]

리프 노드는 각 단어의 마지막 문자를 의미하므로, 단어의 끝 문자라는 표시(endOfWord)를 해야합니다.

또한 리프 노드의 개수는 단어의 개수를 의미합니다.

[트라이(Trie) 생성 과정]

1. "apple"를 트라이에 삽입

• 'a': 첫번째 문자인 'a'는 초기에 트라이 자료구조 내에 아무것도 없으므로 Head의 자식노드에 'a'를 추가
• 'p': 'a' 노드에도 현재 자식이 하나도 없으므로 'a'의 자식노드에 'p'를 추가
• 'p', 'l', 'e'에 대해서도 자식노드로 추가
• 'l': "apple" 단어가 끝남을 알기 위해 'l' 노드에 마지막 노드(endOfWord)임을 표시

2. "app"를 트라이에 삽입

• 'a': 현재 Head의 자식 노드로 'a'가 이미 존재하기 때문에 'a' 노드를 추가하지 않고 기존에 있는 'a'노드로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동하면서, 'p'노드에 마지막 노드임을 표시

3. "dad", "dream",  "age"를 트라이에 삽입

• "dad"와 "dream"의 첫 문자인 'd'는 Head의 자식 노드로 없기 때문에 추가해서, 각 단어별로 문자를 순차적으로 추가
• "age"는 Head의 자식 노드로 'a'가 있기 때문에,
  • 'a'로 이동 => 'a'의 자식 노드에 'g'가 없으므로 'g'를 추가 => 'e'도 'g'의 자식 노드로 추가한 후 마지막 노드 표시

3. 트라이(Trie) 구현(Java)

그럼 트라이를 Java로 구현하려면 어떻게 해야할까?

기본적으로는 Map Interface를 사용해서 구현합니다.

Map의 Key값에는 단어를 이루는 각각의 문자들이 들어가고, Value에는 자식 노드 클래스를 저장합니다.

이제 순차적으로 자바로 구현을 해보겠습니다.

Node 클래스 생성

Node 클래스는 해당 노드의 자식 노드정보와 단어의 끝인지를 판단하는 변수로 구성합니다.

private class Node {
    HashMap<Character, Node> childNode = new HashMap<>(); // 자식 노드
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
}

트라이(Trie) 자료구조 클래스 생성

기본적으로 루트 노드를 초기화해 줍니다.

*루트 노드는 1) 항상 비어있고 2) 루트노드의 자식 노드는 각 단어의 첫 글자입니다.

public class Trie {
    private Node rootNode;
    Trie() {
        // Trie 생성시 루트 노드는 기본으로 생성
        rootNode = new Node(); // 루트 노드는 빈 노드
    }
}

기본 메서드

1) 노드 추가(insert)

입력 받은 단어를 문자 순대로 트리 계층 구조의 자식 노드로 생성해서 넣습니다.

• 문자가 자식 노드에 존재하면 새로 생성하지 않고 자식 노드로 이동
• 단어의 마지막 문자인 노드라면 endOfWord = true로 설정

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드를 확인
    //  1) 자식 노드에 있는 문자라면 자식 노드를 가져옴
    //  2) 자식 노드에 없는 문자라면 새롭게 생성
    for (int i=0; i<word.length(); i++) node = node.childNode.computeIfAbsent(word.charAt(i), key -> new Node());
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

2) 포함 여부 확인(contains)

특정 단어가 트라이에 존재하는지 확인합니다.

• 루트 노드부터 단어의 문자 순대로 일치하는 자식 노드가 계층을 이루고 있는지 확인
• 단어의 마지막 문자에 endOfWord가 true

두 조건을 만족하는 경우가 트라이에 존재하는 경우입니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        if (!node.childNode.containsKey(c)) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode.get(c); // 마지막 문자를 node에 저장
    }
    return node.endOfWord; // 마지막 문자 여부를 반환
}

3) 노드 삭제(delete)

트라이에 추가했던 단어를 삭제합니다.

• 부모 노드에 대한 정보는 없기 때문에 삭제할 단어의 마지막 문자까지 이동해서 문자를 삭제해와야 합니다. => 재귀
• 다음 문자에 존재하는 자식노드가 있고, 삭제를 시작하는 마지막 노드(리프 노드)에는 endOfWord가 true로 되어있어야 합니다. 
  • 즉, 삭제할 단어가 트라이에 포함되어있어야 합니다.
• 단어 삭제를 위해 마지막 문자 노드인 리프 노드의 endOfWord를 false로 변경합니다. 이후 순차적으로 거꾸로 올라가면서 노드를 삭제합니다. 단, 아래 두 조건이 아닌 경우에만 삭제합니다.
  • 해당 노드의 자식노드가 있는 경우
    • 자식노드가 있다는 뜻은 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.
  • endOfWord가 true인 경우
    • 단어의 끝인 문자인 경우 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
private void delete(Node node, String word, int idx) {
    // 단어의 마지막 인덱스인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    }
    char c = word.charAt(idx); // 현재 확인해야하는 문자
    if (!node.childNode.containsKey(c)) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    Node child = node.childNode.get(c); // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childNode.isEmpty() && !child.endOfWord) node.childNode.remove(c, child);
}

🧪 구현 테스트

public static void main(String[] args) {
        Trie trie = new Trie();
        // insert
        String[] arr = {"apple", "app", "dream", "dad", "age"};
        for (String word: arr) {
            trie.insert(word);
        }
        // delete
        trie.delete("app");
        trie.delete("dream");
        // contains
        System.out.println(trie.contains("apple")); // true
        System.out.println(trie.contains("app")); // 삭제했으므로 false
        System.out.println(trie.contains("age")); // true
        System.out.println(trie.contains("dream")); // 삭제했으므로 false
        System.out.println(trie.contains("dad")); // true
}

위에서 예시로 들었던 문자열 배열을 기준으로 트라이를 생성하고 삭제, 포함여부를 확인하면 아래와 같은 결과를 확인할 수 있습니다.

💡 전체 코드는 아래 링크에서 확인해주세요.

4. 트라이(Trie) 시간 복잡도

총 문자의 개수를 N, 가장 긴 문자열의 길이가 L이라고 할때

• 생성 시간 복잡도: O(N*L)
  • 모든 문자열 N개를 넣어야하고, N개에 대해 트라이에 넣는 건 가장 긴 문자열 길이인 L만큼 걸린다.
  • 삽입은 O(L)만 소요
• 탐색 시간 복잡도: O(L)
  • 트리를 가장 깊게 탐색하는 경우는 가장 긴 문자열 길이인 L까지 들어가는 것이므로 O(L)

5. 트라이(Trie) 장단점

• 문자열에 대한 검색을 빠르게 할 수 있습니다.
  
  • 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나 추가하면 되기 때문에 문자열의 추가와 탐색 모두 O(M)만에 가능합니다.

• 필요로 하는 메모리의 크기가 너무 크다는 단점이 있습니다.
  • 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있기에 저장공간의 크기가 크다는 단점이 있습니다.
  • 문자열이 모두 영소문자로 이루어져 있어도, 자식 노드를 가리키는 26개의 포인터를 저정해야하는데
  • 최악의 경우에는 집합에 포함되는 문자열의 길이의 총 합만큼의 노드가 필요하기 때문에 총 메모리는 O(포인터 크기*포인터 배열 개수*총 노드 개수)가 됩니다.
    • 만약 1,000자리의 문자열이 1,000만개가 있다면 이때, 100만개의 노드가 필요하고 포인터의 크기가 8Byte라 하면 약 200MB의 메모리가 필요합니다.

트라이(Trie) 단점 해결을 위한 방법

'메모리의 크기가 너무 큰' 단점을 해결하기 위해, 보통 map이나 vector를 이용해서 필요한 노드만 메모리를 할당하는 방식을 사용합니다. 그러나 이는 메모리 제한이 타이트한 경우에는 최적화가 까다롭습니다.

또한 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다고 합니다.

6. 트라이(Trie) 코딩테스트 문제

• [백준] - 전설
• [백준] - 전화번호 목록 : 🔗풀이 포스팅

참고한 링크

• [자료구조] 트라이 (Trie)
• [Algorithm] Trie를 Java로 구현해보자!
• [자료구조] 트라이