본 강좌에서는 투 포인터 알고리즘을 활용한 코딩 문제를 다루고, 문제를 해결하는 과정을 단계별로 설명합니다.
투 포인터 기법은 배열이나 리스트와 같은 선형 데이터 구조에서 두 개의 포인터를 사용하는 방식으로, 시간 복잡도를 줄이고
효율적인 문제 해결을 가능하게 합니다.
문제 설명
주어진 정수 배열 nums와 정수 target가 있을 때,
nums 배열 내에서 두 수의 합이 target과 같은 인덱스를 찾아 해당 인덱스를 반환하는 문제를 해결하세요.
사용자는 한 쌍의 정수가 반드시 존재한다고 가정합니다.
입력 예시
nums = [2, 7, 11, 15]target = 9
출력 예시
[0, 1]
알고리즘 접근법
이 문제를 해결하기 위해서는 투 포인터 기법을 사용하여 배열을 순회하고,
현재 두 포인터가 가리키는 값의 합을 비교하면서 목표한 값을 찾는 방향으로 접근합니다.
투 포인터 기법은 보통 정렬된 배열에 적용되지만, 이 문제에서는 두 포인터가
같은 배열을 가리키면서 다양한 경우를 고려하는 방법으로 사용될 수 있습니다.
문제 풀이 과정
1. 배열의 두 포인트 초기 인덱스 설정
배열의 시작 포인터 left는 0으로, 마지막 포인터 right는 배열의 길이 – 1로 초기화합니다.
이렇게 하면 nums[left]와 nums[right]를 통해 배열을 탐색할 수 있습니다.
2. 반복 형태로 포인터 이동
예를 들어, 다음과 같은 반복문을 사용하여 두 포인터가 가리키는 값의 합을 비교합니다:
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] { left, right };
} else if (sum < target) {
left++;
} else {
right--;
}
}3. 결과 반환
조건에 맞는 left와 right의 인덱스를 찾으면 해당 값을 반환합니다.
만약 조건에 맞는 값이 없다면 null 또는 예외를 반환하도록 처리합니다.
C# 코드 구현
using System;
class Program {
static void Main(string[] args) {
int[] nums = { 2, 7, 11, 15 };
int target = 9;
int[] result = TwoSum(nums, target);
Console.WriteLine($"[{result[0]}, {result[1]}]");
}
static int[] TwoSum(int[] nums, int target) {
int left = 0;
int right = nums.Length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] { left, right };
} else if (sum < target) {
left++;
} else {
right--;
}
}
// 조건에 맞는 쌍을 찾지 못한 경우
throw new Exception("No two sum solution");
}
}
풀이 분석
1. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(n)입니다.
left와 right 포인터가 한 번씩 배열을 스캔하기 때문에 최악의 경우에도
O(n)으로 성능이 유지됩니다.
2. 공간 복잡도
공간 복잡도는 O(1)입니다. 추가적인 배열이나 리스트를 사용하지 않으므로 공간적 성능이 뛰어납니다.
결론
이번 강좌에서는 투 포인터 알고리즘을 이용하여 간단한 문제를 해결해보았습니다.
투 포인터 기법은 여러 문제에서 매우 유용하게 사용될 수 있으며, 배열이나 리스트를 효과적으로
탐색하는 방법입니다. 앞으로 더 다양한 예제와 함께 이 기법을 더욱 심화학습하면 좋겠습니다.