leetcode에서 문제를 풀다가 투 포인터(슬라이딩 윈도우) 기법을 활용하는 방법을 알게 되었고 이에 대한 개념을 확실하게 다지고자 이렇게 글을 적는다..!
우선, 투 포인터 기법은 많은 알고리즘 문제에서 효율적인 해결 방법을 제공한다. 주로 배열이나 연결 리스트에서 값을 처리할 때 유용하며, O(n) 시간 복잡도를 가진 문제에서 최적화된 해법을 제시할 수 있다고 한다.
1. 투 포인터(슬라이딩 윈도우)란?
투 포인터 기법은 말 그대로 두 개의 포인터를 사용하여 문제를 해결하는 기법이다. 이 포인터들은 주로 배열이나 연결 리스트와 같은 데이터 구조에서 탐색 범위를 좁히거나, 값을 추적하는 역할을 한다.
슬라이딩 윈도우는 주로 범위가 정해진 문제에서 사용되며, 하나의 포인터는 범위의 시작을, 다른 하나는 범위의 끝을 가리킨다. 이를 통해 효율적인 탐색을 할 수 있다.
2. 투 포인터 기법의 기본 사용법
문제 1: "두 수의 합"
문제 설명
정수 배열 nums와 정수 target이 주어집니다. 배열에서 두 수를 더한 값이 target이 되는 인덱스를 반환하는 문제입니다. 각 입력에 대해 정답은 유일합니다.
nums = [2, 7, 11, 15], target = 9
Input: 9 2 7 11 15
Output: [0, 1]문제 풀이
이 문제는 두 수의 합을 구하는 문제이다. nums의 배열에서 두 수의 합이 target이 되도록 하는 두 인덱스를 찾는 문제로, 투 포인터를 사용해서 한 포인터는 배열의 맨 앞, 다른 포인터는 배열의 맨 끝에서 시작하며 가리키는 합이 target과 일치하면 return 하는 방식으로 접근할 수 있다.
핵심은, 두 포인터가 가리키는 값의 합이 target과 비교하면서
- 합이 target보다 작으면, 첫 번째 포인터를 오른쪽으로 이동시켜 합을 증가시킨다.
- 합이 target보다 크면, 두 번째 포인터를 왼쪽으로 이동시켜 합을 감소시킨다.
포인터가 서로 만날 때까지 이 과정을 반복한다는 것이다..!
위의 과정을 코드로 작성하면,
# 두 수의 합을 찾는 함수
def twoSum(nums, target):
left, right = 0, len(nums) - 1 # 포인터 초기화
# 배열을 정렬한 후 두 포인터 기법을 사용
nums_sorted = sorted((num, i) for i, num in enumerate(nums)) # 값과 인덱스를 묶어 정렬
while left < right:
current_sum = nums_sorted[left][0] + nums_sorted[right][0]
if current_sum == target:
return [nums_sorted[left][1], nums_sorted[right][1]] # 인덱스 반환
elif current_sum < target:
left += 1 # 합이 작으면 left 포인터를 오른쪽으로 이동
else:
right -= 1 # 합이 크면 right 포인터를 왼쪽으로 이동
return [] # 답이 없을 경우 빈 리스트 반환
# 입력 받기
nums_input = input().split()
target = int(nums_input[0]) # target
nums = list(map(int, nums_input[1:])) # nums 리스트
# 두 수의 합을 찾고 결과 출력
result = twoSum(nums, target)
# 결과 출력
print(result)이와 같이 투 포인터 기법을 사용하여 문제를 해결하면 효율적으로 코드를 작성할 수 있는데 아래에 장점을 정리해보았다.
3. 투 포인터 기법의 장점
1) 효율적인 시간 복잡도(O(n))
일반적으로, 배열이나 리스트에서 문제를 풀 때 여러 번 순회해야 하는 경우가 많다. 하지만 두 개의 포인터를 사용하면 배열을 한 번만 순회해도 문제를 해결할 수 있기 때문에 시간 복잡도를 O(n) 으로 줄일 수 있다. 예를 들어, 위의 두 수의 합 문제에서도 배열을 한 번만 순회하고, 각 값을 한 번만 비교하면서 해답을 찾을 수 있음을 알 수 있다.
2) 공간 복잡도 절약(O(1))
투 포인터 기법은 O(1) 의 추가 공간만 필요로 한다. 별도의 추가적인 자료구조를 만들지 않고 두 포인터만을 이용하여 해결할 수 있기 때문에 메모리 효율적인 방법이다.
이외에도 간결하고 직관적인 코드를 작성할 수 있고 코드의 복잡성을 줄일 수 있다는 점과 탐색 범위를 동적으로 조정할 수 있기 때문에 배열, 연결 리스트, 문자열 등 다양한 데이터 구조에서 활용할 수 있다는 점 또한 장점이다!
4. 결론
투 포인터 기법은 매우 강력하고 효율적인 방법으로, 다양한 알고리즘 문제를 해결할 때 큰 도움이 된다는 것을 알았다. 특히 배열이나 연결 리스트에서 범위를 동적으로 변경하거나 값을 추적할 때 매우 유용하며, O(n) 시간 복잡도로 문제를 해결할 수 있는 방법을 제공하므로 다양한 활용법을 배우고 적용해 나가면, 더 많은 문제를 효율적으로 해결할 수 있을 것이므로 많은 문제를 접하면서 적용해봐야겠다!
참고로 투 포인터와 관련하여 이 글을 적게 된 leetcode 19 "Remove Nth Node From End of List" 문제에 대해서는 다음 게시물에 정리해놓았다.
