[C/Python] 알고리즘 (해시)

💡 1. 존재 유무와 빈도수 체크 (완주하지 못한 선수, 폰켓몬)

가장 기본적인 해시의 용도입니다. 특정 데이터가 '몇 번 등장했는지' 혹은 '존재하는지'를 파악합니다.

• C++의 무기: unordered_map과 unordered_set
  • C++의 map은 존재하지 않는 키에 접근해 map[key]++를 해도 자동으로 0으로 초기화해 주는 마법 같은 편리함을 제공합니다.
  • 빈도수(Count)가 필요 없고 오직 '종류(중복 제거)'만 필요하다면, 메모리와 속도 최적화를 위해 unordered_set을 사용하는 것이 정석입니다.
• Python의 무기: collections.Counter
  • 파이썬 딕셔너리에서 없는 키를 조회하면 KeyError가 발생하므로 in 키워드로 검사해야 합니다.
  • 하지만 Counter 객체를 사용하면 단 한 줄로 빈도수를 세고, 심지어 딕셔너리끼리 뺄셈(-) 연산까지 가능한 엄청난 퍼포먼스를 보여줍니다.

💡 2. 접두어와 빠른 탐색 (전화번호 목록)

문자열 배열에서 특정 문자열이 다른 문자열의 부분에 포함되는지 찾는 문제입니다.

• 해시(Hash)적 접근: 모든 번호를 해시에 넣고, 각 번호의 문자열을 한 글자씩 잘라가며 해시 맵에 존재하는지 검색합니다. 해시 탐색이 O(1)이기에 가능한 O(N) 알고리즘입니다.
• 정렬(Sort)적 접근: 해시 문제지만 **사전순 정렬(Lexicographical Sort)**을 이용하면 더 직관적으로 풀립니다. 정렬 후 바로 뒤의 원소와만 비교(O(N log N))하면 이중 루프를 피할 수 있습니다. 파이썬은 .startswith()를, C++은 substr()이나 find() == 0을 활용합니다.

💡 3. 해시와 수학의 결합 (의상)

해시는 결국 데이터를 수학적으로 다루기 위한 '전처리 도구'일 뿐이라는 것을 보여주는 문제입니다.

• 경우의 수 공식: 옷의 종류별로 묶은 뒤, (A종류 개수 + 1) * (B종류 개수 + 1) ... - 1 이라는 공식을 도출해 내는 것이 핵심입니다. 여기서 + 1은 해당 부위의 옷을 입지 않는 경우를 의미하며, 마지막 - 1은 모두 입지 않은 벌거벗은 상태를 제외하는 것입니다.
• 백트래킹으로 모든 조합을 찾으려 하면 시간 초과가 발생하므로, 수학적 접근이 필수입니다.

💡 4. 다중 조건 정렬과 중첩 구조 (베스트앨범)

해시 파트의 최종 보스이자, 현업에서 가장 많이 쓰이는 복잡한 데이터 핸들링 문제입니다.

• C++의 커스텀 정렬:
  • unordered_map은 정렬이 불가능하므로, 정렬을 위해서는 반드시 vector로 데이터를 옮겨야 합니다.
  • sort() 함수에 람다(Lambda)식이나 커스텀 비교 함수(compare)를 넘겨주어, 조건에 따라 true를 반환하도록 설계합니다.
• Python의 우아함 (defaultdict, zip):
  • collections.defaultdict(list)를 사용하면 초기화 에러 없이 즉시 리스트(append)와 정수형 카운팅 연산이 가능합니다.
  • 파이썬 람다 정렬의 꽃인 **음수 트릭(lambda x: (-x[0], x[1]))**을 사용하면 첫 번째 조건은 내림차순, 두 번째 조건은 오름차순으로 단 한 줄에 다중 조건 정렬을 완성할 수 있습니다.