[Do it! 알고리즘 코딩 테스트 자바] 투 포인터 - 백준 2018, 1940, 1253번 (4일차)

투 포인터: 2개의 포인터로 알고리즘의 시간 복잡도를 최적화

 

전제

데이터 정렬: 특정 인덱스를 옮겼을 때 결과의 변화가 불규칙하다면 투 포인터 적용이 불가능함.

 

이동 원칙

- A[start_index] + A[end_index] > target: end_index--;

- A[start_index] + A[end_index] < target: start_index++;

- A[start_index] + A[end_index] == target: start_index++; end_index--; count++;

 

결론

- 시간 복잡도: 중첩 반복문 O(N^2)의 작업을 배열을 한 번 훑는 O(N)의 속도로 최적화함. (정렬 시간을 포함할 경우 O(N log N)

- 공간 복잡도: 별도의 대규모 메모리 할당 없이 변수 두 개(포인터)만으로 탐색이 가능하여 메모리 효율성이 극대화됨

- 포인터 선택:

   문제의 조건(두 수의 합인지, 연속된 구간의 합인지)에 따라 적절한 이동 방식 선택이 관건임.

   1. 양 끝에서 서로를 향해 이동 

   정렬된 배열에서 두 요소의 조합을 찾을 때 주로 사용함.

• 초기 위치: 하나는 왼쪽 끝(0), 하나는 오른쪽 끝(N-1).
• 이동 원리: 합이 크면 오른쪽 포인터를 줄이고, 합이 작으면 왼쪽 포인터를 늘림.

   2. 같은 방향으로 함께 이동

   주로 연속된 구간의 합이나 길이를 구할 때 사용하며, '슬라이딩 윈도우'와 유사한 형태임.

• 초기 위치: 두 포인터 모두 배열의 시작점(0 또는 1)에서 출발.
• 이동 원리:
  • 오른쪽 포인터(End): 조건에 미달할 때 구간을 확장하며 전진.
  • 왼쪽 포인터(Start): 조건에 도달하거나 초과할 때 구간을 축소하며 추격.

 

 

---

백준 2018번 (수들의 합 5)

1. 주요 오개념 및 시행착오 (Pain Point)

• 1부터 N까지의 숫자를 저장하기 위해 배열을 선언하여 메모리 초과(Memory Limit Exceeded) 발생.
• N의 최대치(10,000,000)를 고려하지 않은 데이터 구조 선택.
• long[] A = new long[N]을 선언하면, 8바이트(long) * 10,000,000개 = 약 80MB의 메모리를 사용.
• 보통 이 문제의 메모리 제한은 32MB~128MB 사이인데, Java의 기본 메모리 오버헤드까지 합쳐지면 제한을 넘김.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 연속된 자연수의 합은 시작점과 끝점의 위치에 따라 결정됨.
• 투 포인터(Two Pointers) 이동에 따른 구간 합의 단조 증가/감소 성질 활용.

3. 설계 통찰

• 연속된 숫자의 값 자체가 인덱스와 동일하므로 별도의 배열 저장 생략 가능.
• 메모리 사용량을 O(N)에서 O(1)로 극단적으로 줄이는 접근법.

4. 구현상의 유의점 (Implementation Wisdom)

• startIndex와 endIndex를 1부터 시작하여 N에 도달할 때까지 반복 처리.
• N 자체도 하나의 가짓수로 포함해야 하므로 초기 count를 1로 설정하거나 반복 조건 세밀화.

---

백준 1940번 (주몽)

1. 주요 오개념 및 시행착오 (Pain Point)

• 정렬되지 않은 상태에서 투 포인터를 적용하거나 무리하게 중첩 반복문 사용.
• 인덱스 초기화 과정에서 startIndex + 1 등의 수동 조작으로 인한 배열 범위 초과(ArrayIndexOutOfBounds) 에러 발생.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 배열을 정렬하면 양 끝 포인터의 합을 목표값(M)과 비교하여 탐색 범위를 이진적으로 축소 가능.
• 정렬 시간 복잡도 O(N log N)과 투 포인터 탐색 O(N)의 결합.

3. 설계 통찰

• 두 수의 합을 찾을 때는 양 끝에서 중앙으로 모이는 투 포인터 형식이 가장 효율적임.
• 정렬은 탐색의 방향성을 결정하는 필수 전제 조건임.

4. 구현상의 유의점 (Implementation Wisdom)

• while (i < j) 조건을 통해 포인터 역전 및 인덱스 월담 방지.
• 입력 데이터가 여러 줄에 걸쳐 들어오는 경우 StringTokenizer와 readLine()의 적절한 호출 횟수 확인.

---

백준 1253번 (좋다)

1. 주요 오개념 및 시행착오 (Pain Point)

• '다른 두 수의 합'이라는 조건에서 자기 자신(Target Index)을 포함해버리는 오류.
• 음수와 0이 포함된 경우를 간과하여 탐색 범위를 target 이전으로만 한정하는 실수.

2. 핵심 원리 및 수학적 근거 (Logic & Math)

• 모든 인덱스 i에 대해 각각 투 포인터 탐색을 수행하는 O(N^2) 로직.
• 0이나 음수가 있을 경우, 자신보다 큰 인덱스의 값을 더해서 자신이 나올 수 있음을 인지.

3. 설계 통찰

• 값의 중복 여부보다 인덱스의 중복(자기 참조) 여부가 문제 해결의 열쇠임.
• 하나라도 조합을 찾으면 즉시 해당 숫자에 대한 탐색을 종료(break)하여 효율성 제고.

4. 구현상의 유의점 (Implementation Wisdom)

• sum == target일 때 start_index == i 또는 end_index == i인 경우 포인터만 한 칸 옮기고 탐색 지속.
• long 타입을 사용하여 합계 계산 시 발생할 수 있는 오버플로우 사전 차단.