LV03 Direct Adressing Table, Hash Table, 패턴찾기

C++ 패턴 매칭과 해시 테이블

패턴찾기 (Pattern Matching)

패턴 매칭의 기본 개념

패턴 매칭은 긴 문자열에서 특정 패턴(부분 문자열)을 찾는 알고리즘입니다. Flag 써서 찾거나, 함수를 만들어서 찾습니다.

기본적인 패턴 찾기 구현

#include <iostream>
using namespace std;

char vect[12] = "BTABCQABCQAB";
char pattern[4] = "ABC";

bool IsPattern(int startIdx)
{
    for (size_t i = 0; i < 3; i++)
    {
        if (pattern[i] != vect[startIdx + i])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    for (size_t i = 0; i < 7; i++)
    {
        if (IsPattern(i) == true)
        {
            cout << "Pattern found at index: " << i << endl;
            break;
        }
    }

    return 0;
}
C++
복사

알고리즘 동작:

시작 위치 설정: 원본 문자열의 각 위치에서 시작

패턴 비교: 패턴의 각 문자와 원본 문자열 비교

일치 확인: 모든 문자가 일치하면 패턴 발견

결과 반환: 첫 번째 일치 위치 반환 또는 계속 검색

2차원 배열에서의 패턴 찾기

2차원 배열에서도 패턴을 찾을 수 있습니다.

#include <iostream>
using namespace std;

int vect[6][3] =
{
    3, 5, 1,
    2, 4, 5,
    3, 6, 1,
    3, 1, 1,
    4, 5, 6,
    2, 4, 5
};

int pattern[3] = { 2, 4, 5 };

int IsPattern(int line)
{
    for (int x = 0; x < 3; x++)
    {
        if (pattern[x] != vect[line][x])
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int result;

    for (int y = 0; y <= 5; y++)
    {
        result = IsPattern(y);
        if (result == 1) break;
    }

    if (result == 1)
    {
        cout << "발견" << endl;
    }
    else
    {
        cout << "미발견" << endl;
    }

    return 0;
}
C++
복사

일반적인 2차원 패턴 찾기

#include <iostream>
using namespace std;

int vect[3][5] =
{
    1, 2, 3, 4, 1,
    3, 1, 0, 0, 1,
    2, 3, 4, 1, 2
};

int pattern[3] = { 3, 4, 1 };

bool IsPattern(int dy, int dx)
{
    for (size_t i = 0; i < 3; i++)
    {
        if (pattern[i] != vect[dy][dx + i])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    bool ret = false;

    for (int y = 0; y < 3; y++)
    {
        for (size_t x = 0; x < 3; x++)
        {
            ret = IsPattern(y, x);
            if (ret)
            {
                break;
            }
        }
    }

    if (ret == true)
    {
        // 존재
    }
    else
    {
        // 존재하지 않음
    }

    return 0;
}
C++
복사

패턴이 게임에서 활용되는 예시의 대표적으로 스타듀밸리가 있다.

패턴 매칭은 게임에서 다양하게 활용됩니다:

•

아이템 조합: 특정 패턴의 아이템 배치로 새로운 아이템 생성

•

퍼즐 게임: 특정 패턴 완성시 점수 획득

•

지형 생성: 특정 패턴에 따른 맵 생성

해시 테이블 (Hash Table)

해시 테이블의 개념

해시 테이블이란 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말합니다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있습니다.

Direct Address Table (직접 주소 테이블)

Direct Address Table은 먼저 가장 간단한 형태의 해시테이블로 이름 그대로 키 값을 주소(인덱스)로 사용하는 테이블을 말합니다. 이는 키 값이 100이라고 했을 때 배열의 인덱스 100에 원하는 데이터를 저장하는 것입니다.

#include <iostream>
using namespace std;

int main()
{
    int bucket[256] = {};

    char str[7] = "ADBFAD";
    for (int i = 0; i < 6; i++)
    {
        bucket[str[i]]++; // str[i](아스키코드)값 자체를 index로 활용
    }

    return 0;
}
C++
복사

Direct Address Table의 특징:

•

빠른 접근: O(1) 시간 복잡도

•

메모리 낭비: 사용하지 않는 인덱스도 메모리 할당

•

키 범위 제한: 키 값이 배열 크기를 초과할 수 없음

Hash Table - DAT(Direct Addressing Table)

#include <iostream>
using namespace std;

int main()
{
    // DAT(Direct Addressing Table) - Hash Table
    // 값 자체를 index로 활용해서 사용하겠다.
    // 너무한 크기의 배열을 선언
    int bucket[256] = {};
    char target = 'A';
    // 'A'의 아스키코드는 65
    // bucket 배열의 65번째에 1을 대입
    bucket[target] = 1;

    return 0;
}
C++
복사

해시 함수와 해시 테이블 구조

해시 함수 H(x) = [x %10]을 사용한 예제:

Hashing Data Structure
List = [11, 12, 13, 14, 15]
H(x) = [x %10]

11%10 → 1    12%10 → 2    13%10 → 3    14%10 → 4    15%10 → 5

Hash Table: [0] [1] [2] [3] [4] [5]
              □  11  12  13  14  15
Plain Text
복사

해시함수를 사용하여 특정 해시값을 얻어내고 그 해시값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조이다. 충돌에 대해서 이해하기 위해선 먼저 **적재율(Load Factor)**에 대해서 이해해야 한다.

•

*충돌(Collision)**이다. 충돌에 대해서 이해하기 위해선 먼저 적재율 **적재율(Load Factor)**에 대해서 이해해야 한다.

적재율이란 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉, 키의 개수를 k, 해시 테이블의 크기를 N이라고 했을 때 적재율은 k/N이다. Direct Addressing을 사용하는 경우이며 이때 적재율이 1을 초과할 해시 테이블의 경우 반드시 충돌이 발생하게 된다.

만약, 충돌이 발생하지 않는다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 수행되지만 충돌이 발생할 경우 정우 탐색하는 시간 이상의 시간이 소요될 것이다. 이는 같은 인덱스에 모든 키 값과 데이터가 저장된 경우로 충돌을 진부 발생했을 말한다. 따라서, 충돌을 최대한으로 줄여서 연습속도를 빠르게 하는 것이 해시 함수를 구성하는 해시 알고리즘의 핵심인데 이에 중요하게 작용하는 것이 바로 해시함수를 구성하는 해시 알고리즘이다. 해시 알고리즘의 견고하지 못하게 되면 해시함수 도출된 값들이 같은 경우가 빈번하게 발생하게 되므로 충돌을 이어지게 되는 것이다.

해시 테이블 활용 예제

배열에 존재하는 알파벳 갯수 찾기

#include <iostream>
using namespace std;

int main()
{
    // 넉넉한 크기의 배열을 선언
    int bucket[256] = {};
    char str[7] = "ADBFAD";

    for (int i = 0; i < 6; i++)
    {
        // 아스키코드 자체를 인덱스로 사용
        // 알파벳 갯수를 카운트
        int idx = str[i];
        bucket[idx]++;
    }

    // for문을 사용해서 하나하나 count하지 좋지 않다.
    int count = 0;
    for (int i = 'A'; i <= 'Z'; i++)
    {
        cout << (char)i << " : " << bucket[i] << endl;
    }

    return 0;
}
C++
복사

배열에 존재하는 알파벳의 종류와 각 갯수 출력

#include <iostream>
using namespace std;

int main()
{
    // 넉넉한 크기의 배열을 선언
    int bucket[256] = {};
    char str[7] = "ADBFAD";

    for (size_t i = 0; i < 6; i++)
    {
        // 아스키코드 자체를 인덱스로 사용
        // 알파벳 갯수를 카운트
        bucket[str[i]]++;
    }

    for (size_t x = 0; x < 256; x++)
    {
        // 알파벳이 존재한다면
        if (bucket[x] != 0)
        {
            // 사용된 알파벳의 종류가 출력된다.
            // 사용된 알파벳의 종류 및 갯수도 함께 출력한다.
            cout << (char)x << " : " << bucket[x] << "\n";
        }
    }

    return 0;
}
C++
복사

배열의 글자를 순서대로 정렬하여 출력

버블정렬, 선택정렬보다 훨씬 간단하다.

#include <iostream>
using namespace std;

int main()
{
    // 넉넉한 크기의 배열을 선언
    int bucket[256] = {};
    char str[7] = "ADBFAD";

    for (size_t i = 0; i < 6; i++)
    {
        // 아스키코드 자체를 인덱스로 사용
        // 알파벳 갯수를 카운트
        bucket[str[i]]++;
    }

    for (size_t x = 0; x < 256; x++)
    {
        // 알파벳이 존재한다면
        if (bucket[x] != 0)
        {
            // 사용된 알파벳을 정렬하여 출력
            for (size_t i = 0; i < bucket[x]; i++)
            {
                cout << (char)x;
            }
        }
    }

    return 0;
}
C++
복사

출력 결과: AABDDF (알파벳 순으로 정렬됨)

패턴 찾기 심화

개선된 패턴 찾기 함수

#include <iostream>
using namespace std;

char vect[10] = "BTABCQABC";
char pattern[4] = "ABC";

// 문자열 끝 표시를 위해 널 문자 '\0'을 고려해야 하지만 여기서 생략하고 학습목적 하기 때문에
// 마지막 문자인 '\0' null 문자의 자리까지 고려해서 문자열 배열의 사이즈를 선언한다.
// char pattern[4] = "ABC\n" 이런 것을 가진 것이다.

int IsPattern(int idx)
{
    for (size_t i = 0; i < 3; i++)
    {
        if (pattern[i] != vect[idx + i])
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    // 패턴찾기 (찾는 이후)
    int result = 0;
    for (size_t i = 0; i < 7; i++)
    {
        result = IsPattern(i);
        if (result == 1)
        {
            break;
        }
    }

    if (result == 0)
    {
        cout << "발견" << endl;
    }
    else
    {
        cout << "미발견" << endl;
    }

    return 0;
}
C++
복사

해시 테이블의 장단점

장점

빠른 검색: 평균 O(1) 시간 복잡도

효율적인 삽입/삭제: O(1) 시간 복잡도

유연한 키 타입: 해시 함수만 정의하면 다양한 타입 사용 가능

단점

메모리 사용량: 충분한 크기의 배열 필요

충돌 처리: 해시 충돌 발생 시 성능 저하

순서 보장 없음: 저장 순서와 출력 순서가 다름

실무 활용 분야

1. 캐싱 시스템

•

웹 브라우저 캐시

•

CPU 캐시

•

데이터베이스 버퍼

2. 데이터베이스 인덱싱

•

빠른 레코드 검색

•

중복 제거

3. 프로그래밍 언어

•

Python의 딕셔너리

•

Java의 HashMap

•

C++의 unordered_map

4. 게임 개발

•

플레이어 정보 관리

•

아이템 인벤토리

•

스킬 쿨다운 관리

해시 테이블은 빠른 검색과 효율적인 데이터 관리가 필요한 모든 영역에서 핵심적으로 활용되는 자료구조입니다.

“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”

혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.

•

강의는 다 들었지만 막상 손이 안 움직이고,

•

복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,

•

질문할 곳도 없고,

•

유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.

문제는 ‘연습’이 빠졌기 때문입니다.

단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.

실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.

그래서, 얌얌코딩 코칭은 다릅니다.

그냥 가르치지 않습니다.

스스로 설계하고, 코딩할 수 있게 만듭니다.

얌얌코딩 코칭에서는 단순한 예제가 아닌,

스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.

이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:

•

문제를 스스로 쪼개고 설계하는 힘

•

다양한 조건을 만족시키는 실제 구현 능력

•

기능 단위가 아닌, 프로그램 단위로 사고하는 습관

•

마침내 자신의 힘으로 코드를 끝까지 작성하는 경험

지금 필요한 건 더 많은 강의가 아닙니다.

코드를 스스로 완성해 나가는 훈련,

그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.

자세한 안내 보기: 프리미엄 코칭 안내 바로가기

또는 카카오톡 상담방: 얌얌코딩 상담방