이 글에서는 알고리즘 문제를 통해 배열과 리스트에 대한 이해를 높이고, 배열과 리스트를 다룰 때 유용한 다양한 기법들을 살펴보겠습니다. 배열과 리스트는 데이터 구조 중 가장 기초적이고 중요한 부분으로, 코딩 테스트에서 자주 출제됩니다. 본 강좌에서는 알고리즘 문제 하나를 선정하여 그 문제를 해결하는 과정을 단계적으로 설명할 것입니다.
문제 설명
다음은 “주어진 배열에서 특정 숫자 쌍을 찾는 문제”입니다.
문제: 두 수의 합 (Two Sum)
주어진 정수 배열 nums와 정수 target이 주어질 때,
배열에서 두 수의 합이 target이 되는 두 수의 인덱스를 반환하는 함수를 작성하세요.
예를 들어, nums = [2, 7, 11, 15]이고 target = 9인 경우,
반환해야 할 결과는 [0, 1]입니다. (2 + 7 = 9)
문제 접근 방법
이 문제를 해결하기 위해 몇 가지 전략을 고려할 수 있습니다. 접근 방법은 다음과 같습니다:
- 브루트 포스 (Brute Force) 방법: 두 개의 중첩된 루프를 사용하여 모든 쌍의 합을 확인합니다. 이는 O(n^2)의 시간 복잡도를 가집니다.
- 해시 맵 (HashMap) 사용: 숫자를 순회하면서 해시 맵에 현재 숫자의 인덱스를 저장하고,
target - 현재 숫자가 해시 맵에 존재하는지를 확인합니다. 이는 O(n)의 시간 복잡도를 가집니다.
해결 방법
두 번째 방법인 해시 맵을 사용하는 방법이 더 효율적이므로 이 방법을 사용하여 해결해 보겠습니다.
먼저, 주어진 배열과 타겟을 바탕으로 다음과 같은 단계를 따라 진행합니다:
1단계: 초기화
빈 해시 맵을 초기화하고 배열을 순회하면서 두 수의 합을 찾기 위한 변수를 설정합니다.
2단계: 숫자 순회
배열의 각 숫자를 확인하면서, 먼저 현재 숫자의 보수가 해시 맵에 있는지를 확인합니다.
만약 있다면 그 인덱스를 결과로 반환합니다. 없다면 현재 숫자와 그 인덱스를 해시 맵에 추가합니다.
3단계: 결과 반환
모든 숫자를 순회한 후, 합이 target인 두 수를 찾지 못했다면 이는 문제의 요구 사항에 맞지 않습니다.
코드 구현
위의 접근 방법을 코드로 구현하면 다음과 같습니다:
def two_sum(nums, target):
num_map = {}
for index, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], index]
num_map[num] = index
return []
코드 설명
위 코드에서 two_sum 함수는 두 매개변수 nums와 target을 입력받습니다.
num_map이라는 빈 해시 맵을 초기화하고, enumerate 함수를 사용하여 nums를 순회합니다.
각 숫자에 대해 complement를 계산하고 해시 맵에서 그 값을 찾습니다.
만약 찾는다면 해당 인덱스와 현재 인덱스를 리스트에 담아 반환합니다.
끝까지 찾지 못했다면 빈 리스트를 반환합니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다.
이는 해시 맵에 저장된 모든 숫자와 인덱스 때문입니다.
이 방법은 주어진 배열에서 원하는 쌍을 효율적으로 찾을 수 있도록 설계되었습니다.
결론
배열과 리스트는 데이터 처리의 기본 요소이며, 다양한 알고리즘 문제에서 중요한 역할을 합니다.
이번 강좌에서는 “두 수의 합” 문제를 통해 배열의 인덱스를 탐색하고 해시 맵을 활용하여 효율적으로 문제를 해결하는 방법에 대해 알아보았습니다.
실제 코딩 테스트 상황에서 시간을 절약하고 문제를 해결하는 데 큰 도움이 될 것입니다.
앞으로도 다양한 알고리즘 문제를 통해 배열, 리스트, 해시 맵 등 데이터 구조에 대한 이해를 깊이 있게 다질 예정입니다.
지속적인 연습과 문제 풀이를 통해 더욱 숙련된 코더가 되기를 바랍니다. 감사합니다.