투포인터 처음 보는데 어렵네_[python_파이썬_Fail]백준_2003번_수들의 합_투포인터 개념 설명_풀이

공부하는허딩크 : https://www.youtube.com/live/dnKTEnrL2OM?feature=shared

 

처음 문제를 보고 itertools를 생각했다. 이 전에 백트레킹을 공부하면서 itertools를 계속 봐서 그런지는 모르겠지만, 수열이란 단어를 보고 모든 수열을 뽑아서 더해보면 될 것이라고 생각했다.

 

<첫번째 시도 : 포기함>

예를 들면 itertools로 하면 (1, 2), (1, 3) 이런 조합도 가능하다. 단, 문제의 조건은 연속된 수들의 합이므로 (1, 3)의 조건은 불가능하다. 즉, 정답이 더욱 커진다.

즉. itertools로는 불가능하다는 이야기가 나온다. 만약 나온 조합이 연속되지 않은 조건을 추가적으로 걸면 가능하겠지만

굳이 그럴 필요 없이 다른 방법을 찾아봤다.

itertools로 하려고 했으나 이건 아닌것 같음

i ~ j번째가 연속적으로 나와야 하는데 itertools는 i, i + 1도 나오지만 i, i + 2도 나옴 => 이건 안됨.

N, M = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

for i in range(N):

  num = list(j for j in itertools.combinations(nums, i + 1))

  for k in num:

    if sum(k) == M:

      cnt += 1

print(cnt)

 

<두번째 시도 : 시간초과>

일단 해당 코드의 방향성은 맞을 것 같다.

브루트포스 알고리즘 형식으로 모든 경우의 수를 구해서 다 더해주면 답이 나올 것 같았는데 아니네... 

#N개의 수열,i번째 수~j번째 수까지 합이 M이 되는 경우의 수

import sys

import itertools

input = sys.stdin.readline

N, M = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

for i in range(N):

    sum_check = nums[i]

    for j in range(i + 1, N):

        sum_check += nums[j]

    #print("i = ", i, "nums[i] = ", nums[i], "j = ", j, "nums[j] = ", nums[j], "sum_check = ", sum_check)

        if sum_check == M:

            cnt += 1

print(cnt)

 

<세번째 시도 : 시간초과>

수열의 개수가 1개일때 조건을 추가해서 cnt를 정했다.

일단 파이썬에서 돌렸을때 정답은 나오는데 시간초과가 나온다.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

for i in range(N):

    sum_check = nums[i]

    if sum_check == M:

        cnt += 1

    for j in range(i + 1, N):

        sum_check += nums[j]

        #print("i = ", i, "nums[i] = ", nums[i], "j = ", j, "nums[j] = ", nums[j], "sum_check = ", sum_check)

        if sum_check == M:

            cnt += 1

print(cnt)

 

<네번째 시도 : 시간초과>

이중for문을 사용하는게 문제인 것 같다. 그냥 코드를 짧게 만들었을 뿐... 별로 달라진건 없다...

두번째 for문에서 N + 1을 N으로 바꿔줘야 하는거 아닌가;;;; but, 어차피 둘다 시간초과.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

for i in range(N):

    for j in range(i + 1, N + 1):

        if sum(nums[i:j]) == M:

            cnt += 1

print(cnt)

 

<다섯번째 시도 : 투포인터 알고리즘 설명 찾아보고 왓음_아직 잘 이해가 안감....>

투포인터는 start(0)와 end(N-1)로 2개의 포인터를 잡고 구하려는 값과 비교해서 start + 1, end -1을 해주면서 합의 변화를 누적하면서 구간을 조정해 나가는 방식이다. 

 

이것도 틀렸다고 나오네..... 뭐지;;;;

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

nums = list(map(int, input().split()))

cnt = 0

start = 0

end = 0

temp_sum = 0

while end < N:

    if temp_sum < M:

        temp_sum += nums[end]

        end += 1

    elif temp_sum > M:

        temp_sum -= nums[start]

        start += 1

    else:

        cnt += 1

        temp_sum -= nums[start]

        start += 1

print(cnt)

 

 

<Chat GPT 설명 : 천천히 읽어보면 조금씩 윤곽이 보인다.>

핵심 개념

투 포인터는 두 개의 포인터(인덱스)를 사용해서 한 번에 하나씩 배열의 구간을 움직이면서 그 구간의 합을 관리합니다. 이 방식은 매번 새로운 구간의 합을 처음부터 계산하지 않고, 이미 계산된 구간을 확장하거나 줄여가면서 합을 유지하기 때문에 전체 구간을 효율적으로 탐색합니다.

목표: 연속된 수열의 합이 M이 되는 구간 찾기

1. 배열에 두 포인터를 배치
   • start와 end라는 두 개의 포인터를 배열의 처음에 배치합니다. 이 두 포인터는 배열의 구간을 나타냅니다. 초기 상태에서 두 포인터는 같은 위치를 가리킵니다.
    

   nums = [1, 2, 3, 4, 5] start = 0, end = 0 current_sum = 0
2. end를 증가시키며 부분합을 늘려감
   • end 포인터는 배열에서 구간의 끝을 나타내며, end 포인터를 한 칸씩 오른쪽으로 이동하면서 부분합을 늘려갑니다.
   첫 번째 반복:두 번째 반복:세 번째 반복:이렇게 end 포인터가 오른쪽으로 이동할 때마다 새로운 값을 더해가면서 부분합을 계산합니다. 이렇게 하면 start에서 end까지의 연속된 수열의 합을 유지할 수 있습니다.
3. 첫번째 반복
   start = 0, end = 2, current_sum = 1 + 2 + 3 = 6 (nums[0] + nums[1] + nums[2])
4. 두번째 반복
   start = 0, end = 1, current_sum = 1 + 2 = 3 (nums[0] + nums[1])
5. 세번째 반복
   start = 0, end = 0, current_sum = 1 (nums[0])
6. 부분합이 M보다 크거나 같으면 start를 증가시키며 구간을 줄임
   • 만약 현재 current_sum이 목표값인 M보다 크다면, 구간을 줄여야 합니다. 이때 start 포인터를 오른쪽으로 이동시키며 구간의 크기를 줄이고, 그에 따라 합도 줄어듭니다.
   예를 들어, current_sum = 6인데 목표값 M = 5라면 start 포인터를 오른쪽으로 옮깁니다:이제 current_sum이 5가 되어 목표값을 찾았습니다. 이때 카운트를 1 증가시키고, 다시 구간을 이동해 다음 구간을 찾습니다.
7.  
   start = 1, end = 2, current_sum = 6 - nums[0] = 5
8. 모든 구간을 확인
   • start 포인터가 이동할 때마다 구간의 시작이 바뀌고, end 포인터가 움직일 때마다 구간의 끝이 바뀝니다. 이런 방식으로 start와 end 두 포인터는 배열의 모든 구간을 한 번씩 거칩니다. 배열의 처음부터 끝까지 모든 연속된 수열을 확인하게 됩니다.

투 포인터가 배열의 모든 수열을 확인하는 이유

투 포인터는 배열에서 모든 구간을 확인하게 됩니다. 아래는 투 포인터 알고리즘의 각 단계에서 어떻게 모든 구간을 확인하는지를 더 자세히 설명한 것입니다.

1. start는 처음엔 배열의 첫 번째 인덱스(0)에 있고, end는 start와 함께 움직이면서 구간을 확장해 나갑니다.
2. current_sum이 목표값보다 크다면 start를 오른쪽으로 한 칸씩 이동해 구간을 줄여 나갑니다.
3. 이렇게 하면 start와 end의 조합을 통해 배열의 모든 연속된 부분합을 효율적으로 탐색하게 됩니다.

직관적인 이해

만약 배열이 [1, 2, 3, 4, 5]이고 목표 합이 5라고 하면, 투 포인터는 다음과 같이 배열의 모든 연속된 부분합을 탐색합니다:

1. start = 0, end = 0: 부분합 1
2. start = 0, end = 1: 부분합 1 + 2 = 3
3. start = 0, end = 2: 부분합 1 + 2 + 3 = 6 (여기서 start를 이동해 구간 축소)
4. start = 1, end = 2: 부분합 2 + 3 = 5 (목표값 달성)
5. start = 1, end = 3: 부분합 2 + 3 + 4 = 9 (다시 start 이동)

이런 식으로 모든 가능성 있는 구간을 확인하게 됩니다.

요약

• start와 end 포인터는 배열의 한 구간을 나타냅니다.
• end를 이동시키면서 구간을 확장하고, start를 이동시키면서 구간을 축소합니다.
• 구간을 확장하고 축소하는 과정에서 모든 구간을 확인하게 됩니다.
• 이 방법을 사용하면 O(N) 시간 복잡도로 배열의 연속된 수열의 합을 효율적으로 찾을 수 있습니다.

<추가 시도 : 맞았습니다.>

와... 이런 알고리즘이 너무 생소하니까 이해하는데 조금 오래 걸린다. 

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

nums = list(map(int, input().split()))

start, end = 0, 1

cnt = 0

while start <= N and end <= N:

    tsum = sum(nums[start:end])

    if tsum == M:

        cnt += 1

        end += 1

    elif tsum < M:

        end += 1

    else:

        start += 1

       

print(cnt)

   

"""

0,

1. start = 0, end = 1일때, tsum = 1

tsum < M이므로 start = 0, end = 2

==> nums[0]

2. start = 0, end = 2일때, tsum = 2

tsum == M이므로 cnt = 1, start = 0, end = 3

==> nums[0] + nums[1]

3. start = 0, end = 3일때, tsum = 3

tsum > M이르모 start 1, end = 3

==> nums[0] + snums[1] + nums[2]

4. start = 1, end = 3일때 tsum = 2

tsum == M이므로 cnt = 2, start = 1, end = 4

==> nums[1] + nums[2]

5. start = 1, end = 4일때, tsum = 3

tsum > M이므로 start = 2, end = 4

==> nums[1] + nums[2] + nums[3]

6. start = 2, end = 4일때, tsum = 2

tsum == M이므로 cnt = 3, start = 2, end = 5

==> nums[2] + nums[3]

"""

 

<추가 실패>

투포인터를 사용해서 진행을 했는데 아래와 같이 마지막 index가 계속 + 1이 되어 에러가 난다.

# while end < N:

#     if temp_sum < M:

#         temp_sum += nums[end]

#         end += 1

#     elif temp_sum == M:

#         cnt += 1

#         temp_sum -= nums[start]

#         start += 1

#     else:

#         temp_sum -= nums[start]

#         start += 1

       

# print(cnt)

"""

1. start = 0, end = 0에서 시작

    temp_sum < M이 참, temp_sum = 1 (nums[0])

                        end = 1

2. start = 0, end = 1에서 시작

    temp_sum < M이 참, temp_sum = 2 (nums[0] + nums[1])

                        end = 2

3. start = 0, end = 2에서 시작

    temp_sum == M이 참, cnt = 1

                        temp_sum = 1 (nums[1])

                        start = 1

4. start = 1, end = 2에서 시작

    temp_sum < M이 참, temp_sum = 2 (nums[1] + nums[2])

                        end = 3

5. start = 1, end = 3에서 시작

    temp_sum == M이 참, cnt = 2

                        temp_sum = 1(nums[2])

                        start = 2

5. start = 2, end = 3에서 시작

    temp_sum < M이 참, temp_sum = 2(nums[2] + nums[3])

                        end = 4?? 이거 indexError

 

<추가 실패_수정>

음..... 힘드네.... 아 코딩 포기하고 싶다... 1년 넘게 공부한 내 500시간이 아까워서 내가 포기 못한다.

while조건을 start < N:으로 하고 if조건에서 end < N을 줘서 indexerror가 나오지 않게 했다.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

nums = list(map(int, input().split()))

start, end = 0, 0

temp_sum = 0

cnt = 0

while start < N:

    if temp_sum < M and end < N:

        temp_sum += nums[end]

        end += 1

    elif temp_sum == M:

        cnt += 1

        temp_sum -= nums[start]

        start += 1

    else:

        temp_sum -= nums[start]

        start += 1

       

print(cnt)

 

<정답 체크 : 브루트포스처럼 가능성 없는 수열을 다 더하는 것이 아닌 M의 조건에 따라서 index가 움직이게 하는 방법이네.>

10 5
1 2 3 4 2 5 3 1 1 2

0 1 2 3 4 5 6 7 8 9
start =  0 end =  0 temp_sum =  0
start =  0 end =  1 temp_sum =  1 => nums[0]
start =  0 end =  2 temp_sum =  3 => nums[0] + nums[1]
start =  0 end =  3 temp_sum =  6 => nums[0] + nums[1] + nums[2]
start =  1 end =  3 temp_sum =  5 => nums[1] + nums[2]
start =  2 end =  3 temp_sum =  3 => nums[2]
start =  2 end =  4 temp_sum =  7 => nums[2] + nums[3]
start =  3 end =  4 temp_sum =  4 => nums[3]
start =  3 end =  5 temp_sum =  6 => nums[3] + nums[4]
start =  4 end =  5 temp_sum =  2 => nums[4]
start =  4 end =  6 temp_sum =  7 => nums[4] + nums[5]
start =  5 end =  6 temp_sum =  5 => nums[5]
start =  6 end =  6 temp_sum =  0 => 없음
start =  6 end =  7 temp_sum =  3 => nums[6]
start =  6 end =  8 temp_sum =  4 => nums[6] + nums[7]
start =  6 end =  9 temp_sum =  5 => nums[6] + nums[7] + nums[8]
start =  7 end =  9 temp_sum =  2 => nums[7] + nums[8]
start =  7 end =  10 temp_sum =  4 => nums[7] + nums[8] + nums[9]
start =  8 end =  10 temp_sum =  3 => nums[8] + nums[9]
start =  9 end =  10 temp_sum =  2 => nums[9]

               ※ end = 10일때 if조건이 거직이니까 else:로 넘어가서 nums[start]가 빠지고, start + 1을 계속 하는거지.

                   그리고 start = 10이 될 때 while문 탈출.

<Chat GPT 도와줘>

맞습니다! 이 코드는 완전 탐색(브루트포스, Brute-force) 방식처럼 모든 부분 수열을 다 확인하는 방식이 아니라, 투 포인터(Two Pointers) 알고리즘을 사용하여 더 효율적으로 문제를 해결하고 있습니다.

차이점

1. 브루트포스 알고리즘:
   • 모든 가능한 부분 수열을 하나하나 다 확인하는 방식입니다.
   • 예를 들어, 배열이 [1, 2, 3, 4]라면 모든 시작점과 끝점을 선택해 가능한 모든 부분 수열을 다 계산해 봅니다.
   • 이 방법은 시간 복잡도가 O(N^2)에 가깝습니다. 즉, 배열의 크기가 커질수록 모든 부분 수열을 확인해야 하기 때문에 비효율적입니다.
2. 투 포인터 알고리즘:
   • 투 포인터는 배열의 구간을 start와 end라는 두 개의 포인터로 관리하면서 부분 수열의 합을 구합니다.
   • 합이 작으면 end를 증가시켜 더 큰 부분 수열을 만들고, 합이 크면 start를 증가시켜 부분 수열을 줄이는 방식입니다.
   • 이 방법은 시간 복잡도가 O(N)입니다. 배열을 한 번 순회하면서 필요한 부분 수열만 찾기 때문에 훨씬 더 효율적입니다.

투 포인터 알고리즘의 특징

• 불필요한 계산을 줄임: 합이 목표값 M보다 작으면 end를 늘리고, 크면 start를 늘리면서 유연하게 부분 수열을 조정합니다. 이렇게 함으로써 모든 부분 수열을 확인할 필요 없이 원하는 합을 효율적으로 찾아낼 수 있습니다.
• 효율성: 이 방법은 배열의 크기가 커져도 비교적 빠르게 답을 찾을 수 있습니다. start와 end가 한 방향으로만 이동하므로 배열을 한번만 훑게 됩니다.

정리

• 브루트포스는 모든 경우의 수를 하나하나 다 확인하는 방식으로 비효율적입니다.
• 투 포인터는 두 개의 포인터를 이용해 구간을 조절하면서 원하는 조건에 맞는 부분 수열을 효율적으로 찾아내는 방식으로, 이 코드에서 사용된 알고리즘입니다.

따라서 이 코드는 모든 수열을 확인하는 브루트포스 방식이 아니라, 더 적은 연산으로 답을 찾아낼 수 있는 투 포인터 방식을 사용한 것입니다.