[알고리즘] 투 포인트(Two Point)

코드보다는 알고리즘 접근 방법에 대해 정리합니다!

keypoint.

리스트에 순차적으로 접근해야할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘

순차적, 일방향으로 되어있는 선형적인 구조에서 사용

 

 

1. 투 포인트란?

리스트에 순차적으로 접근해야할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘입니다.

구간을 설정하는 시작점과 끝점을 지정하는 방법이라고 생각하면 되는데, 순차적, 일방향으로 되어있는 선형적인 구조에서 사용할 수 있는 방법입니다!

 

예를 들어, 특정한 합을 가지는 부분 연속 수열을 찾는 문제가 있다고 합니다.

양의 정수로만 구성된 리스트[1,2,3,2,5]가 있을 때, 부분적으로 선택한 정수들의 합이 m(5)가 되는 수열의 개수를 출력해야 할때 위 투 포인트 알고리즘을 사용할 수 있습니다.

이 투 포인트 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 시작점과 끝점을 기록한다는 점입니다.

 

위 문제에서의 접근방법은 아래와 같습니다.

1) 시작점, 끝점이 첫 번째 원소의 인덱스(0)을 가리키도록 설정.
2) 현재까지의 합(s)과 m이 같으면 카운트를 증가
3) 현재까지의 합(s)이 m보다 작으면 end를 1 증가 시킴.
4) 현재까지의 합(s)보다 크거나 같으면 start를 1 증가 시킴.
5) 모든 경우를 확인할 때 까지 2~4번의 과정을 반복.

 

투 포인트 알고리즘의 특징은 위와 같은 방법이 아니더라도 문제를 풀 수 있는 접근방법이 많다는 점입니다.

만약 리스트가 [1,5,2,3,4] 라고 한다면, 시작점이 m이 된 경우에는 카운트를 증가시키고 다음 시작점으로 넘어가게끔 하는 순서를 추가할 수도 있습니다. 그 이후의 end를 계속 더한들 m이 될수는 없기 때문입니다.

 

 

2. 정렬되어 있는 두 리스트의 합집합

A리스트가 [1,3,5]이고 B리스트가 [2,4,6,8]일때, 두 리스트를 합쳐 1개의 리스트로 정렬하라는 문제가 주어졌을때, 2개의 포인터를 이용하여 각 리스트에서 처리되지 않은 원소 중 가장 작은 원소를 가리키게 하여 새 리스트로 원소를 추가하는 식으로 전개할 수 있습니다.

 

1) 정렬된 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 함.
2) 정렬된 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 함.
3) A[i]와 B[j] 중 더작은 원소를 결과 리스트에 추가한다.
4) 리스트 A와 B에서 더이상 처리할 원소가 없을때까지 1~3번의 과정을 반복.

 

포인터의 쓰임새에 중점을 두면 좋을 것 같습니다!