10.4 해시를 이용한 최적화 전략¶
알고리즘 문제에서는 선형 탐색을 해시 탐색으로 바꾸어 시간 복잡도를 줄이는 경우가 많다. 한 가지 문제를 통해 더 자세히 알아보자.
문제
정수 배열 nums와 목표 원소 target이 주어진다. 배열에서 '합'이 target인 두 원소를 찾아 그 인덱스를 반환하라. 답이 여러 개라면 아무거나 하나를 반환해도 된다.
10.4.1 선형 탐색: 시간을 더 써서 공간 절약¶
가능한 모든 조합을 직접 순회해 보자. 아래 그림(10-9)과 같이 이중 반복문을 사용하여 매번 두 정수의 합이 target인지 확인하고, 맞으면 두 인덱스를 반환한다.
그림 10-9 선형 탐색으로 두 수의 합 구하기
코드는 다음과 같다.
two_sum.c
/* 방법 1: 완전 열거 */
int *twoSumBruteForce(int *nums, int numsSize, int target, int *returnSize) {
for (int i = 0; i < numsSize; ++i) {
for (int j = i + 1; j < numsSize; ++j) {
if (nums[i] + nums[j] == target) {
int *res = malloc(sizeof(int) * 2);
res[0] = i, res[1] = j;
*returnSize = 2;
return res;
}
}
}
*returnSize = 0;
return NULL;
}
코드 시각화
이 방법의 시간 복잡도는 \(O(n^2)\), 공간 복잡도는 \(O(1)\)이다. 데이터가 많으면 시간이 매우 오래 걸린다.
10.4.2 해시 탐색: 공간을 더 써서 시간 절약¶
키와 값으로 각각 배열 원소와 그 인덱스를 저장하는 해시 테이블을 사용해 보자. 배열을 순회하면서 매번 아래 그림(10-10)의 단계를 수행한다.
- 수
target - nums[i]가 해시 테이블에 있는지 확인하고, 있으면 두 원소의 인덱스를 바로 반환한다. nums[i]와 인덱스i로 이루어진 키-값 쌍을 해시 테이블에 추가한다.
그림 10-10 보조 해시 테이블로 두 수의 합 구하기
구현 코드는 다음과 같으며, 단일 반복문만 있으면 된다.
two_sum.cpp
/* 방법 2: 보조 해시 테이블 */
vector<int> twoSumHashTable(vector<int> &nums, int target) {
int size = nums.size();
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
unordered_map<int, int> dic;
// 단일 반복문이며 시간 복잡도는 O(n)이다
for (int i = 0; i < size; i++) {
if (dic.find(target - nums[i]) != dic.end()) {
return {dic[target - nums[i]], i};
}
dic.emplace(nums[i], i);
}
return {};
}
two_sum.java
/* 방법 2: 보조 해시 테이블 */
int[] twoSumHashTable(int[] nums, int target) {
int size = nums.length;
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
Map<Integer, Integer> dic = new HashMap<>();
// 단일 반복문이며 시간 복잡도는 O(n)이다
for (int i = 0; i < size; i++) {
if (dic.containsKey(target - nums[i])) {
return new int[] { dic.get(target - nums[i]), i };
}
dic.put(nums[i], i);
}
return new int[0];
}
two_sum.cs
/* 방법 2: 보조 해시 테이블 */
int[] TwoSumHashTable(int[] nums, int target) {
int size = nums.Length;
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
Dictionary<int, int> dic = [];
// 단일 반복문이며 시간 복잡도는 O(n)이다
for (int i = 0; i < size; i++) {
if (dic.ContainsKey(target - nums[i])) {
return [dic[target - nums[i]], i];
}
dic.Add(nums[i], i);
}
return [];
}
two_sum.go
/* 방법 2: 보조 해시 테이블 */
func twoSumHashTable(nums []int, target int) []int {
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
hashTable := map[int]int{}
// 단일 반복문이며 시간 복잡도는 O(n)이다
for idx, val := range nums {
if preIdx, ok := hashTable[target-val]; ok {
return []int{preIdx, idx}
}
hashTable[val] = idx
}
return nil
}
two_sum.ts
/* 방법 2: 보조 해시 테이블 */
function twoSumHashTable(nums: number[], target: number): number[] {
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
let m: Map<number, number> = new Map();
// 단일 반복문이며 시간 복잡도는 O(n)이다
for (let i = 0; i < nums.length; i++) {
let index = m.get(target - nums[i]);
if (index !== undefined) {
return [index, i];
} else {
m.set(nums[i], i);
}
}
return [];
}
two_sum.dart
/* 방법 2: 보조 해시 테이블 */
List<int> twoSumHashTable(List<int> nums, int target) {
int size = nums.length;
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
Map<int, int> dic = HashMap();
// 단일 반복문이며 시간 복잡도는 O(n)이다
for (var i = 0; i < size; i++) {
if (dic.containsKey(target - nums[i])) {
return [dic[target - nums[i]]!, i];
}
dic.putIfAbsent(nums[i], () => i);
}
return [0];
}
two_sum.rs
/* 방법 2: 보조 해시 테이블 */
pub fn two_sum_hash_table(nums: &Vec<i32>, target: i32) -> Option<Vec<i32>> {
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
let mut dic = HashMap::new();
// 단일 반복문이며 시간 복잡도는 O(n)이다
for (i, num) in nums.iter().enumerate() {
match dic.get(&(target - num)) {
Some(v) => return Some(vec![*v as i32, i as i32]),
None => dic.insert(num, i as i32),
};
}
None
}
two_sum.c
/* 해시 테이블 */
typedef struct {
int key;
int val;
UT_hash_handle hh; // uthash.h를 기반으로 구현한다
} HashTable;
/* 해시 테이블 조회 */
HashTable *find(HashTable *h, int key) {
HashTable *tmp;
HASH_FIND_INT(h, &key, tmp);
return tmp;
}
/* 해시 테이블에 원소 삽입 */
void insert(HashTable **h, int key, int val) {
HashTable *t = find(*h, key);
if (t == NULL) {
HashTable *tmp = malloc(sizeof(HashTable));
tmp->key = key, tmp->val = val;
HASH_ADD_INT(*h, key, tmp);
} else {
t->val = val;
}
}
/* 방법 2: 보조 해시 테이블 */
int *twoSumHashTable(int *nums, int numsSize, int target, int *returnSize) {
HashTable *hashtable = NULL;
for (int i = 0; i < numsSize; i++) {
HashTable *t = find(hashtable, target - nums[i]);
if (t != NULL) {
int *res = malloc(sizeof(int) * 2);
res[0] = t->val, res[1] = i;
*returnSize = 2;
return res;
}
insert(&hashtable, nums[i], i);
}
*returnSize = 0;
return NULL;
}
two_sum.kt
/* 방법 2: 보조 해시 테이블 */
fun twoSumHashTable(nums: IntArray, target: Int): IntArray {
val size = nums.size
// 보조 해시 테이블의 공간 복잡도는 O(n)이다
val dic = HashMap<Int, Int>()
// 단일 반복문이며 시간 복잡도는 O(n)이다
for (i in 0..<size) {
if (dic.containsKey(target - nums[i])) {
return intArrayOf(dic[target - nums[i]]!!, i)
}
dic[nums[i]] = i
}
return IntArray(0)
}
코드 시각화
이 방법은 해시 탐색으로 시간 복잡도를 \(O(n^2)\)에서 \(O(n)\)으로 줄여 실행 효율을 크게 높인다.
해시 테이블을 추가로 유지해야 하므로 공간 복잡도는 \(O(n)\)이다. 그렇더라도 시간과 공간 효율의 균형이 더 좋으므로 이 문제의 최적 풀이에 해당한다.