두 개의 포인터로 시간복잡도를 줄이는 알고리즘, 투 포인터 알고리즘에 대해 알아봅시다. 문제를 해결하는 방법은 많지만, 효율적인 방법을 찾는 것이 프로그래밍의 핵심입니다. 투 포인터는 그런 효율성을 추구하는 대표적인 알고리즘입니다.
투 포인터의 정의
투 포인터(Two Pointers) 알고리즘은 배열이나 리스트와 같은 시퀀스 자료구조에서 두 개의 포인터를 이용해 문제를 해결하는 알고리즘 기법입니다. 이름 그대로 두 개의 포인터가 데이터를 순회하며 원하는 결과를 찾아내는 방식으로 동작합니다. 일반적으로 단순한 반복문을 사용했을 때 O(n²)의 시간복잡도를 가질 수 있는 문제를 O(n)으로 줄일 수 있어 효율성이 크게 향상됩니다.
투 포인터 알고리즘은 크게 두 가지 유형으로 나눌 수 있습니다. 첫 번째는 '같은 방향으로 이동하는 투 포인터'로, 두 포인터가 모두 한쪽 끝에서 시작하여 같은 방향으로 이동합니다. 두 번째는 '양쪽 끝에서 시작하는 투 포인터'로, 하나는 배열의 시작점에서, 다른 하나는 끝점에서 시작하여 서로를 향해 이동합니다.
투 포인터의 핵심 아이디어는 불필요한 연산을 제거하는 것입니다. 예를 들어, 정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는 문제가 있을 때, 모든 쌍을 확인하는 대신 두 포인터를 이용해 합이 목푯값보다 작으면 왼쪽 포인터를 증가시키고, 크면 오른쪽 포인터를 감소시키는 방식으로 효율적으로 문제를 해결할 수 있습니다.
이 알고리즘은 특히 배열이나 문자열을 다루는 문제, 부분 배열의 합(Subarray Sum), 팰린드롬 판별, 중복 요소 제거 등 다양한 문제에 적용할 수 있어 코딩 테스트나 알고리즘 대회에서 자주 활용됩니다.
투 포인터의 구현 방법
투 포인터 알고리즘은 개념적으로는 간단하지만, 실제 구현에서는 세심한 주의가 필요합니다. 포인터의 이동 조건과 종료 조건을 명확히 설정해야 하며, 특히 경계 케이스(edge case)를 고려해야 합니다. 여기서는 부분합 문제를 예시로 투 포인터 구현 방법을 살펴보겠습니다.
부분합 문제는 주어진 배열에서 연속된 요소들의 합이 특정 값과 같은 부분 배열을 찾는 문제입니다. 이 문제를 이중 반복문으로 해결하면 O(n²) 시간이 소요되지만, 투 포인터를 활용하면 O(n)으로 해결할 수 있습니다.
아래 코드에서 투 포인터의 핵심 구현 방법을 볼 수 있습니다:
- 두 포인터 left와 right를 배열의 시작점에 위치시킵니다.
- right 포인터를 증가시키며 부분합을 누적합니다.
- 부분합이 목표값보다 커지면, left 포인터를 이동시키며 합에서 해당 값을 뺍니다.
- 부분합이 목표값과 일치하면 결과를 저장합니다.
이 방식을 통해 배열의 모든 요소를 최대 두 번만 방문하게 되어 시간복잡도는 O(n)이 됩니다. 투 포인터 구현에서는 포인터 이동 조건을 명확히 설정하는 것이 중요합니다. 특히 포인터가 서로 교차하지 않도록 하거나, 필요한 경우 적절히 교차할 수 있도록 조건을 설정해야 합니다.
투 포인터로 해결할 수 있는 코딩테스트 문제
투 포인터 알고리즘은 다양한 코딩테스트 문제에 적용할 수 있습니다. 백준 온라인 저지에서 볼 수 있는 대표적인 유형들을 살펴보겠습니다.
- 두 수의 합 - 정렬된 배열에서 합이 특정 값인 두 요소 찾기
- 배열을 정렬한 후, 양쪽 끝에서 시작하는 두 포인터를 이용합니다.
- 예: 백준 3273번 "두 수의 합"
- 부분합 - 연속된 부분 배열의 합이 특정 값 이상인 가장 짧은 길이 찾기
- 시작점과 끝점을 조절하며 조건을 만족하는 구간을 찾습니다.
- 예: 백준 1806번 "부분합"
- 소수의 연속합 - 연속된 소수의 합으로 특정 자연수 표현하기
- 에라토스테네스의 체로 소수를 구한 후 투 포인터로 연속합을 확인합니다.
- 예: 백준 1644번 "소수의 연속합"
- 수들의 합 2 - 연속된 부분 배열의 합이 특정 값인 경우의 수 찾기
- 합이 목표값보다 작으면 오른쪽 포인터를 증가, 크면 왼쪽 포인터를 증가시키는 방식으로 해결합니다.
- 예: 백준 2003번 "수들의 합 2"
- 회문 - 문자열이 팰린드롬인지 판별하고, 아니라면 한 문자를 삭제해서 팰린드롬이 되는지 확인하기
- 양끝에서 중앙으로 이동하는 두 포인터로 검사합니다.
- 예: 백준 17609번 "회문"
- 두 용액 - 두 용액을 혼합하여 0에 가장 가까운 특성값 만들기
- 정렬 후 양쪽 끝에서 시작하는 투 포인터로 합이 0에 가까운 두 용액을 찾습니다.
- 예: 백준 2470번 "두 용액"
- 세 용액 - 세 용액을 혼합하여 0에 가장 가까운 특성값 만들기
- 한 용액을 고정하고 나머지 두 용액을 투 포인터로 찾는 방식으로 해결합니다.
- 예: 백준 2473번 "세 용액"
이러한 문제들은 투 포인터 기법의 다양한 변형을 보여주며, 실제 코딩테스트에서도 자주 등장합니다. 각 문제는 투 포인터의 기본 개념을 응용하면서도 문제마다 특화된 조건과 처리 방법이 필요하므로, 여러 유형을 익혀두는 것이 좋습니다.
마무리
투 포인터 알고리즘은 단순하지만 강력한 기법으로, 시간복잡도를 크게 개선할 수 있어 효율적인 코드 작성에 큰 도움이 됩니다. 다양한 문제에 적용할 수 있으며, 특히 배열이나 문자열을 다루는 알고리즘 문제에서 자주 활용되므로 코딩테스트를 준비하는 개발자라면 반드시 숙지해야 할 기법입니다.