👉 [알고리즘] 투포인터 알고리즘

투 포인터(Two Pointers) 알고리즘은 주로 배열이나 리스트와 같은 순차적인 자료구조에서 특정 범위를 탐색하거나 부분합, 부분 문자열 등을 찾을 때 유용한 알고리즘이다.

 

투 포인터 알고리즘은 이름 그대로, 두 개의 포인터를 이용하여 문제를 해결한다.

 

이 알고리즘은 보통 정렬된 배열에서 찾는 문제에서 유용하게 사용한다.

 

1. 배열이나 리스트에서 각각 왼쪽 포인터(left)와 오른쪽 포인터(right)를 정한다.

2. right를 체크 대상 추가를 위해 +1 씩한다.

3. left를 체크 대상 해제를 위해 +1 씩한다.

4. 반복해서 두 포인터의 위치를 조정하며 문제를 해결한다.

 

보통 이 알고리즘은 두 포인터의 위치를 이동시키는 규칙을 설정하여 사용한다.

예를 들어, 부분합을 구하는 문제에서는 왼쪽 포인터를 고정하고 오른쪽 포인터를 이동시키며 부분합을 구한다.

 

부분합이 구해진 후, 왼쪽 포인터를 이동시켜 불필요한 계산을 줄인다.

 

또한, 투 포인터 알고리즘은 이진 탐색과도 함께 사용한다.

 

이진 탐색에서는 중간값을 기준으로 값을 비교하는데, 투 포인터 알고리즘에서는 중간 값을 기준으로 포인터의 위치를 조정한다.

 

이 알고리즘은 O(N)의 시간 복잡도를 갖으며, 두 개의 포인터를 조정하며 해결하기 때문에 다른 알고리즘에 비해 상대적으로 적은 메모리를 사용한다.

 

이러한 특징으로 인해 투 포인터 알고리즘은 대부분의 경우에 유용하게 사용한다.

---

두 수의 합

• 정렬된 정수 배열 nums와 정수 target이 주어집니다.
• nums 배열에서 두 수를 더해 target을 만들 수 있는 인덱스 두 개를 찾아 반환합니다.
• 만약, 두 수를 찾을 수 없다면 빈 배열을 반환합니다.

예시 입력: nums = [2,7,11,15], target = 9

예시 출력: [0,1]

def twoSum(nums, target):
    left, right = 0, len(nums)-1
    while left < right:
        if nums[left] + nums[right] == target:
            return [left, right]
        elif nums[left] + nums[right] < target:
            left += 1
        else:
            right -= 1
    return []

 

 

연속된 자연수의 합

• 자연수 N이 주어집니다. N을 연속된 자연수의 합으로 나타내는 경우의 수를 구합니다.

예시 입력: N = 15

예시 출력: 3

 

def consecutive_numbers_sum(N):
    count = 0
    for k in range(1, int((2 * N) ** 0.5) + 1):
        if (N - (k * (k - 1)) // 2) % k == 0:
            count += 1
    return count