단일 패스 탐색: 투 포인터 기법의 활용

투 포인터 기법은 두 개의 포인터를 조작하여 원하는 값을 찾거나 특정 조건을 만족하는 부분 배열을 찾을 때 사용합니다.

 

사용하는 방법이 많지만 결국 두 개의 포인터가 배열의 양 끝에서 시작하여 중앙으로 이동하거나, 같은 방향으로 이동하면서 모든 요소를 단 한 번씩만 검사한다는 특징이 있습니다.

 

양 끝에서 시작하여 중앙으로 이동하는 예제 중 주어진 배열에서 두 원소의 합이 target과 일치하는 쌍의 개수를 찾는 알고리즘으로 확인해 보겠습니다.

 

배열은 오름차순 정렬되어 있고 중복값은 없습니다.

1. 시작점(start)과 끝점(end) 두 개의 포인터를 설정합니다. 일반적으로 배열의 시작 위치에 두 포인터를 설정하지만 이 경우 배열의 처음과 끝에 포인터를 설정합니다.
2. 문제의 조건에 따라 두 포인터를 이동시킵니다.
   • 현재 부분 합이 목표값보다 작으면 start를 증가시킵니다.
   • 현재 부분 합이 목표값보다 크거나 같으면 end를 감소시킵니다.
3. 조건을 만족하는 경우 개수를 카운트합니다.

 

---

 

전체 코드를 보고 주요 부분만 확인해 보겠습니다.

def find_pair(arr, target):
    arr.sort()	#Timsort() 알고리즘 실행. O(N log N)
    start, end = 0, len(arr) - 1
    stack = 0 
    while start < end:
        current_sum = arr[start] + arr[end]
        
        if current_sum == target:
            stack += 1
            start += 1
        elif current_sum < target:
            start += 1
        else:
            end -= 1
    
    return stack

result = find_pair(arr, target)
print(result)

1. 포인터 초기화: left와 right 두 포인터를 각각 배열의 시작과 끝에 위치합니다.
2. 탐색: while 루프를 통해 left가 right보다 작은 동안 계속 탐색합니다.
3. 조건처리: 위의 설명처럼 문제의 조건에 따라 포인터가 이동됩니다.

이런 투 포인터 기법의 시간 복잡도는 O(N)입니다.

• 선형적 이동: 각 포인터가 배열의 처음부터 끝까지 최대 한 번 씩만 이동합니다.
  • 이는 전체 배열의 길이에 비례하는 시간이 소요됨을 의미합니다. O(N)
• 중첩 루프 제거.
  
  • 투 포인터 기법은 이중 반복문을 사용하는  O(N^2) 시간 복잡도의 해결책을 O(N)으로 해결할 수 있습니다.

결과적으로, 투 포인터 기법은 배열의 모든 요소를 단 한 번씩만 검사하면서 원하는 결과를 찾아내기 때문에 O(N)의 시간 복잡도를 갖습니다.

 

 

아래는 투 포인터 기법을 사용하는 문제들입니다.

1. 백준 1940번 주몽

[백준] 1940번 주몽 - Python(1편)

 

 

 

 

---

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.