주어진 정수 배열에서 두 수의 합이 특정 값인 조합을 찾는 문제는 알고리즘의 기본적인 문제 중 하나입니다. 이러한 문제를 해결하기 위해 두 가지 일반적인 방법을 사용할 수 있습니다: 브루트 포스 알고리즘과 해시 맵을 이용한 방법입니다.
브루트 포스 알고리즘
가장 간단한 방법은 브루트 포스 알고리즘을 사용하는 것입니다. 이 방법은 배열의 모든 가능한 조합을 확인하여 조건에 맞는 조합을 찾습니다.
def find_sum_combination(arr, target_sum):
n = len(arr)
for i in range(n-1):
for j in range(i+1, n):
if arr[i] + arr[j] == target_sum:
return (arr[i], arr[j])
return None
arr = [1, 2, 3, 4, 5]
target_sum = 8
result = find_sum_combination(arr, target_sum)
if result is not None:
print(f"The combination for sum {target_sum} is {result[0]} and {result[1]}.")
else:
print("No combination found.")
위의 코드에서 find_sum_combination 함수는 배열과 목표 합계를 인수로 받아 조합을 찾아줍니다. 이 함수는 두 개의 반복문을 사용하여 모든 가능한 조합을 확인합니다. 조건에 맞는 조합을 찾으면 해당 조합을 반환하고, 찾을 수 없으면 None을 반환합니다.
해시 맵을 이용한 방법
다른 방법은 해시 맵을 이용하여 문제를 해결하는 것입니다. 이 방법은 배열을 한 번 순회하면서 해시 맵에 각 요소의 값과 인덱스를 저장한 후, 다시 배열을 순회하면서 조합을 찾습니다.
def find_sum_combination(arr, target_sum):
num_dict = {}
for i in range(len(arr)):
complement = target_sum - arr[i]
if complement in num_dict:
return (arr[i], complement)
num_dict[arr[i]] = i
return None
arr = [1, 2, 3, 4, 5]
target_sum = 8
result = find_sum_combination(arr, target_sum)
if result is not None:
print(f"The combination for sum {target_sum} is {result[0]} and {result[1]}.")
else:
print("No combination found.")
위의 코드에서는 find_sum_combination 함수가 해시 맵 num_dict를 사용하여 요소의 값을 키로, 인덱스를 값으로 저장합니다. 배열을 순회하면서 찾을 수 있는 조합을 확인하고, 조건에 맞는 조합을 발견하면 해당 조합을 반환합니다.
결론
배열에서 두 수의 합이 특정 값인 조합을 찾는 문제는 브루트 포스 알고리즘과 해시 맵을 이용한 방법으로 해결할 수 있습니다. 브루트 포스 알고리즘은 간단하지만 배열의 크기가 클 경우 효율적이지 않을 수 있습니다. 반면에 해시 맵을 이용한 방법은 추가적인 공간을 사용하지만 배열을 한 번만 순회하므로 시간 복잡도가 개선됩니다. 상황과 요구사항을 고려하여 적절한 방법을 선택하면 됩니다.
참고 자료:
- GeeksforGeeks: Find pair of elements from an array whose sum equals a given number
- LeetCode: Two Sum #algorithm #coding