Two Sum 문제란?
난이도: 3/10
해시 테이블로 O(n) 해결 가능. 기본적인 자료구조 활용 문제로 초보자도 접근 가능. 최적화는 간단.Two Sum은 대표적인 알고리즘 문제로, 정수 배열 nums와 목표 합 target이 주어졌을 때, 배열에서 두 숫자를 찾아 그 합이 target이 되도록 하고, 해당 숫자들의 인덱스를 반환하는 문제입니다. 조건은 다음과 같습니다:
- 각 입력에는 정확히 하나의 해답이 존재합니다.
- 같은 요소를 두 번 사용할 수 없습니다.
예시:
- 입력: nums = [2, 7, 11, 15], target = 9
- 출력: [0, 1] (왜냐하면 nums[0] + nums[1] = 2 + 7 = 9)
왜 O(n) 시간 복잡도가 필요할까?
가장 직관적인 방법은 배열의 모든 숫자 쌍을 확인하는 것입니다. 하지만 이는 O(n²) 시간 복잡도를 가지므로 큰 배열에서는 비효율적입니다. 이를 개선하기 위해 해시 테이블을 사용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 해시 테이블은 숫자와 그 인덱스를 저장하여 빠른 조회를 가능하게 합니다.
해시 테이블의 작동 원리
해시 테이블을 사용한 Two Sum 해결 과정은 다음과 같습니다:
- 배열을 한 번 순회합니다.
- 각 숫자 nums[i]에 대해:
- 보수(complement, 즉 target - nums[i])를 계산합니다.
- 해시 테이블에서 보수가 존재하는지 확인합니다.
- 보수가 있으면 해당 숫자의 인덱스와 현재 인덱스 i를 반환합니다.
- 보수가 없으면 현재 숫자 nums[i]와 그 인덱스 i를 해시 테이블에 추가합니다.
- 이 방식은 배열을 단 한 번만 순회하므로 O(n) 시간 복잡도를 달성합니다.
코드 분석
위의 C 코드는 선형 탐사(linear probing)를 사용한 해시 테이블로 Two Sum 문제를 해결합니다. 코드를 하나씩 살펴보겠습니다.
1. 해시 테이블 구조
typedef struct {
int key; // 숫자 값
int value; // 배열 내 인덱스
} HashEntry;
typedef struct {
HashEntry* entries;
int size;
} HashTable;
- HashEntry: 숫자(key)와 해당 인덱스(value)를 저장합니다.
- HashTable: HashEntry 배열과 테이블 크기를 관리합니다.
2. 해시 테이블 초기화
HashTable* createHashTable(int size) {
HashTable* ht = malloc(sizeof(HashTable));
ht->entries = calloc(size, sizeof(HashEntry));
ht->size = size;
for (int i = 0; i < size; i++) {
ht->entries[i].key = -1; // 빈 슬롯 표시
}
return ht;
}
- 동적으로 해시 테이블을 할당하고, 빈 슬롯을 -1로 초기화합니다.
3. Two Sum 핵심 로직
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
HashTable* ht = createHashTable(numsSize);
int* result = malloc(2 * sizeof(int));
*returnSize = 2;
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
int hash = abs(complement % numsSize);
// 선형 탐사로 충돌 처리
while (ht->entries[hash].key != -1 && ht->entries[hash].key != complement) {
hash = (hash + 1) % numsSize;
}
// 보수(complement)를 찾음
if (ht->entries[hash].key == complement) {
result[0] = ht->entries[hash].value;
result[1] = i;
free(ht->entries);
free(ht);
return result;
}
// 현재 숫자 삽입
hash = abs(nums[i] % numsSize);
while (ht->entries[hash].key != -1) {
hash = (hash + 1) % numsSize;
}
ht->entries[hash].key = nums[i];
ht->entries[hash].value = i;
}
// 해답을 찾지 못함
free(ht->entries);
free(ht);
*returnSize = 0;
return NULL;
}
- 보수 확인: complement = target - nums[i]를 계산하고, 해시 테이블에서 이를 검색합니다.
- 충돌 처리: abs(complement % numsSize)로 해시 값을 계산하고, 충돌 시 선형 탐사로 다음 슬롯을 확인합니다.
- 결과 반환: 보수가 있으면 인덱스 쌍을 반환하고, 없으면 현재 숫자를 해시 테이블에 추가합니다.
- 메모리 해제: 사용한 메모리를 정리하여 누수를 방지합니다.
4. 사용 예시
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int numsSize = 4;
int returnSize;
int* result = twoSum(nums, numsSize, target, &returnSize);
if (result != NULL) {
printf("인덱스: [%d, %d]\n", result[0], result[1]);
free(result);
} else {
printf("해답을 찾지 못했습니다\n");
}
return 0;
}
- 예시 입력으로 [2, 7, 11, 15]와 target = 9를 사용해 [0, 1]을 출력합니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n). 해시 테이블의 삽입과 조회는 평균적으로 O(1)이며, 배열을 한 번 순회합니다.
- 공간 복잡도: O(n). 최대 n개의 요소를 저장하는 해시 테이블을 사용합니다.
장점
- 효율성: O(n) 시간 복잡도로 최적의 성능을 제공합니다.
- 간결함: 해시 테이블을 사용한 접근법은 이해하기 쉽고 구현이 간단합니다.
- 안정성: 선형 탐사로 충돌을 처리하고, 메모리 누수를 방지합니다.
사용팁
- 엣지 케이스 테스트: 빈 배열, 음수, 중복 숫자 등이 포함된 입력을 테스트해보세요.
- 해시 함수 개선: 실제 서비스에서는 더 정교한 해시 함수나 동적 크기 조정을 고려하세요.
- 다른 언어로 연습: Python, Java 등으로 동일한 로직을 구현해보세요. 언어별 해시 테이블의 차이를 알 수 있습니다.
- 직접 실행해보기: 코드를 복사해 컴파일하고, 다양한 입력으로 테스트해보세요.
마무리
Two Sum 문제는 코딩 인터뷰에서 자주 등장하는 기본 문제로, 해시 테이블의 활용법을 익히기에 최적입니다. 이 코드를 통해 O(n) 시간 복잡도의 힘을 체감하고, 해시 테이블의 사용법을 익힙니다. 한번에 이해하기 힘들 경우 반복 학습으로 의미를 파악하고, 구현을 해보시길 바랍니다.
full소스
#include <stdio.h>
#include <stdlib.h>
// 해시 테이블 구조체
typedef struct {
int key; // 숫자 값
int value; // 배열 내 인덱스
} HashEntry;
typedef struct {
HashEntry* entries;
int size;
} HashTable;
// 해시 테이블 생성 및 초기화
HashTable* createHashTable(int size) {
HashTable* ht = malloc(sizeof(HashTable));
ht->entries = calloc(size, sizeof(HashEntry));
ht->size = size;
for (int i = 0; i < size; i++) {
ht->entries[i].key = -1; // 빈 슬롯 표시
}
return ht;
}
// Two Sum 함수
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
HashTable* ht = createHashTable(numsSize);
int* result = malloc(2 * sizeof(int));
*returnSize = 2;
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
int hash = abs(complement % numsSize);
// 선형 탐사로 충돌 처리
while (ht->entries[hash].key != -1 && ht->entries[hash].key != complement) {
hash = (hash + 1) % numsSize;
}
// 보수(complement)를 찾음
if (ht->entries[hash].key == complement) {
result[0] = ht->entries[hash].value;
result[1] = i;
free(ht->entries);
free(ht);
return result;
}
// 현재 숫자 삽입
hash = abs(nums[i] % numsSize);
while (ht->entries[hash].key != -1) {
hash = (hash + 1) % numsSize;
}
ht->entries[hash].key = nums[i];
ht->entries[hash].value = i;
}
// 해답을 찾지 못함
free(ht->entries);
free(ht);
*returnSize = 0;
return NULL;
}
// 사용 예시
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int numsSize = 4;
int returnSize;
int* result = twoSum(nums, numsSize, target, &returnSize);
if (result != NULL) {
printf("인덱스: [%d, %d]\n", result[0], result[1]);
free(result);
} else {
printf("해답을 찾지 못했습니다\n");
}
return 0;
}
댓글
댓글 쓰기