투 포인터 ✔

이론 ✌

1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 것을 얻는 형태이다. 이 때문에 투 포인터 알고리즘으로 불린다.

N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트 해보면 구간 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이므로 시간초과를 얻게 된다.

예시 🔽

원소가 순서대로 N 이하 자연수 배열의 끝 까지 탐색하면서 합이 N이 될 경우의 수를 구합니다. start가 한 칸 이동하는 것은 구간에서 왼쪽 칸을 삭제하는 효과가 있고, end가 한 칸 이동하는 것은 구간에서 구간을 한 칸더 확장 시킨다는 효과가 있습니다. 같을 때는 경우의 수를 1 증가시키고, 구간을 확장할려고 end를 한 칸 이동시킵니다.

1. 먼저 포인터 2개 start, end를 준비한다. start는 앞 쪽, end는 뒤쪽의 인덱스이다

2. (start, end) 구간의 합을 저장 할 sum을 준비한다.

3. 이동원칙을 준수한다.

sum > N : sum -= start, start += 1
sum < N : end += 1, sum += end
sum == N : count += 1, end += 1, sum += end

---

N이하의 자연수 순서대로 이루어진 배열은 아니지만 그림 설명이 쉬울 것 같아서 퍼왔습니다.

Ex) M = 5인 경우를 살펴보자.

초기 상태이며, 빨간색 포인터 : start, 파란색 포인터 : end이다. S : 합.

end가 뒤로 움직일 때는 새로 포함한 원소를 S에 더하고, start가 뒤로 움직일 때는 새로 넘긴 원소를 S에서 빼는 식으로 현재 [start, end)의 합 S를 매번 쉽게 구할 수 있다.

처음에는 이렇게 end만 증가하게 된다. S가 계속 M보다 작기 때문! 마지막엔 S>=M이 되었으므로 아래와 같다.

start를 한 칸 옮겼는데, 동시에 S = 5인 경우를 만났다. 이때 결과를 1 증가시켜 준다.

이런 식으로 포인터들이 움직이게 된다. 여기서 2번째로 S = 5인 지점을 만났으므로 결과를 1 증가시켜 준다.

그 직후, start가 1 증가하면서 start = end인 경우가 나온다.

계속 가다 보면 세 번째로 S = 5인 지점을 만난다.

그 이후 조건에 맞춰 포인터를 증가시키다 보면, end가 배열 끝을 가리키게 되어 더이상 증가할 수 없는 상태가 된다.

그렇게 되면 그냥 start만 증가시켜 가다가 start 역시 배열 끝에 다다르면 종료해도 되고, 그냥 그 자리에서 루프를 끝내버려도 된다. 이렇게 해서 S = 5인 경우는 3개 발견되었다.

그림설명링크

---

백준 - 2018(수들의 합) 1️⃣

문제 설명

어떠한 자연수 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을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

풀이 🔓

위 설명과 같음

코드 📃

n = int(input())

start = 1
end = 1
s = 1
cnt = 0
# end가 n이라는 것은 끝에 도달
# 끝에 도달 한 경우는 남아 있는 start에서 end 까지 구간의 합이
# n보다 작다는 소리니깐 즉시 종료해줘도 됨
while end != n:
  # 현재 구간에서 한 칸 확장
  # 확장을 하고 확장된 칸을 더해줘야 의미가 있음
  if s < n:
    end+=1
    s+=end
  # 현재 구간에서 한 칸 삭제
  # 먼저 현재 구간에서 한 칸을 삭제해야 앞부분이 변경되는 효과
  elif s > n:
    s-=start
    start+=1
  else:
    cnt += 1
    end+=1
    s+=end

# 마지막 n은 무조건 포함이 되어야 하므로
print(cnt+1)

---

백준 - 1940(주몽) 2️⃣

문제 설명

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

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 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. 배열을 정렬한다. O(nlogn)
2. 배열의 처음과 끝의 인덱스를 s, e로 초기화 한다
3. s를 한 칸 증가시키고(값이 증가), e를 한 칸 감소시키며(값이 감소) 구간을 좁혀간다
4. s와 e가 만나는 지점은 투 포인트가 아니라 원 포인트이기 때문에 종료조건이다.

코드 📃

n = int(input())
m = int(input())
arr = list(map(int, input().split()))
arr.sort()

s = 0 # 가장 작은 쪽 초기화
e = n-1 # 가장 큰 쪽 초기화
cnt = 0
while s < e:
  if arr[s] + arr[e] == m:
    cnt+=1
    s += 1 # 배열의 요소들은 고유한 수이기 때문에 둘 중 하나만 위치를
    e -= 1 # 조정 한다고 해서 다시 m이 나올 수 없기 때문에 둘 다 위치를 바꿔줌
  elif arr[s] + arr[e] < m:
    s+=1
  else:
    e-=1

print(cnt)

---

백준 - 1253(좋다) 3️⃣

문제 설명

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

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

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

입력

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

출력

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

풀이 🔓

1. 배열을 s를 오름차순으로 이동, e를 내림차순으로 이동할려고 정렬을 했다. O(nlogn)

2. N개의 수 중 좋은 수를 체크 하기 위하여 N개의 수를 모두 탐색한다

• s를 첫 번째, e를 마지막 인덱스로 초기화
• s 인덱스 값과, e 인덱스 값의 합이 타겟인 i값 보다 작으면 s 인덱스를 증가, i값 보다 크면 e 인덱스를 감소, 타겟과 같으면 반복문을 빠져나와서 해당 타겟값은 좋은 수라고 판단
• 이때 타겟값과 같은 부분을 s 나 e 인덱스가 가리키면 해당 인덱스를 증가 또는 감소해서 그냥 지나감

코드 📃

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

cnt = 0
for idx ,i in enumerate(arr):
  s = 0
  e = n-1
  flag = 0
  while s < e:
    if idx == s:
      s+=1
      continue
    if idx == e:
      e-=1
      continue

    if arr[s] + arr[e] > i:
      e-=1
    elif arr[s] + arr[e] < i:
      s+=1
    else:
      flag = 1
      break

  if flag :
    cnt += 1
print(cnt)

---

알아둘 것 🎉

일단 s나 e를 조정했을 때 값이 증가나 감소가 일어날 수 있도록 설정해야함 그래서 나는 두 수의 합을 이용하여 어떤 수를 얻어내는 문제에서 정렬을 사용하여 s를 증가하도록 맨 앞에서 부터 오름차순으로 가게 하였고, e를 내림차순으로 가게 만들어줬음