2026-03-25 TIL (22일차)

C++

pair을 이용하여 vector 선언

vector는 연속된 메모리 공간에 데이터를 저장하는 배열 기반 컨테이너입니다. 여기에 pair를 넣으면, 각 칸마다 두 개의 데이터가 묶인 하나의 쌍이 저장됩니다.

메모리 저장 형태와 특징

• 저장되는 형태: 메모리 상에 (첫 번째 데이터, 두 번째 데이터), (첫 번째 데이터, 두 번째 데이터) 순서로 빈틈없이 배치됩니다.
• 자료형의 자유: first와 second에 서로 다른 자료형을 넣을 수 있습니다. (예: int와 string, float와 bool 등)

    std::vector<std::pair<int, std::string>> userList;

    userList.push_back(std::make_pair(1, "Alice"));
    userList.push_back({2, "Bob"});
    userList.emplace_back(3, "Charlie");
   
    for (int i = 0; i < userList.size(); ++i) {
        // 벡터의 i번째 요소(pair)의 first와 second에 접근
        std::cout << "ID: " << userList[i].first 
                  << ", Name: " << userList[i].second << std::endl;
    }
}

장점

① 연관된 데이터 묶기
서로 관련이 있는 두 데이터를 하나의 리스트로 관리하고 싶을 때 유용합니다.

② 자동 정렬 (Sorting)
std::pair는 기본적으로 비교 연산자가 정의되어 있습니다. std::sort를 사용하면 편하게 정렬할 수 있습니다.

해시 테이블(Hash Table)

해시 테이블(Hash Table)은 컴퓨터 과학에서 데이터를 르게 찾아내기 위해 고안된 ‘키(Key)-값(Value)’ 기반의 자료구조입니다. 쉽게 비유하자면, 수만 권의 책이 꽂힌 도서관에서 책 제목(Key)을 말하자마자 사서가 “그 책은 7번 선반의 3번째 칸에 있습니다”라고 단번에 알려주는 안내 시스템과 같습니다.

해시 테이블의 상세 정의 및 핵심 구성 요소

해시 테이블은 해시 함수(Hash Function)를 사용하여 키를 특정 Index으로 변환하고, 이 Index을 주소 삼아 데이터를 저장하는 배열 형태의 자료구조입니다.

• 키(Key): 데이터를 찾기 위한 고유한 식별자 (예: 유저 닉네임, 학번).
• 해시 함수(Hash Function): 임의의 길이를 가진 키를 고정된 크기의 숫자(Index)로 바꿔주는 수학적 연산입니다.
• 해시 값(Hash Value/Code): 해시 함수의 결과물로 나온 숫자입니다. 이 숫자가 배열의 Index가 됩니다.
• 버킷(Bucket/Slot): 데이터가 저장되는 각각의 공간입니다.

해시 테이블의 특징

해시 테이블이 다른 자료구조(배열, 리스트, 트리)와 구별되는 특징은 탐색의 효율성입니다.

• 상수 시간 탐색 ($O(1)$): 일반 배열은 처음부터 끝까지 훑어야 하지만($O(N)$), 해시 테이블은 키를 함수에 넣는 즉시 주소가 나오므로 데이터 양과 무관하게 거의 즉시 찾아냅니다.
• 공간과 시간의 교환: 빠른 속도를 얻는 대신, 데이터를 띄엄띄엄 저장하므로 메모리 공간을 상대적으로 더 많이 차지합니다.

해시 충돌(Collision)

해시 테이블의 단점은 서로 다른 두 키가 해시 함수를 거쳤는데 똑같은 방 번호(Index)가 나오는 ‘해시 충돌’입니다. 이 현상이 발생하는 이유는 다음과 같습니다.

1. 비둘기집 원리 (Pigeonhole Principle)
   • 입력될 수 있는 키(Key)의 종류는 무한대(예: 세상의 모든 문자열 조합)에 가깝지만, 해시 테이블의 방(Bucket) 개수는 컴퓨터의 한정된 메모리 때문에 유한합니다.
   • 10개의 비둘기집에 11마리의 비둘기를 넣으려면 반드시 한 집에는 2마리 이상이 들어가야 하듯, 무한한 키를 유한한 배열 인덱스로 압축하다 보면 필연적으로 겹치는 주소가 생깁니다.
2. 해시 함수의 한계
   • 어떤 키가 들어와도 완벽하게 100% 다른 주소로 분산시켜주는 ‘완벽한 해시 함수’를 만드는 것은 현실적으로 불가능하거나 연산 비용이 너무 큽니다. 따라서 효율성을 위해 적당히 빠르고 잘 분산되는 함수를 쓰다 보면 우연히 같은 값이 계산될 확률이 존재합니다.

충돌 해결 방법

• 체이닝 (Chaining): 충돌이 난 방 안에 연결 리스트(Linked List)를 만들어 데이터를 줄 세우는 방식.
• 개방 주소법 (Open Addressing): 충돌이 나면 규칙에 따라 비어있는 옆 방을 찾아 들어가는 방식.

활용 예시

• ① 데이터베이스 인덱싱: 수백만 명의 회원 정보 중 ‘ID’ 하나로 특정 회원을 즉시 찾아야 할 때 사용합니다. 로그인 시 비밀번호 대조 과정에서도 쓰입니다.
• ② 컴파일러의 심볼 테이블: 코드 안의 수많은 변수 이름과 함수 이름을 메모리 주소와 연결해 줘야 할 때 사용합니다.
• ③ 캐싱 (Caching): 웹 브라우저나 서버가 연산 결과를 저장해 두었다가, ‘URL’이나 ‘검색어’를 키로 하여 데이터를 빠르게 다시 가져올 때 사용합니다.
• ④ 게임 개발 (Object Lookup): 수만 개의 아이템 중 특정 고유 번호(UID)를 가진 객체를 즉시 찾아 로직을 실행해야 할 때 필수적입니다. (std::unordered_map)

요약 해시 테이블은 무엇(Key)을 넣으면 어디(Index)에 있는지 바로 계산해 내는 자료구조입니다. 데이터가 정렬되어 있을 필요가 없고, 오직 찾는 속도($O(1)$)가 생명인 시스템 입니다.