[실전 알고리즘] 0x14강 - 투 포인터

 

 

안녕하세요, 이게 강의 목차를 16진수로 붙이니까 혼동을 주는데 이번 강의가 0x14강이니까 오리엔테이션은 빼고 20번째입니다. 아직 갈길이 좀 멀긴 하지만 꽤 많이 온 것 같습니다. 여러분들도 지금까지 잘 따라오셨다면 잘은 몰라도 대충 100문제는 넘게 풀었을거고 이제 적어도 내가 공부한 알고리즘은 문제로 나오면 풀 수 있다는 자신감을 가질 수 있을 것 같습니다. 그럼 마저 화이팅해봅시다.

 

투 포인터의 경우에는 알고리즘 자체에서 크게 설명할건 없고 그냥 문제를 해결하는 예시를 몇 개 보면서 쓰임새를 파악하면 좋습니다.

 

혹시 리뉴얼 전 강의도 보셨던 분이 있으면 알겠지만 이전에는 투 포인터 알고리즘이 없었습니다. 리뉴얼 전 강의는 2018년경부터 만들던 자료여서 사실 좀 오래된 자료였고, 당시에는 투 포인터가 잘 안나왔습니다. 그런데 언젠가부터 투 포인터 알고리즘이 코딩테스트에 한 문제씩 잘 나왔습니다. 이것도 유행이 있는건지 잘 모르겠는데 투 포인터 알고리즘이 적당히 이론적이기도 하고 인덱스 하나 차이로 정답과 런타임 에러 혹은 오답을 왔다갔다하는 그 구현에서의 디테일을 보기에도 적합한 것 같습니다. 아무튼 그래서 투 포인터 알고리즘이 뭔가 하면, 저는 위의 그림과 같이 정의를 합니다. 조금 있다가 연습 문제를 같이 보면 더 이해가 잘 되겠지만, 아무튼 배열에서 원래는 이중 for문으로 탐색을 해야한다면 O(N²)입니다. 그런데 포인터 2개를 두고 그 포인터를 잘 움직여서 O(N)에 해결하는게 투 포인터 알고리즘입니다. 여기서 포인터라고 하는건 C에서 사람들을 굉장히 괴롭게 했던 int*와 같은 포인터는 아니고, 그냥 커서라고 생각을 하면 됩니다. 그러면 왜 이렇게 시간복잡도를 줄일 수 있는거냐면, 이중 for문에서는 i = 0일 때 j가 0부터 n-1까지 돌고, i = 1일 때 j가 0부터 n-1까지 돌고, 이와 같이 각 i에 대해서 j가 0부터 n-1까지 돕니다. 그리고 이 과정에서 i = 0일 때 계산하면서 얻은 정보가 i = 1일 때에 전혀 쓰이지가 않습니다. 그런데 투 포인터에서는 i = 0일 때 계산하면서 얻은 정보를 i = 1일 때 활용합니다. 그 정보가 포인터의 이동으로 나타납니다.

그리고 미리 말씀을 드리면 이분 탐색으로 투 포인터 문제를  풀 수 있는 경우가 많습니다. 당장 전 단원에서 다뤘던 수 찾기, 숫자 카드 2, 세 수의 합 이런 문제들을 전부 투 포인터로도 해결할 수 있습니다. 반대로 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우도 많습니다. 그래서 이번에 연습 문제들을 보면서 이분 탐색으로는 어떻게 해결을 할 수 있을지도 고민을 해보시면 좋을 것 같습니다. 그러면 바로 연습 문제로 들어가보겠습니다.

 

첫 문제는 BOJ 2230번: 수 고르기 문제입니다. 일단 문제를 보고 이분탐색으로 풀 수 있겠다는 생각이 바로 들면 좋겠습니다. 사실은 좋을 것 같은게 아니라 보고 자연스럽게 이분탐색 풀이를 떠올릴 수 있어야 합니다. 미리 수열 A를 정렬해둔 다음에 현재 보고있는 수가 x라고 한다면 x + M에 대해서 lower_bound를 계산하면 끝입니다. 그런데 이걸 투 포인터로는 어떻게 해결을 할 수 있는지 소개를 해드리겟습니다. 직관적으로 떠오르는 이중 for문 풀이로부터 투 포인터 풀이가 어떻게 발전되는지를 보여드리겠습니다.

 

일단 배열은 이미 정렬이 되어있다고 치고, 이중 for문으로 코드를 짜면 이렇게 그다지 어렵지않게 구현을 할 수 있습니다. 당연히 이 코드의 시간복잡도는 O(N²)이라 시간초과가 날텐데, 실제 배열 예시를 하나 가지고 각 i에 대해서 a[j] - a[i]가 m 이상이 되는 최초의 지점 j를 나타내봤습니다. 그림을 한 번 참고해봅시다. 그림을 보면 관찰을 하나 할 수 있습니다.

 

첫 번째로 i가 증가함에 따라 a[j] - a[i]가 m 이상이 되는 최초의 지점 j 또한 증가합니다. 우린 a를 정렬해뒀기 때문에 이 관찰은 당연하게 유추할 수 있습니다. 두 번째로 각 i에 대해 a[j] - a[i]가 m 이상이 되는 최초의 지점 j를 찾은 이후에는 a[j+1], a[j+2], …을 확인할 필요가 없다는 것도 관찰할 수 있습니다. 예를 들어 i = 0인 상황을 보면 j = 2일 때 최초로 a[j] - a[i]가 9 - 2 = 7로 계산되어서 m을 넘어섰습니다. 그러면 문제에서 요구하는게 m 이상의 차이 중에서 최소이기 때문에 j = 3, 4일 때는 확인할 필요가 없습니다. 이 두 가지의 아주 강력한 관찰을 바탕으로 저희는 O(N²)의 비효율적인 이중 for문 풀이를 투 포인터 풀이로 바꿔낼 수 있습니다.

 

이전 슬라이드의 이중 for문 코드처럼 두 개의 차를 볼건데, 이번에는 투 포인터를 이용해 구현할 예정입니다. 일단 그림처럼 변수 st, en을 0에 두겠습니다. 여기서 변수 st가 이전 코드에서의 i와 같은 역할이고 en이 j와 같은 역할이라고 생각하시면 됩니다. 그리고 오른쪽 위에 있는 min은 차이의 최솟값을 저장할 변수입니다. 처음에는 아주 큰 값을 둬야하고 INF가 Infinity, 즉 그냥 엄청 큰 값을 의미합니다. 실제 구현을 할 때에는 0x7fffffff와 같은 큰 값을 담으면 됩니다.

 

우리는 각 st에 대해서 a[en] - a[st]가 m 이상이 되는 최초의 en을 찾을건데, 이 en을 찾으려고 st부터 n-1까지 다 순회하던 이중 for문의 방식과는 다르게 보다 더 효율적으로 찾아볼 예정입니다. 일단 맨 처음에 할 일은 a[en] - a[st]가 m보다 커질 때까지 en을 증가시키는 일입니다. 지금은 a[en] - a[st]가 0이니 en을 증가시켜야 합니다.

 

en을 오른쪽으로 옮겼는데 a[en]  - a[st]는 1이어서 여전히 m보다 작습니다.

 

한번 더 옮기면 a[en] - a[st]는 7이어서 m 이상이 되었고, 우리는 st = 0에 대해 a[en] - a[st]가 m 이상이 되는 최초의 지점 en을 찾았습니다. 이제 min을 7로 갱신합니다. 이 다음엔 뭘 해야할지 고민해봅시다.

 

이 다음이 재밌는데, 저희의 두 번째 관찰에 의하면 더 이상 en을 늘릴 필요는 없습니다. 그러면 이번엔 st를 옮깁니다. st = 1일 때에 a[en] - a[st]가 m 이상이 되는 최초의 지점 en을 찾아야하는데 지금 en이 애초에 그 지점입니다. 그래서 바로 min을 갱신해주면 됩니다.

 

st = 1일 때 해야할걸 다 했으니 다시 st를 오른쪽으로 한 칸 옮깁니다. 이번에는 a[en] - a[st]가 m보다 작기 때문에 en을 옮길 차례입니다.

 

en을 옮겨보면 a[en] - a[st]가 아직 m보다 작습니다. 그렇기 때문에 en을 한 번 더 옮겨야 합니다.

 

en을 한 번 더 옮기고 났더니 a[en] - a[st]가 m 이상이 됐습니다. 하지만 a[en] - a[st]가 min보다 크기 때문에 min의 갱신은 일어나지 않습니다. 이 뒤는 생략을 하겠습니다. 이렇게 각 st에 대해 모든 en을 보는게 아니라 이전의 en 값을 계속 가지고 있다가 효율적으로 써먹는 방법이 투 포인터이고 시간복잡도를 생각해보면 일단 처음 정렬에 O(NlgN)입니다. 그 다음으로 투 포인터를 수행할 때 필요한 시간복잡도를 생각해보면, 한 번 비교를 할 때마다 적어도 st가 한 칸 움직이거나 en이 한 칸 움직입니다. 그리고 en이 범위를 벗어나거나 st가 제일 끝에 도달하면 알고리즘이 끝나니까 st와 en이 움직여야 하는 거리는 최대 2N이고, 그렇기 때문에 놀랍게도 O(N)에 동작을 합니다. 이렇게 이전의 정보를 활용해서 시간복잡도를 떨굴 수 있습니다. 근데 투 포인터 알고리즘이 실제 구현을 할 때 조금 애로사항이 있습니다. 가장 많이 실수하는게 인덱스 하나 차이로 어긋나는건데, 이를테면 0-indexed 기준으로 a[n]은 절대 참조를 하면 안되는 값입니다. 그런데 뭔가 반복문 탈출 조건을 잘못 줘서 en의 값이 n이 된 이후에도 a[en] 값을 참조한다던가 하는 일을 저지르기가 쉽습니다. 그래서 이 문제는 직접 한 번 짜본다음 제 코드를 보면 좀 느낄 수 있는게 있어서 직접 짜보는 시간을 가져보겠습니다.

 

여러분이 어떻게 짜셨는지 볼 수는 없지만 굉장히 예외처리를 복잡하게 구현하신 분도 분명 있을겁니다. 그런데 사실 그냥 16, 17번째 줄처럼 짜면 끝입니다. 각 st에 대해서 a[en] - a[st]가 최초로 m 이상이 되는 지점을 찾으려면 a[en] - a[st]가 m보다 작을 동안 en을 계속 증가시키면 되고, en이 n이 되는 순간 탈출을 해야하기 때문에 while문 안에도 en < n이 필요하고, 17번째 줄의 코드도 필요합니다. 그리고 하나의 구현 팁으로 예외처리를 더 간단하게 할 수 있는 방법이 있습니다. 지금 코드에서는 a를 전역 변수로 잡았으니까 a[n]에 0이 들어가 있습니다. 그런데 지금 각 수는 -1,000,000,000에서 1,000,000,000 사이의 값이니까 그냥 a[n]에 1,000,000,000 * 10처럼 답에 영향을 줄 수 없는 아주 큰 값을 넣어버리면 en은 무조건 n에 걸려서 멈춰서있게 됩니다. 즉 en이 n을 넘어가는 일이 생기지 않고, 그러면 굳이 16, 17번째 줄에서 en이 n보다 작은지 뭐 그런걸 고려할 필요가 없이 그냥 while(a[en] - a[st] < m) en++; 으로 두면 됩니다. 다만 이렇게 경계 끝에 엄청 큰 값을 담아버리는 테크닉을 쓰다가 값을 이상하게 줘서 오히려 답을 망쳐버리는 경우도 종종 있습니다. 당장 지금도 저 테크닉을 쓰려면 a를 int가 아니라 long long으로 둬야 합니다. 그래서 이 테크닉은 나중에 코드를 찾아보다보면 다른 사람이 그렇게 구현을 해놓은 경우도 종종 있어서 알려드리긴 하지만 제가 제공하는 모범코드에서는 그냥 인덱스의 범위를 제대로 확인하는 방식으로 구현을 할 예정입니다. 혹시 저 테크닉이 마음에 들어서 자주 쓸 예정이라면 내가 설정한 a[n]값이 답에 영향을 안주는게 맞는지 아주 꼼꼼하게 확인을 해야 합니다. (코드 링크)

 

다음 문제는 BOJ 1806번: 부분합 문제입니다. 투 포인터를 쓰는 느낌이 이전 문제와 좀 비슷한 것 같아서 충분히 떠올려낼만할 것 같은데, 먼저 한 번 시도를 해봅시다. 일단 포인터 2개를 놓고 시작할거고 합이 s 이상일 때 까지 en을 증가시키다가 s 이상이 된 순간 st를 옮기고, 다시 en을 옮기는 느낌으로 접근을 하면 됩니다. 이 말까지만 듣고 방법을 알겠다 싶으면 설명을 보기 전에 먼저 직접 한 번 짜보시고, 저는 일단 실제 배열에서 설명을 좀 드리겠습니다.

 

그림은 적당히 좋은 예시를 하나 나타낸거고 min은 구간의 최소 길이를, tot는 현재 a[st]부터 a[en]까지의 합을 의미합니다. tot를 변수로 둬서 가지고 있어야 현재 보는 구간의 합이 s를 넘겼는지 아닌지 판단할 수 있습니다.

 

아직 tot가 s보다 작으니까 en을 한 칸 오른쪽으로 옮깁니다. 이 때 tot에 2를 추가해줘야 합니다.

 

en은 계속 증가할텐데 그냥 쭉 건너뛰어서 바로 tot가 s 이상이 된 순간으로 넘어가겠습니다. en이 7을 가리킬 때 tot는 17이 되면서 s 이상이 됐습니다. 그럼 이 때 뭘 해야할지 고민해봅시다.

 

바로 구간의 길이를 갱신해줘야 합니다. 구간의 길이는 en - st + 1로 계산이 가능하고 현재 담겨있는 INF보다 구간의 길이인 4가 더 짧으니까 4로 바꿔줍니다. 그 다음으로는 뭘 해야할까요?

 

st = 0일 때 구간의 합이 s 이상이 되는 en을 찾아서 처리를 다 끝냈으니까 이제는 st를 증가시켜야 합니다. st를 증가시키면 tot는 17에서 12가 됩니다.

 

st = 1에 대해서도 구간의 합이 s 이상이 되는 en을 찾아나서야 하니 en을 또 한칸 오른쪽으로 옮겨야 합니다. 이 때 tot는 16여서 s 이상이지만 구간의 길이가 4여서 min의 갱신은 일어나지 않습니다. 이 뒤는 생략하겠습니다. 구현도 바로 해볼 수 있겠죠? 다음 슬라이드에는 바로 코드가 나오니 시도를 해보고 확인을 하시면 됩니다.

 

코드에서 딱히 설명이 필요한 부분은 없어보여서 설명은 생략하겠습니다. 참고로 이 문제를 누적합에 대한 이분탐색으로도 풀 수 있는데, 다만 투 포인터로 풀면 O(N)인 반면 이분탐색으로 해결하면 O(NlgN)이 필요하다는 차이는 있습니다. (코드 링크)

 

되게 오랜만에 분량이 좀 작았습니다. 투 포인터는 사실 그렇게 할 얘기가 많지는 않습니다. 같이 다룬 두 문제는 포인터 2개가 모두 같은 배열에서 왼쪽에서 오른쪽으로 움직이는 예시였는데 두 포인터가 서로 다른 배열에서 움직이거나, 혹은 같은 배열에서 하나는 왼쪽에서 오른쪽으로 움직이는 반면 다른 하나는 오른쪽에서 왼쪽으로 움직이는 상황도 있습니다. 이건 올려놓은 다른 문제들을 투 포인터로 풀다보면 자연스럽게 습득할 수 있으니 문제들을 풀어보도록 합시다.

 

그리고 도입부에서도 말을 했었지만 투 포인터 문제가 이분탐색으로도 풀리거나, 반대로 이분탐색 문제가 투 포인터로도 풀리는 경우가 되게 자주 있습니다. 이번 강의에서 다룬 두 문제도 그런 상황이었습니다. 투 포인터는 O(N)인 반면 이분탐색은 O(NlgN)에 동작하긴 하지만 이 lgN 차이로 보통 시간 초과냐 통과냐가 갈리는 경우는 잘 없어서 둘 다 쓸 수 있겠다 싶은 문제에서는 아무거나 편하신걸로 쓰면 됩니다. 다만 투 포인터로만 풀어야 하는 문제가 간혹 있어서 투 포인터를 좀 익혀둘 필요가 있긴 합니다. 그럼 이렇게 강의를 마치겠습니다. 이전 단원의 문제들도 좌표 압축이랑 parametric search가 쓰이는 문제를 빼면 투 포인터로 풀리는 문제들이어서 한 번 들여다보시면 좋을 것 같습니다. 고생 많으셨습니다.