[기초 알고리즘 #05] 투포인터

오늘 이야기해 볼 알고리즘은 투포인터(Two-Pointer) 알고리즘입니다.

개념은 자체는 어렵지 않지만,

인덱스를 적극 활용하는 알고리즘인만큼 인덱스 에러를 조심할 필요가 있습니다!

그럼 바로 시작해보겠습니다 ❤

1. 투포인터 (Two Pointer)

1차원 배열에서 각자 다른 원소를 가리키는 2개의 인덱스(포인터)를 조작해가면서 값을 조회하는 알고리즘.

네, 이게 답니다.

예를 하나 들어서 설명해볼게요.

아래 이미지처럼 8개의 정수값이 담긴 배열의 총합을 구해본다고 생각해봅시다.

1-1. for문으로 구하기

단순하게 생각해본다면…

반복문을 통해서, 8개의 값을 모두 조회하면서 sum 변수에 누적해서 더하는 방식으로 결과를 구할 수 있을 것 같습니다.

• 이미지

  

• 코드

    numbers = [1, 4, 7, 12, 31, 22, 66, 0]
    sum = 0
  
    for i in range(len(numbers)):
        sum += numbers[i]
  
    print(sum)
  

이 코드는 반드시 배열의 길이 N만큼의 반복하게 됩니다.

그런데! 투포인터 알고리즘을 사용하면, 무려 N / 2 번 만큼 반복 횟수를 줄일 수 있습니다.

1-2. 투포인터를 적용해서 구하기

• 이미지

  

• 코드

    numbers = [1, 4, 7, 12, 31, 22, 66, 0]
    sum = 0
  
    start = 0
    end = len(numbers) - 1
  
    while start < end:
        sum += numbers[start] + numbers[end]
        start += 1
        end -= 1
  
    print(sum)
  

  그럼 바뀐 코드를 한 줄씩 분석해보죠!

        start = 0
        end = len(numbers) - 1
  

  • 먼저 start 변수는 배열의 시작지점에 해당하는 index를 나타내기 위해 0으로 초기화 해줍니다.
  • end 변수는 배열의 끝지점에 해당하는 index를 나타내기 위해 배열의 길이(len(number))에서 1을 뺀 값으로 으로 초기화 해줍니다.

        while start < end:
            sum += numbers[start] + numbers[end]
            start += 1
            end -= 1
  

  • numbers[start]와 numbers[end]를 더한값을 sum 변수에 더해줍니다.
  • 덧셈이 완료 된 후, start 변수는 1을 더해주고, end 변수는 1을 빼줍니다.
  • while 반복이 진행됨에 따라, start 변수와 end 변수가 만나는 지점이 오겠죠?
  • start == end 의 상태가 되면 while 문 조건이 불충족됨에 따라 반복은 종료됩니다.

지금까지 배열의 총합을 구하는 문제를 통해 투포인터 알고리즘을 알아봤는데요.

방금처럼, 양끝에서 가운데쪽으로 두 개의 인덱스를 끌어오면서 조회를 하는 방법이 있는가 하면,

같은 인덱스에서 시작해서 조건에 따라 인덱스를 옮겨가며, 값을 조회할 수도 있기 때문에

두 개의 인덱스를 유연하게 활용하는 연습이 꼭 필요합니다.

아래 연습 문제를 통해 충분히 연습해보셔요 😁

⚫ 더 연습해볼 수 있는 문제

1. 백준 1940 주몽 » 링크
2. 백준 2018 수들의 합 5 » 링크
3. 백준 30804 과일탕후루 » 링크

⚫ 참고 자료

1. Two-Pointers Algorithm (투 포인터 알고리즘). velog. heyggun https://velog.io/@heyggun/Algorithm-Two-Pointers-Algorithm-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

---