투포인터

연속된 합을 구할 때 사용하는 알고리즘이다. 구간 합으로 구할 수도 있지만 작은 시간복잡도가 필요할 때 사용할 수 있다.

 

 

  • start_idx와 end_idx를 놓는다.
  • 다음과 같은 방법으로 합이 목표한 값과 맞는지 판단하면서 포인터들을 옮긴다.
    • sum < M : end_idx++; sum += end_idx;
    • sum > M : sum -= start_idx; start_idx++;
    • sum == M : end_idx++; sum += end_idx; cnt++;
  • 종료 조건은 end_idx == M일 때다.

왜 start_idx가 움직일 때 더하고 end_idx가 움직일 때 빼는 건 안되는지 생각해 봤다. start_idx가 더하면서 움직이면 나중에 end_idx를 추월한다. 이는 우리가 구성한 로직과 맞지 않다.

end_idx를 빼면서 가게 되면 앞으로 올 수들을 더하는게 아니라 빼기 때문에 sum이 점점 절댓값이 큰 음수로 변한다.

 

 

📍시간 복잡도 비교

투포인터와 구간 합의 시간 복잡도를 비교해보자. 문제 상황은 특정 수 N과 같은 연속된 구간 합의 개수를 구하는 것이다.

 

구간 합

  • 모든 구간의 차를 구해야 한다. 이는 합 배열에서 무작위로 순서 상관 없이 두 원소를 구하는 것과 같다.
  • 조합으로 구한다면, 원소의 갯수가 N일 때 N(N-1) / 2 이므로 O(N^2)이다.

투포인터

  • start_idx, end_idx가 최대 끝까지 이동하는 경우가 최대로 오래 걸리는 경우의 수다.
  • 원소 수가 N개라면 둘 다 N번 이동하는 게 끝이므로, N + N = 2N O(N)이 최대다.

 

연속된 원소들의 합을 구하는데 적은 시간 복잡도가 필요한 경우 투포인터를 이용하자.

 

 

연속된 자연수의 합 구하기 (2018)

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶어 한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 출력하시오

예제 입력 1 

15

예제 출력 1 

4

 

 

1️⃣ 분석, 2️⃣ 손으로 풀어보기

 

위에서 분석한 투포인터를 사용하기 적합하다. 시간 제한이 1 초고 N이 천만이기 때문에 구간 합을 이용하면 시간제한을 넘어버린다.

 

3️⃣ 슈도 코드

 

4️⃣ 실제 코드 작성

import sys
input = sys.stdin.readline
N = int(input())
start_idx = 1
end_idx = 1
sum = 1
cnt = 1

while end_idx != N:
    if sum < N: 
        end_idx += 1
        sum += end_idx
    elif sum > N: 
        sum -= start_idx
        start_idx += 1
    elif sum == N:
        end_idx += 1
        sum += end_idx
        cnt += 1

print(cnt)

주목할 건 cnt = 1로 미리 초기화 했다는 것이다. 그 이유는 while 문의 종료조건이 end_idx가 N일 때라 N 하나로 구성할 수 있는 경우의 수를 못 구하기 때문이다. 

그래서 미리 cnt = 1로 그 경우의 수를 세둔다.

 

💡배운점

  • 투포인터의 정의와 시간복잡도

 

 

주몽 (1940)

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입력 1 

6
9
2 7 4 1 5 3

예제 출력 1 

2

 

 

1️⃣ 분석

 

N이 15,000이 되니 합 배열로 모든 구간 합을 조사하면 O(N^2)이다. 투포인터로 풀어야 한다.

 

2️⃣ 손으로 풀어보기

 

조건을 보고 생각한 문제는 두 가지다. 

  • 정렬이 안되어 있는 리스트에서 투포인터를 어떻게 사용하나?
  • 모든 경우의 수를 봐야하는가? 아니면 어떻게 포인터를 움직여야 하나?

처음 배열을 받을 때 정렬되지 않은 상태로 받아 투포인터를 생각하기 어려웠다. 포인터를 움직일 기준이 없기 때문이다.

그래서 생각한 건 직접 정렬을 시키는 것이다. 그래서 파이썬에서 제공하는 정렬 메소드를 찾아봤다.

 

💡파이썬 정렬 메소드
파이썬은 sorted와 .sort()의 두 개의 메소드를 제공한다. 전자는 어느 iteration에 다 적용되는 정렬 메소드이고 반환값은 정렬한 iteration이다. .sort()는 리스트 전용 정렬 메소드이며 반환값이 없다.
sorted()의 시간 복잡도는 최악은 O(N^2) 평균은 O(NlogN)으로 iteration마다 다르다. 

https://docs.python.org/3/howto/sorting.html 

 

Sorting Techniques

Author, Andrew Dalke and Raymond Hettinger,. Python lists have a built-in list.sort() method that modifies the list in-place. There is also a sorted() built-in function that builds a new sorted lis...

docs.python.org

 

리스트를 정렬해야 투포인터를 사용할 때 기준을 정할 수 있다. 이는 정렬 메소드로 해결했다.

그럼 투포인터의 기준을 어떻게 잡아야 하나? 내가 아는건 start_idx와 end_idx 두 개를 움직여 구하는 것이었다. 그치만 이 방법은 구간 합을 구하는데 좀 더 특화돼있는 것 같았다. 딱 두 값만 더해 M을 만족해야 했기에 이 방법을 사용하는건 비효율적이었다.

만약 알던 방법을 사용하고 싶으면 포인터가 움직일 때 더했던 값을 다시 빼고 앞 인덱스의 값을 더해야했다.

   

3️⃣ 슈도 코드

  • 투포인터의 기준을 어떻게 잡을 것인가?

이걸 고민하고 코드를 한번 작성해봤다.

 

4️⃣ 실제 코드 작성

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
A = sorted(list(map(int, input().split())))
cnt = 0
start_idx = 0
end_idx = 1
sum = A[0] + A[1]

while end_idx != (len(A)-1):
    if sum < M:
        sum -= A[end_idx]
        end_idx += 1
        sum += A[end_idx]
    elif sum > M:
        sum -= A[start_idx]
        start_idx += 1
        sum += A[start_idx]
    elif sum == M:
        sum -= A[end_idx]
        end_idx += 1
        sum += A[end_idx]
        cnt += 1

print(cnt)

 

첫 번째로 작성한 코드다. 다음과 같은 문제가 있었다.

  • 복잡하다.
  • 맞는 로직인지 잘 모르겠다
  • 두 원소의 합만 따지면 되는 상황에서 구간 합을 사용하니 비효율적이다.
  • 리스트의 끝 인덱스는 그냥 N-1로 하면된다.

책에선 투포인터를 양끝으로 활용하는 방법을 알려준다. 사실 투포인터에서 꼭 두개의 포인터가 같은 인덱스에서 시작할 필요는 없다. 양끝에서 시작하면 두개의 원소를 판단할 때 더 쉽다.

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
A = sorted(list(map(int, input().split())))
i = 0
j = N-1
cnt = 0
while i < j:
    if A[i] + A[j] > M:
        j -= 1
    elif A[i] + A[j] < M:
        i += 1
    elif A[i] + A[j] == M:
        cnt += 1
        j -= 1
        i += 1

print(cnt)

인덱스 변수 이름을 i, j로 쉽게 하고 끝 인덱스를 N-1이라 하자. 투포인터를 양끝에서 시작하면 포인터를 움직이는 기준을 잡기 쉬워진다. 그리고 인덱스를 사용해 sum과 같은 추가적인 변수 없이 바로 값을 비교할 수 있다.

  • A[i] + A[j] > M : 두 값을 더한게 M보다 크므로 큰 쪽 인덱스를 줄인다.
  • A[i] + A[j] < M : 두 값을 더한게 M보다 작으므로 작은 쪽 인덱스를 올린다.
  • A[i] + A[j] == M : cnt를 올리고 큰 쪽 작은 쪽 인덱스 모두 가운데로 모이게 한다.

 

💡배운 점

  • 리스트 끝 인덱스 N-1
  • 양

 

좋은 수 (좋다 - 1253)

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1 

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 

8

 

1️⃣ 분석

주어진 수들 중 다른 두 수의 합으로 이루어진 수가 있으면 그 수는 좋은 수다. 여기서 헷갈렸던 건 a + b = c 인 상황인건지, a + b = c일 때 a = c or b = c가 가능한거지 궁금했다. 문제에선 설명이 모호했기에 넘어갔고 여러 번의 실패끝에 전자임을 확인했다. 

 

2️⃣ 손으로 풀어보기

 

어떤 구조로 코드를 작성해야 할지 고민될 땐 시간복잡도를 근거로 판단하면 좋다. 문제에선 2초의 제한 시간을 둔다. 4천만번의 연산을 받아들일 수 있다. 여러가지의 경우의 수를 생각해 볼 수 있는데,

 

  • 리스트에서 한 수를 뽑고 N, 두 수의 조합을 직접 찾는 경우 N * N => O(N^3)
    • N^3은 4천만을 넘어가 안된다.
  • 리스트에서 한 수를 뽑고 N, 투포인터를 사용하는 경우 N + N => O(N^2)
    • 이건 된다. for문 안에 while문을 넣어도 시간 초과가 나지 않는다.

 

3️⃣ 슈도 코드

 

여기서 작성한 코드는 오류가 있다. 밑에서 설명하겠다.

 

4️⃣ 실제 코드 작성

import sys
input = sys.stdin.readline
N = int(input())
A = sorted(list(map(int, input().split())))
cnt = 0

for n in A:
    i = 0
    j = N-1
    while i < j:
        if A[i] + A[j] > n:
            j -= 1
        elif A[i] + A[j] < n:
            i += 1
        elif A[i] + A[j] == n:
            cnt += 1
            break
            
print(cnt)

이 코드가 안되는 이유는 a + b = c를 따라야 하기 때문이다. 전성준 다녀감.

예를 들어 [0, 5, 5]를 입력하면 좋은 수는 0이다. 0 + 5 = 5이기 때문이다. 이걸 고려하여 다음 코드를 짰다.

 

import sys
input = sys.stdin.readline
N = int(input())
A = sorted(list(map(int, input().split())))
cnt = 0

for n in A:
    i = 0
    j = N-1
    while i < j:
        if A[i] + A[j] > n:
            j -= 1
        elif A[i] + A[j] < n:
            i += 1
        elif A[i] + A[j] == n:
            if A[i] != n or A[j] != n:
                cnt += 1
                break
            elif A[i] == n:
                i += 1
            elif A[j] == n:
                j -= 1
            
print(cnt)

A[i]와 A[j]가 n과 같을 때를 찾아서 따로 처리했다. 문제는 조건문의 or가 아닌 and가 들어가야 했다. Inspection을 통해 이를 찾아냈기 때문에 이 또한 기록해 둔다. (Inspection은 코드의 로직 중 오류를 찾는데 좋은 방법이다.)

or를 and로 바꾼다고 해도 이 방법이 안되는 이유는 문제의 조건을 따르지 않았기 때문이다. 문제에선 수가 같지만 자리가 다르면 다른 수라 했다.

예를 들어 [-5 0 5 5]를 입력한 경우 답은 4이다. -5 + 5 = 0 2개와 0 + 5 = 5 2개이기 때문이다. 리스트의 원소를 가져오면 안되고 인덱스로 원소를 가져오고 위치에 대한 조건을 달아야 한다.

 

import sys
input = sys.stdin.readline
N = int(input())
A = sorted(list(map(int, input().split())))
cnt = 0

for k in range(N):
    i = 0
    j = N - 1
    while i < j:
        if A[i] + A[j] == A[k]:
            if i != k and j != k:
                cnt += 1
                break
            elif i == k:
                i += 1
            elif j == k:
                j -= 1
        elif A[i] + A[j] > A[k]:
            j -= 1
        elif A[i] + A[j] < A[k]:
            i += 1   

print(cnt)

 

💡배운 점

  • 시간복잡도에 따른 알고리즘 선택 방법
  • 인덱스로 리스트 원소 가져오기, 값이 아닌 위치에 따른 원소 판단
  • Inspection으로 코드 로직 오류 찾기

'Algorithm' 카테고리의 다른 글

[Do it 알고리즘 코딩테스트] 3-5. 스택과 큐  (0) 2025.09.08
[Do it 알고리즘 코딩테스트] 3-4. 슬라이딩 윈도우  (0) 2025.08.13
[Do it 알고리즘 코딩 테스트] 3-2. 구간 합  (0) 2025.08.07
[Do it 알고리즘 코딩 테스트] 3-1. 배열과 리스트  (0) 2025.08.06
[Do it 알고리즘 코딩 테스트] 2. 디버깅  (0) 2025.08.05

티스토리툴바