[코딩 테스트 합격자 되기] 해시 – 3. 해시 몸풀기 문제

이 글은 〈[되기] 코딩 테스트 합격자 되기(파이썬 편)〉에서 발췌했습니다.

골든래빗 출판사

박경록 지음

해시의 원리를 이해하고 문제에서 요구하는 해시 함수를 구현할 수 있습니다.

3편은 해시 몸풀기 문제 2개입니다.

총 3편으로 준비했습니다.

1. 해시의 개념

2. 해시 함수와 충돌 처리

3. 해시 몸풀기 문제

문제 01 두 개의 수로 특정값 만들기 ⭐️

저자 권장 시간: 30분

권장 시간 복잡조: O(N+K)

출제: 저자 출제

Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/18.py

n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True, 없으면 False를 반환하는 solution( ) 함수를 작성하세요.

제약 조건

n은 2 이상 10,000 이하의 자연수입니다.

arr의 각 원소는 1 이상 10,000 이하의 자연수입니다.

arr의 원소 중 중복되는 원소는 없습니다.

target은 1 이상 20,000 이하의 자연수입니다.

입출력의 예

문제 분석하고 풀기

arr에서 특정 원소 두 개를 뽑아 두 수의 합이 target과 같을 수 있는지 확인하는 문제입니다. 첫 번째 입출력을 보겠습니다. arr이 [1, 2, 3, 4, 8]이고 target이 6입니다. 여기서는 두 가지 방법을 알아볼 겁니다. 첫 번째 방법은 무작정 가능한 모든 경우의 합을 확인하고, 두 수의 합이 되는지 확인하는 방법입니다. 두 번째 방법은 해시를 활용하는 방법입니다.

무작정 더하며 찾기

가장 간단한 방법은 각 원소에 대해 자신을 제외한 나머지 원소를 전부 더하면서 두 수의 합이 6인 경우를 찾는 겁니다. 이렇게 하면 정답은 당연히 나오겠지만 시간 복잡도는 O(N2)이므로 데이터가 최대 10,000개까지 들어오는 것을 가정하면 대략 1억 번의 연산이 수행될 수 있으므로 효율이 떨어집니다. 뭔가 개선이 필요합니다.

해시를 활용해 찾기

어떻게 개선할 수 있을까요? 코드를 구현하기 전에 별 아이디어가 떠오르지 않다면 직접 이 문제를 풀어보는 것도 방법입니다. 만약 여러분이 이 문제를 직접 푼다면 하나의 숫자를 고른 다음 그 숫자를 더했을 때 target이 되는 수가 arr에 있는지 확인해볼 겁니다. 그러니 다음과 같은 관점으로 문제에 접근할 수도 있을 겁니다.

“arr에서 임의의 원소 x에 대해 x + k = target이 되는 원소 k가 arr에 있는지 확인하기”

여기서 핵심은 k를 확인하는 동작의 효율입니다. 문제에서는 x, k는 모두 arr의 원소라고 했으므로 원소의 유무를 표시할 수 있는 해시 테이블 hash_table을 마련해 활용하면 O(1) 안에 찾을 수 있습니다. 그림으로 표현하면 다음과 같습니다.

왼쪽이 arr, 오른쪽이 arr을 보고 각 원소의 유무를 표현한 해시 테이블입니다. 해시 테이블의 크기는 arr의 원소 중 가장 큰 원소의 값 8과 같습니다. 1, 2, 3, 4, 8에 대해서는 1을, 나머지 수에 대해서는 0을 매치했습니다. 이렇게 해시 테이블을 준비하고 각 원소에 대해 hash_table(target – 원소)가 1이면 합을 통해 target을 만들 수 있는 두 수가 arr에 있다고 봐도 됩니다.

다음 코드는 계수 정렬(Counting Sort) 알고리즘을 사용해 배열 arr에서 문제에서 요구한 target을 찾는 함수를 구현한 겁니다. 계수 정렬 알고리즘은 입력 배열을 순회하며 각 원소의 등장 횟수를 세는 작업을 수행합니다. 코드를 보면 arr의 각 원소를 순회하면서 현재 원소의 값이 k 이하일 때 순회 대상 원소를 인덱스로 하는 해시 테이블의 값을 1로 설정합니다.

※ 계수 정렬은 ‘13장 정렬’에서 자세히 설명하므로 궁금하다면 잠깐 넘어가 공부하고 오기 바랍니다.

Use a different Browser

def count_sort(arr, k): # ➊ 해시 테이블 생성 및 초기화 hashtable = [0] * (k + 1) for num in arr: # ➋ 현재 원소의 값이 k 이하인 때에만 처리 if num <= k: # ➌ 현재 원소의 값을 인덱스로 해 해당 인덱스의 해시 테이블 값을 1로 설정 hashtable[num] = 1 return hashtabledef solution(arr, target): hashtable = count_sort(arr, target) for num in arr: complement = target - num # ➍ target에서 현재 원소를 뺀 값이 해시 테이블에 있는지 확인 if ( complement != num and complement >= 0 and complement <= target and hashtable[complement] == 1 ): return True return False

solution( ) 함수는 ❶ count_sort( ) 함수를 호출해 해시 테이블을 생성한 후 배열 arr을 순회하며 다음 작업을 수행합니다. ➋ 현재 원소 num에 대해서 target – num을 계산해 그 값이 해시 테이블에 있는지 확인합니다. 이때 target에서 현재 원소를 뺀 값이 현재 원소와 다르고, 0 이상이며 target 이하인지 확인하고, 해시 테이블의 값이 1인지 확인합니다. 이 조건을 만족하면 True를 반환하고 모든 원소에 대해 검사를 완료한 후에도 찾지 못하면 False를 반환합니다.

시간 복잡도 분석하기

N은 arr의 길이이고, K는 target의 길이입니다. count_sort( ) 함수의 시간 복잡도는 해시 테이블을 초기화할 때 시간 복잡도는 O(K), 배열 arr을 순회할 때 시간 복잡도는 O(N)이므로 O(N +K)입니다. solution( ) 함수의 시간 복잡도는 count_sort( ) 함수를 호출하면서 arr을 O(N)으로 순회하므로 최종 시간 복잡도는 O(N + K)이 됩니다.

문제 02 문자열 해싱을 이용한 검색 함수 만들기 ⭐️⭐️

저자 권장 시간: 40분

권장 시간 복잡조: O(N+K)

출제: 저자 출제

Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/19.py

문자열 리스트 string_list와 쿼리 리스트 query_list가 있을 때 각 쿼리 리스트에 있는 문자열이 string_list의 문자열 리스트에 있는지 여부를 확인해야 합니다. 문자열이 있으면 True, 없으면 False가 됩니다. 각 문자열에 대해서 문자열의 존재 여부를 리스트 형태로 반환하는 solution( ) 함수를 작성해주세요.

제약 조건

입력 문자열은 영어 소문자로만 이루어져 있습니다.

문자열의 최대 길이는 106입니다.

해시 충돌은 없습니다.

아래와 같은 문자열 해싱 방법을 활용해서 해싱 함수를 구현하세요.

다음 식에서 p는 31, m은 1,000,000,007로 합니다.

hash(s) = (s[0] + s[1]*p + s[2]*p2 …….. s[n-1]*pn-1) mod m

입출력의 예

문제 분석하고 풀기

문자열 해싱에 대한 개념은 앞서 자세히 설명했으므로 여기서 설명하지 않아도 될 것 같네요. 바로 문제를 풀어봅시다. string_list의 각 문자열들을 아스키코드값과 문자열 해싱으로 생성한 해시 값을 활용해서 해시에 저장합니다. 이후 query_list의 각 문자열들도 해싱한 후 해당 값이 해시에 있으면 True, 아니면 False를 반환합니다.

Use a different Browser

# ➊ polynomial hash를 구현한 부분def polynomial_hash(str): p = 31 # 소수 m = 1_000_000_007 # 버킷 크기 hash_value = 0 for char in str: hash_value = (hash_value * p + ord(char)) % m return hash_value def solution(string_list, query_list): # ➋ string_list의 각 문자열에 대해 다항 해시값을 계산 hash_list = [polynomial_hash(str) for str in string_list] # ➌ query_list의 각 문자열이 string_list에 있는지 확인 result = [ ] for query in query_list: query_hash = polynomial_hash(query) if query_hash in hash_list: result.append(True) else: result.append(False) return result

➊ 문자열 해싱을 구현한 부분입니다. 문자열 해싱을 하려면 각 문자의 아스키코드값이 필요합니다. ord( ) 함수는 특정 문자의 유니코드값을 반환하지만 예제에서는 영어 소문자만을 사용하므로 아스키코드값을 반환합니다. ➋ 각 string_list의 문자열들을 해싱하고 이를 기준으로 해시 테이블을 완성합니다. ➌ query_list의 각 문자열 해싱값이 해시 테이블에 있으면 True, 아니면 False를 result에 추가합니다.

시간 복잡도 분석하기

N은 string_list의 길이이고, K는 query_list의 길이입니다. polynomial_hash( ) 함수를 보면 충돌이 없다고 가정했으므로 시간 복잡도는 O(1)입니다. 다음으로 solution( ) 함수를 보면 string_list의 각 문자열에 대해 해시값을 계산하여 O(N), query_list의 각 문자열이 string_list에 있는지 확인하여 O(K)입니다. 따라서 최종 시간 복잡도는 O(N + K)입니다.

자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지

[되기] 코딩 테스트 합격자 되기(파이썬 편)

더 알아보기

저자 박경록

매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.

BFS DFS PYTHON 검색 그래프 깊이우선탐색 너비우선탐색 네이버 배달의민족 배민 버블정렬 빠른정렬 삼성 삼성전자 스택 알고리즘 알고리즘시험 우아한형제들 우형 이진트리 자료구조 자료구조시험 재귀호출 카카오 코딩테스트 코테 쿠팡 큐 탐색 트리 파이썬 프로그래머 프로그래머스 프로그래밍 프로그램

Related News

[Agent] AI 에이전트 프로토콜, 구글 A2A 개념부터 원리 실습하기

[Python] 파이썬으로 엑셀 다루기 | ❷ 엑셀 데이터 사용하기

[Python] 파이썬으로 엑셀 다루기 | ❶ 엑셀 데이터 사용하기

[Python] 아나콘다 설치하기 | Anaconda, 파이썬, 주피터 노트북, 단축키

골든래빗 2023-12-04