Two Pointers Speed Control

Cycle 검사, Median, 시계

Intro

Photo by Susan Q Yin on Unsplash

미로에서 전진만 반복했는데 아까 왔던 곳으로 되돌아왔다. 어떻게 알았을까?

2가지 가능성이 있다. 첫째로, 한번 지나갔다는 것을 알 수 있도록 흔적을 남겨 놓았을 수 있다. 둘째로, 선발대와 후발대로 나뉜 다음 후발대가 선발대를 놓치지 않도록 충분히 긴 줄 등으로 연결한 상태에서 선발대가 빠르게 전진했을 수도 있다; 선발대가 후발대를 뒤에서 따라잡으면 두 집단을 연결하는 줄이 Cycle을 이룬다.

Graph에서 Cycle을 검사하는 방법도 2가지 이상 있다. 첫째, 각 원소별 방문 여부를 저장한다. 둘째, Two Pointers 알고리즘을 활용한다.

Two Pointers

Two Pointers는 자료 구조를 탐색하는 Pointer(또는 Iterator)가 같은 원소를 재방문하지 않도록 보장하면서 복수의 Pointer로 각 자료 구조를 동시에 탐색하는 알고리즘이다. 자료 구조에 있는 원소의 개수가 최대 \(n\)개일 때 각 Pointer는 \(n\)개의 원소를 최대 1번씩 방문하다가 선형 시간 \(O(n)\) 안에 탐색을 마친다. 따라서 총 수행 시간 \(T(n)\)은 Pointer의 개수 \(k\)에 비례한다: \(T(n) = O(kn)\). 이에 비해 99라는 숫자를 셀 때 0부터 9를 10번 다시 세는 것처럼 각 Pointer의 지역적 중복 방문을 허용해 모든 방문 상태를 탐색하는 시간은 Cartesian Product를 \(k\)번 반복하므로 \(k\)에 따라 지수적으로 증가한다: \(O(n^k)\). 가령, \(k = 2\)이면 \(O(n^2) \ne O(2n) = O(n)\)이다. 이처럼 Two Pointers 수행 시간이 선형인 이유는 지역적인 재방문을 전역적으로 방지하기 때문이다; 한번 다녀간 원소에 처음부터 다시 와보는 등 돌이키지 못하고 오로지 전진만 허용한다.

Two Pointers를 통한 Graph Cycle 검사

Two Pointers 알고리즘을 통한 Cycle 검사의 장점은 방문 여부를 저장하지 않고도 중복 방문을 방지할 수 있다는 것이다. Graph에 Cycle이 없을 때는 재방문의 2가지 원인 중 첫째인 후진(Backtracking)만 안 하면 선형 탐색이 가능하다; 애초에 방문 여부나 경로 등을 전혀 저장하지 않고 후진하다가는 무한 루프에 갇히고 말 것이다. 재방문의 또다른 원인은 Cycle이다. Cycle이 있는 Graph에서는 전진 탐색은 물론이고 선발대가 후발대를 다시 만나는 즉시 Cycle로 판단해서 중단해야 한다.

Cycle 위의 Two Pointers로 Cycle 검사를 선형 시간 안에 수행하려면 선발대와 후발대의 속력 차가 \(1\)이면 된다. 그렇지 않으면 가령 선발대가 짝수번째 원소만 방문하고 후발대가 홀수번째만 방문할 때 경로가 겹치는 것처럼 보여도 두 집단은 영원히 만날 수 없다; 무한 루프에 갇힌다. 수학적으로는 다음과 같다: 선발대가 임의의 시점에 도착한 원소를 \(0\)부터 오름차순으로 \(i_s\)번째, 후발대는 \(j_s\)번째라고 하고, \(i_s\)와 \(j_s\)가 길이가 \(m\)인 Cycle 위에 있을 때 \(t\) 시간을 더 탐색하면:

\[ \begin{align} \forall i_s, j_s \in \mathbb{Z}, \forall m \in \mathbb{Z}^+ : \exists t \in \mathbb{Z} \text{ such that } \\ & & i_s + t & \equiv j_s & \pmod{m}\;\\ \text{ and }\\ & & 0 \leq t & < m.\\ \therefore \forall a \in \mathbb{Z} :\\ & & i_s + (a + 1)t & \equiv j_s + at & \pmod{m}. \end{align} \]

다시 말해 후발대가 \(a\)의 속력으로 이동할 때 선발대가 \(a + 1\)의 속력으로 더 빨리 전진하면서 Two Pointers 알고리즘을 진행하다가 두 집단이 \(x\) 시점에 도착하는 \(j_x = j_s + at\)번째 원소와 \(i_x = i_s + (a + 1)t\)번째 원소가 \(x = t\) 시점에서 처음으로 일치(\(i_x \equiv j_x \pmod{m}\))할 때 중단하는 Cycle 검사 알고리즘의 수행 시간은 선발대와 후발대가 이미 Cycle 위에 있을 때 \(T_c(m) = O(m)\)이다. 왜냐하면 \(T_c(m) = O(t)\)이고 \(t = O(m)\)이기 때문이다.

일반적으로 원소의 개수가 \(n\)인 Graph를 탐색할 때 \(i_0 = j_0 = 0\)번째 원소가 Cycle 밖에 있더라도 정지하지 않는다면 즉 \(a > 0\)이면 Cycle 내 원소까지 선형 시간(\(T_u(n) = i_s - i_0 = O(n)\))에 가능한 한 반드시 도달한다. 또한 \(m = O(n)\)이다. 결론적으로 Two Pointers의 Cycle 검사 시간은:

\[ \begin{align} T(n) & = T_u(n) + T_c(m)\\ & = O(n) + O(m)\\ & = O(n) \end{align} \]

Linked List Cycle

LeetCode 문제 Linked List Cycle은 Linked List에 Cycle이 있는지 확인하는 문제이다. 처음에는 방문 흔적을 남기는 풀이밖에 몰랐다. 하지만 Follow up에서 상수 공간 복잡도를 요구하는 것을 보고 나니 선형 공간 복잡도로 만족할 수 없었다. 그래서 고민하던 중 같이 알고리즘 스터디를 하고 계신 쥐쥐 님의 풀이를 본 덕분에 이 글을 쓸 수 있었다. 다음 Python 풀이는 모든 양의 정수 a에 대해 동작한다:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode], a = 1) -> bool:
        node_i = head
        node_j = head
        while node_i is not None and node_j is not None:
            for _ in range(a + 1):
                node_i = node_i.next
                if node_i is None:
                    return False
            for _ in range(a):
                node_j = node_j.next
                if node_j is None:
                    return False
            if node_i == node_j:
                return True
        return False

nodes = [ListNode(x) for x in [3,2,0,-4]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i + 1]
nodes[-1].next = nodes[1]
head = nodes[0]

sol = Solution()
all(sol.hasCycle(head, a) for a in range(1, 100))

True

Two Pointers Speed Control

Two Pointers Cycle 검사는 속력 차가 1이어야 했다: \(a + 1\). 정렬된 List에서 Median 찾기는 속력 비가 2이면 된다: \(2a\).

홀수 \(n\)개 원소가 정렬된 List의 Median은 0부터 셀 때 \(\lfloor \frac n 2 \rfloor\)번째 원소이다. List가 배열이면 임의의 Index에 Random Access하는 데 상수 시간 \(O(1)\)이 걸리니 선형 시간의 Two Pointers가 더 느리다: \(O(n) \ne O(1)\).

반면에 Linked List에서 Two Pointers 알고리즘을 활용하면 \(\lfloor \frac n 2 \rfloor\)번째 원소를 찾을 때 \(n\)을 몰라도 된다는 장점이 있다. \(\forall q \in \mathbb{Z}^+\)인 \(\lfloor \frac n q \rfloor\)번째 원소라면 속력 비가 \(q\)이면 되는 것이다.

Middle of the Linked List

LeetCode 문제 Middle of the Linked List는 Linked List에서 가운데 원소(원소의 개수가 짝수이면 가운데 오른쪽)를 찾는 문제이다. 정렬된 List는 아니지만 Index 또는 가상의 기준으로 정렬돼 있다고 가정할 수 있다. 어차피 \(\lfloor \frac n 2 \rfloor\)번째 원소만 찾으면 된다. 원래는 \(n\)을 먼저 찾고 나서 절반을 되돌아가는 풀이밖에 몰랐다. 그러다 스터디에서 백발백준 님의 풀이를 보고 Two Pointers 접근을 새로 배웠다. 다음 Kotlin 풀이는 \(n\)도 모르고 Index 계산도 하지 않는다:

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        var node: ListNode? = head
        var ans: ListNode? = head
        var odd: Boolean = false
        while (node !== null) {
            node = node.next
            if (odd) {
                ans = ans!!.next
            }
            odd = odd xor true
        }
        return ans
    }
}

아날로그 시계

프로그래머스 문제 아날로그 시계는 초침과 분침이 겹치거나 초침과 시침이 겹치는 횟수를 세는 문제이다. 시계는 Two Pointers와 달리 0부터 다시 세는 지역적 재방문을 허용해서 앞서 얘기한 Cartesian Product를 탐색한다. 가령 초 단위 디지털 시계는 \(12 \times 60 \times 60\)개 상태를 탐색하므로 \(12 + 60 + 60\)개를 탐색하는 Two Pointers 접근은 불가능하다. 방문 횟수는 탐색하며 저장할 필요 없이 시간 차의 몫과 나머지를 구하면 된다.

그런데 문제는 지역적인 중복이 아니고, 시계라는 자료 구조를 공유하는 Iterator 중 일부가 서로 같은 원소에 교차하는 횟수이다. 그리고 더 큰 문제는 아날로그 시계의 원소가 디지털 시계로 다 표현이 안 되는 실수 공간에 있다는 사실이다. 다행히 시간에 따른 각 Iterator의 탐색 공간을 좌표 평면 위의 직선으로 생각하면 직선의 교차 여부를 알 수 있다. 다만 두 직선 간 교차 횟수를 각각 구하면 세 직선이 교차할 경우에 중복 합산하게 되므로 교점의 정확한 좌표를 구해서 일치하는지 확인한다.

MOD = 12 * 60 * 60
DH = 1
DM = 12
DS = 12 * 60
DSH = DS - DH
DSM = DS - DM

def solution(h1, m1, s1, h2, m2, s2):
    src = (h1 * 60 + m1) * 60 + s1
    dest = (h2 * 60 + m2) * 60 + s2
    hi = src % MOD
    mi = (m1 * 60 + s1) * DM
    si = s1 * DS
5    ans = 1 if any(xi == si for xi in [hi, mi]) else 0
    for _ in range(src, dest):
        hj = hi + DH
        mj = mi + DM
        sj = si + DS
        sh = None
1        if hi > si and hj <= sj:
2            sh = (hi - si) * DSM
        sm = None
3        if mi > si and mj <= sj:
4            sm = (mi - si) * DSH
6        bsh = sh is not None
        bsm = sm is not None
        if bsh or bsm:
            ans += 2 if bsh and bsm and sh != sm else 1
        hi = hj % MOD
        mi = mj % MOD
        si = sj % MOD
    return ans

1

시침 직선과 초침 직선의 교차

2

시침 직선과 초침 직선이 교차하는 정확한 시각에 DSM * DSH를 곱해 정수 표현한 값

3

분침 직선과 초침 직선의 교차

4

분침 직선과 초침 직선이 교차하는 정확한 시각에 DSM * DSH를 곱해 정수 표현한 값

5

시작부터 교차하는지

6

직선들이 서로 다른 두 시각에 각각 교차하는지 아니면 동시에 세 직선이 교차하는지

s = '''\
0   5   30  0   7   0   2
12  0   0   12  0   30  1
0   6   1   0   6   6   0
11  59  30  12  0   0   1
11  58  59  11  59  0   1
1   5   5   1   5   6   2
0   0   0   23  59  59  2852
'''
ans = True
for line in s.strip().split('\n'):
    *args, result = map(eval, line.split('\t'))
    ans = ans and solution(*args) == result
ans

True

Photo by Susan Q Yin on Unsplash