ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

728x90
๋ฐ˜์‘ํ˜•
Trie๋ฅผ ๊ฐœ๋…๋งŒ ์•Œ๊ณ , ์ƒ๊ฐํ•ด๋ณด๋‹ˆ ์ง์ ‘ ๊ตฌํ˜„ํ•ด๋ณธ ์ ์ด ์—†์—ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด๋ฅผ ํ•  ๋•Œ, ์š”๊ธดํ•˜๊ฒŒ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•œ ๋ชฉ์ ์œผ๋กœ ์ •๋ฆฌํ•ด๋ณด๊ณ ์ž ํ•œ๋‹ค. ๋‹ค๋ฅธ ๊ณณ์—์„œ ๊ฒ€์ƒ‰ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ๊ณผ ๊ฐ™์ด ๋™์ ์œผ๋กœ ํ• ๋‹นํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹Œ, ๋ฌธ์ œ์˜ ์กฐ๊ฑด์— ๋งž๊ฒŒ ์ •์ ์œผ๋กœ Trie๋ฅผ ํ• ๋‹นํ•ด๋‘๊ณ , ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ์‹์„ ๋‹ค๋ฃจ๊ณ ์ž ํ•œ๋‹ค.

 

Trie?

 

ํŠธ๋ผ์ด (์ปดํ“จํŒ…) - ์œ„ํ‚ค๋ฐฑ๊ณผ, ์šฐ๋ฆฌ ๋ชจ๋‘์˜ ๋ฐฑ๊ณผ์‚ฌ์ „

"A", "to", "tea", "ted", "ten", "i", "in", "inn"๋ฅผ ํ‚ค๋กœ ๋‘” ํŠธ๋ผ์ด. ์ด ์˜ˆ์ œ์—๋Š” ๋ชจ๋“  ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์•ŒํŒŒ๋ฒณ ์ˆœ์œผ๋กœ ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ์ง€๋Š” ์•Š๋‹ค. (๋ฃจํŠธ ๋…ธ๋“œ์™€ 't' ๋…ธ๋“œ) ํŠธ๋ผ์ด(trie)๋Š” ์ปดํ“จํ„ฐ

ko.wikipedia.org

 Trie๋ž€ root๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ฌธ์ž์—ด์„ ์ €์žฅํ• ๋•Œ, ๊ฐ ๋…ธ๋“œ์— ์–ด๋–ค ๋ฌธ์ž๊ฐ€ ์กด์žฌํ•˜๋Š”์ง€ ๊ฐœ์ˆ˜๋Š” ๋ช‡ ๊ฐœ์ธ์ง€ ํšจ์œจ์ ์œผ๋กœ ์ฐพ์„ ์ˆ˜ ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์—์„œ ๋‹ค๋ฃจ๋Š” ๊ฒƒ์€ ๊ฐ ๋…ธ๋“œ๋งˆ๋‹ค ์ตœ๋Œ€ 26๊ฐœ์˜ ์•ŒํŒŒ๋ฒณ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ๋•Œ, ์ด๋ฅผ ๊ตฌ์„ฑํ•˜์—ฌ ํ•ด๊ฒฐํ•˜๋Š” ๋ฌธ์ œ๋“ค์ด ์ฃผ๋ฅผ ์ด๋ฃฌ๋‹ค.

 

๊ตฌ์กฐ์ฒด ์ •์˜

#define MAX_TRIE    200

struct Trie {
    Trie* child[26];
    int cnt;
}Tries[MAX_TRIE], *root;

 ๋™์ ์œผ๋กœ ํ• ๋‹นํ•œ๋‹ค๋ฉด, Constructor(`Trie()`)์™€ Destructor(`~Trie()`)๋ฅผ ํ™œ์šฉํ•˜์—ฌ์•ผ ํ•œ๋‹ค. ํ•˜์ง€๋งŒ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ๋™์ ์œผ๋กœ ํ• ๋‹น, ํ•ด์ œํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค๋Š” ์ •์ ์œผ๋กœ ๋ฌธ์ œ์— ํ•„์š”ํ•œ ์ตœ๋Œ€ ํฌ๊ธฐ๋งŒํผ ์ •์˜(`์ตœ๋Œ€ ๋‹จ์–ด ๊ธธ์ด * ์ตœ๋Œ€ ๋‹จ์–ด ๊ฐœ์ˆ˜`)ํ•ด๋‘๊ณ  ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ๋ณด๋‹ค ํšจ์œจ์ ์ด๋‹ค.

 

ํ•จ์ˆ˜ ์ •์˜

newTrie()

int numOfWord;

Trie* newTrie() {
    Trie* newNode = &Tries[numOfWord++];
    memset(newNode, 0, sizeof(Trie));
    return newNode;
}

 ํ•ด๋‹น ํ•จ์ˆ˜๋Š” ๋ง๊ทธ๋Œ€๋กœ, ์ƒˆ๋กœ์šด ๋‹จ์–ด๊ฐ€ ์ถ”๊ฐ€๋  ๋•Œ, ์ •์ ์œผ๋กœ ์ƒ์„  ๋œ Trie ๊ตฌ์กฐ์ฒด๋ฅผ ์ƒˆ๋กœ์šด ๋‹จ์–ด๊ฐ€ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•ด์ฃผ๋Š” ๊ฒƒ์ด๋‹ค.

 

add

int add(char str[]) {
    Trie* node = root;

    for (int i = 0; str[i]; i++) {
        int nextAlpha = str[i] - 'a';
        if (!node->child[nextAlpha])
            node->child[nextAlpha] = newTrie();
        node = node->child[nextAlpha];
    }
    return ++node->cnt;
}

 ๋‹จ์–ด๊ฐ€ ์ถ”๊ฐ€๋˜๋ฉด, root๋กœ ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ํ•ด๋‹น ๋‹จ์–ด์˜ ๋…ธ๋“œ๋“ค์„ ์ถ”๊ฐ€ํ•ด์ฃผ๊ณ , ์ž…๋ ฅ๋œ ๋ฌธ์ž์—ด์ด ์กด์žฌํ•  ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ ๋‹ค์Œ ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ์—๋Š” ํ•ด๋‹น ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜๋ฅผ ์นด์šดํŠธํ•˜๊ธฐ ์œ„ํ•ด, `++node->cnt`๋ฅผ ํ•˜๊ณ  ๋ฐ˜ํ™˜ํ•ด์ค€๋‹ค.

 

search

int find(Trie* cur, char str[]) {
    for (int i = 0; str[i]; i++) {
        int nextAlpha = str[i] - 'a';

        if (!cur->child[nextAlpha])
            return 0;

        cur = cur->child[nextAlpha];
    }
    return cur->cnt;
}

int search(char str[]) {
    return find(root, str);
}

 ํŠน์ • ๋‹จ์–ด๊ฐ€ ๋ช‡๊ฐœ๊ฐ€ ์žˆ๋Š”์ง€ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์œ„์™€ ๊ฐ™๋‹ค. ์ถ”๊ฐ€ํ•˜๋Š” ๋ฐฉ๋ฒ•๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ, ๋‹จ์–ด์˜ ์•ŒํŒŒ๋ฒณ๋ณ„๋กœ ๋…ธ๋“œ๋ฅผ ํ™•์ธํ•œ๋‹ค. for ๋ฌธ์ด ์ข…๋ฃŒ๋˜๊ธฐ ์ „ (๋‹จ์–ด์˜ ๋๊นŒ์ง€ ํƒ์ƒ‰ํ•˜์ง€ ๋ชปํ•œ ๊ฒฝ์šฐ)์— ๋‹ค์Œ ์•ŒํŒŒ๋ฒณ์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ์—†๋Š” ๋‹จ์–ด์ด๋‹ค.

 

ํ•œ ๋‹จ๊ณ„ ๋‚˜์•„๊ฐ€๊ธฐ

์™€์ผ๋“œ ์นด๋“œ๊ฐ€ ํฌํ•จ๋œ ๋‹จ์–ด ๊ฒ€์ƒ‰

int find(Trie* cur, int next, char str[]) {
    int wordCnt = 0;
    for (int i = next; str[i]; i++) {
        if (str[i] == '*' || str[i] == '?') {
            // ์™€์ผ๋“œ ์นด๋“œ๋ฉด dfs์ฒ˜๋Ÿผ ๊ฐ€์ง€๋ฅผ ๋ป—์–ด๋‚˜๊ฐ€๋ฉด์„œ ํƒ์ƒ‰.
            for (int j = 0; j < 26; j++) {
                if (cur->child[j])
                    wordCnt += find(cur->child[j], i + 1, str);
            }
            return wordCnt;
        }
        // ์™€์ผ๋“œ ์นด๋“œ ์•„๋‹ˆ๋ฉด, ํ•ด๋‹น ๋‹จ์–ด๋งŒ ํƒ์ƒ‰.
        else {
            int nextAlpha = str[i] - 'a';

            if (!cur->child[nextAlpha])
                return 0;

            cur = cur->child[nextAlpha];
        }
    }

    return cur->cnt;
}

 ๋ฌธ์ œ์— ๋”ฐ๋ผ `*`, `?`๊ฐ€ ํฌํ•จ๋œ ๋‹จ์–ด๋ฅผ ๊ฒ€์ƒ‰ํ•˜๋ผ๋Š” ๊ฒฝ์šฐ๊ฐ€ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, `ba*an*` ์ด๋Ÿฐ ์‹์˜ ๋‹จ์–ด๋“ค์ด๋‹ค. ํ•ด๋‹น ๋‹จ์–ด๋“ค์€ `*`, `?` ์ž๋ฆฌ์— ์–ด๋– ํ•œ ์•ŒํŒŒ๋ฒณ์ด ์™€๋„ ์ƒ๊ด€์—†๋‹ค. ๋”ฐ๋ผ์„œ ์œ„์˜ ๊ฒ€์ƒ‰์—์„œ DFS๋ฅผ ํ†ตํ•ด ๋ชจ๋“  ์•ŒํŒŒ๋ฒณ์„ ๊ฒ€์ƒ‰ํ•ด์ฃผ๋Š” ๋ถ€๋ถ„๋งŒ ์ถ”๊ฐ€ํ•˜๋ฉด ๋œ๋‹ค.

 

728x90
๋ฐ˜์‘ํ˜•
๋Œ“๊ธ€
๊ธ€ ๋ณด๊ด€ํ•จ
์ตœ๊ทผ์— ์˜ฌ๋ผ์˜จ ๊ธ€
์ตœ๊ทผ์— ๋‹ฌ๋ฆฐ ๋Œ“๊ธ€