Two Pointers 기법이란? (Why / When / How to use)

Two Pointers?

리트코드 알고리즘 문제에서 정~말 많이 사용되는 유형으로, 보통 데이터 구조가 선형 구조이고, 데이터의 연산이 두 개의 포인터를 가지고 연속적으로 해야할 때 사용된다. 대표적인 유형으로는 Two Sum이 있다. ㅎ

투 포인터 기법을 쓰는 이유는 뭣보다도 시공간 복잡도가 O(N)에 처리될 수 있는 장점때문이다.

이 말고도 문자열이 palindrome인지 구분할때에도 쓸 수 있고, 더 많은 전형적인 유형들은 아래에서 다루어볼 것이다.

 

 

In Real-World Problems

대학교에서는 알고리즘에 관하여 이렇게는 안알려주는 것 같은데, 이것이 왜 필요한 기법인지 납득이 가야지만 알고리즘을 잘 활용하는 나같은 유형의 경우 이걸 좀더 일찍 알았더라면~ 하는 아쉬움은 있다.

따라서 무작정 '알고리즘 문제 풀이'를 위한 테크닉을 공부하지 말고 이 기법이 왜 많이 출제되는지 알아야 아~ 하고 이 기법의 활용도와 중요성에 대해 단번에 파악이 가능할 것이다. (따라서 앞으로도 많이 찾아보길 나자신에게 바란다.)

내가 교수님이어도 너무나 기본적인 지식이지만 문제 풀이 유형용 알고리즘 기법인 투포인터에 대해서는 수업 시간에 굳이 언급할 필요가 없을 듯 하다.

 

서론이 길었고, 실제로 투포인터 기법은 메모리 관리에 사용되는 아주 필수적인 테크닉이라 할 수 있다. (이제 본론도 길어질 예정)

 

• The memory pool is initialized with two pointers: the start pointer, pointing to the beginning of the available memory block, and the end pointer, indicating the end of the block. When a process or data structure requests memory allocation, the start pointer is moved forward, designating a new memory block for allocation. Conversely, when memory is released (deallocated), the start pointer is shifted backward, marking the deallocated memory as available for future allocations. The end pointer remains fixed, acting as a safeguard against errors like overlapping allocations.

 

즉,

메모리 할당과 비할당에 필요한 필수적인 패턴인데, 메모리 풀이 처음에 투포인터(start 포인터-사용 가능한 메모리 블럭의 처음 시작점을 가리킴 / end 포인터-블록의 마지막점을 가리킴)로 초기화된다.

 

만일 프로세스 혹은 자료구조가 메모리 할당을 요청할 경우, start 포인터는 새로운 메모리 블럭을 할당해주면서 앞(높은 주소)으로 이동하며 새 메모리를 할당 반대로 만약 메모리가 해제(비할당)되면 start 포인터는 방금 비할당된 메모리를 사용 가능한 메모리 공간으로 확보하기 위해 뒤로 옮겨지게 된다. 

end 포인터는 항상 고정된 상태로 있는데, 중복할당과 같은 에러들을 방지하기 위한 safeguard로 역할하게 된다.

---

여기서 잠깐...!

📌 왜 높은 주소가 "앞쪽"이라고 표현하는가? -> 💡 주소값이 증가하는 방향을 "앞쪽"으로 간다고 표현하기 때문

• 메모리는 주소가 0x0000부터 0xFFFF까지 선형적인 증가 구조
• Heap의 start pointer는 메모리를 할당할수록 높은 주소로 이동(증가)
• 따라서, Heap에서 "앞쪽으로 이동"한다는 것은 높은 주소로 이동하는 것과 같음

 

보통 heap 영역에서 메모리는 낮은 주소에서 높은 주소로 할당되므로, start pointer는 앞쪽(높은 주소)으로 이동된다.

(메모리의 주소가 높은 주소가 "앞쪽"에 놓여 있는 이유는 CPU의 아키텍처와 메모리 배치 방식 때문인데, 운체나 시스템 프로그래밍을 배웠다면 메모리 주소는 0부터 시작해서 점점 증가한다는 것을 배웠을거다.)

+----------------------+
|  낮은 주소 (0x0000)  | ← 작은 숫자의 주소 (예: 코드 영역, 데이터)
|                      |
|                      |
|  높은 주소 (0xFFFF)  | ← 큰 숫자의 주소 (예: Heap, Stack)
+----------------------+

즉, 주소값이 증가할수록 물리적으로 "앞쪽"에 있는 것처럼 표현할 수 있다.

 

운영체제는 프로세스마다 일정한 메모리 공간을 할당하는데, 일반적으로 다음과 같이 구성된다.

+----------------------+
|  Stack  (높은 주소)    |  ⬆️ 주소 감소 (Push 시 아래 방향)
|                      |
|                      |
|  ↓↓↓↓ 성장 방향 ↓↓↓↓   |
|                      |
|  Heap  (낮은 주소)     |  ⬇️ 주소 증가 (새 할당 시 위 방향)
+----------------------+
|  Data Section        |
|  Code Section        |
|  (낮은 주소)           |
+----------------------+

 

반대로 Stack은 높은 주소 → 낮은 주소로 감소하므로 Stack Pointer는 뒤쪽(낮은 주소 방향)으로 이동한다는 표현을 쓴다.

 

 

📌 Heap과 Stack의 차이점

• Heap: 낮은 주소에서 시작해서 높은 주소로 커짐
  → 즉, 새 메모리를 할당할수록 start pointer는 앞(높은 주소)으로 이동
• Stack: 높은 주소에서 시작해서 낮은 주소로 줄어듦
  → 즉, 데이터를 push할수록 Stack Pointer는 뒤(낮은 주소)로 이동

---

아무튼 투포인터 패턴이 적용되려면, 아래와 같은 세 조건을 만족해야 한다.

• 선형 자료구조 (배열, 연결리스트, 문자열)
• 프로세스 페어 (두 개의 다른 포지션이 연속적으로 계속 데이터 연산 처리가 되어야한다.)
• 동적 포인터 움직임 (특정 조건이나 기준에 따라 두 포인터가 독립적으로 움직이고, 두 포인터는 같거나 각기 다른 자료구조를 가질 수 있다.)

 

• Linear data structure: The input data can be traversed in a linear fashion, such as an array, linked list, or string.
• Process pairs: Process data elements at two different positions simultaneously.
• Dynamic pointer movement: Both pointers move independently of each other according to certain conditions or criteria. In addition, both pointers might move along the same or two different data structures.

 

Other Examples Using Two Pointers

• 배열 중 0은 모두 배열의 끝으로 이동시키기
  투포인터를 left/right로 초기화시키고선 두 포인터 모두 배열의 시작점에 놓는다. 그리고 right 포인터가 배열을 따라 이동할 동안, 만약 0이 아닌 요소를 만나는 경우는 left와 right 포인터가 가리키고 있는 요소들을 서로 swap하고, 두 포인터 모두 증가시킨다. 만약 right 포인터가 0을 만나게 되면 right 포인터만 증가시킨다. right 포인터가 배열의 끝에 다다를때까지 이 과정을 계속한다.
  
  
• Three Sum
  이것도 정말 많이 나오는 문제이다.. Two Sum의 응용 버전이라고 생각하면 되는데, 배열을 순회하면서 현재 값과 나머지 두 개의 값을 계산하면 된다. 나머지 두 개의 값을 찾기 위해서, 각 순회에 투포인터를 활용할건데 각각 leftmost, rightmost 요소에다가 위치시킨다. 그리고 주어진 sum값과 비교하면서 그 결과값에 따라 포인터들을 증가시키거나 감소시킨다.