C++ 코딩테스트 강좌, 사전 찾기

안녕하세요! 오늘은 C++을 이용한 알고리즘 문제를 하나 해결해보는 시간을 가지겠습니다. 이번 주제는 “사전 찾기”입니다. 이 문제는 주어진 단어 목록에서 특정 단어를 찾는 과정을 다루고 있습니다. 이와 관련된 알고리즘을 함께 살펴보면서, 어떻게 효율적으로 문제를 해결할 수 있는지 알아보겠습니다.

문제 설명

주어진 문제는 다음과 같습니다.

    문제: 사전에서 단어 찾기
    - n개의 단어로 이루어진 사전이 주어집니다.
    - 입력으로 검색할 단어가 주어질 때, 이 단어가 사전에 존재하는지 확인하는 프로그램을 작성하세요.
    
    입력:
    - 첫 번째 줄에 단어의 개수 n(1 ≤ n ≤ 100,000)이 주어집니다.
    - 다음 n개의 줄에 각각 알파벳 소문자로 구성된 단어가 주어집니다.
    - 마지막 줄에 검색할 단어가 주어집니다.
    
    출력:
    - 검색할 단어가 사전에 존재하면 'YES', 그렇지 않으면 'NO'를 출력합니다.

문제의 분석

이 문제는 단순한 문자열 검색 문제로, 사전에서 단어를 찾는 것입니다. 따라서 해결해야 할 주요 포인트는 효율적인 검색 방법입니다. 주어진 단어의 수가 최대 100,000개에 달하기 때문에, 비효율적인 방법으로는 시간 초과가 발생할 수 있습니다.

가장 간단한 방법은 리스트를 이용해 모든 단어를 순회하며 값을 비교하는 것이지만, 이 방법은 시간 복잡도가 O(n)으로, 최악의 경우 최적의 성능을 요구하는 경량 검색엔진에서는 비효율적입니다. 그러므로 해시맵을 이용한 방법이 필요합니다. 해시맵을 사용하면 평균적으로 O(1)의 시간 복잡도로 검색이 가능해지기 때문입니다.

구현 방법

이제 본격적으로 문제를 해결하기 위해 C++로 코드를 작성해보겠습니다. 아래의 절차로 진행합니다:

단어의 개수를 입력받습니다.
단어들을 저장하기 위해 unordered_map을 사용하여 해시맵을 구성합니다.
사전에 있는 단어를 해시맵에 추가합니다.
검색할 단어를 입력받고 해시맵에서 해당 단어의 존재 여부를 확인합니다.

코드 구현

    
    #include 
    #include 
    #include 

    using namespace std;

    int main() {
        int n;
        cin >> n; // 단어 개수 입력
        unordered_map dictionary; // 해시맵 초기화

        // 단어 입력
        for (int i = 0; i < n; i++) {
            string word;
            cin >> word;
            dictionary[word] = true; // 단어를 해시맵에 추가
        }

        string searchWord;
        cin >> searchWord; // 검색할 단어 입력

        // 단어 존재 여부 확인
        if (dictionary.find(searchWord) != dictionary.end()) {
            cout << "YES" << endl; // 존재할 경우
        } else {
            cout << "NO" << endl; // 존재하지 않을 경우
        }

        return 0;
    }

코드 설명

코드를 간단히 설명하겠습니다.

#include <iostream>: C++에서 입력과 출력을 위한 라이브러리를 포함합니다.
#include <unordered_map>: 해시맵을 사용하기 위한 라이브러리입니다. 이로 인해 O(1)의 시간 복잡도로 검색할 수 있습니다.
#include <string>: 문자열을 다루기 위한 라이브러리입니다.
unordered_map dictionary;: 단어를 저장할 해시맵을 선언합니다.
cin >> n;: 단어의 개수를 입력받습니다.
dictionary[word] = true;: 입력받은 단어를 해시맵에 추가합니다. 해시맵의 키는 단어, 값은 true로 설정합니다.
dictionary.find(searchWord): 검색어를 해시맵에서 찾아 존재 여부를 확인합니다.

테스트 및 결과

이제 실제로 이 코드를 테스트해 보겠습니다. 예를 들어, 다음과 같은 입력을 해보겠습니다:

    5
    apple
    banana
    cherry
    date
    elderberry
    banana

위와 같이 입력하면 출력 결과는 다음과 같습니다:

YES

또 다른 예를 생각해 볼 수 있습니다:

    5
    apple
    banana
    cherry
    date
    elderberry
    fig

이 경우 출력 결과는 다음과 같습니다:

NO

복잡도 분석

이 알고리즘의 시간 복잡도는 다음과 같습니다:

단어 삽입: O(1) (평균적으로, 해시맵의 특성에 따라)
단어 검색: O(1) (마찬가지로 평균적으로)

따라서 전체 시간 복잡도는 O(n)입니다. 공간 복잡도는 해시맵에 저장된 단어의 개수에 따라 O(n)입니다.

결론

오늘은 C++을 사용하여 사전에서 단어를 찾는 문제를 해결하는 방법을 알아보았습니다. 해시맵을 이용한 접근 방식이 시간 복잡도를 크게 개선할 수 있음을 보여주었습니다. 알고리즘 문제는 항상 다양한 방법으로 접근할 수 있으니, 여러 가지 방법을 시도해 보시길 바랍니다!