괄호 매칭, 스택 없이 병렬로 푸는 법

괄호 매칭은 보통 스택으로 풉니다. 여는 괄호는 쌓고, 닫는 괄호가 오면 꺼내 짝을 맞추죠. 직관적이지만 본질적으로 순차적이라 데이터가 커지면 한 코어만 일합니다. 이 글은 발상을 바꿉니다. 여는 괄호를 +1, 닫는 괄호를 -1로 본 뒤 접두합(prefix sum, scan)을 구하면 각 위치의 중첩 깊이가 나옵니다. 같은 깊이에서 인접한 여는·닫는 괄호가 곧 서로의 짝이라는 점을 이용하면, 스택 없이 각 괄호의 파트너를 동시에 계산할 수 있습니다. 핵심은 스캔이 O(log n) 시간에 병렬화되는 잘 알려진 연산이라는 점입니다. 덕분에 GPU·SIMD에서 수천 개 코어를 동시에 굴려 JSON·소스코드·중첩 구조를 대규모로 파싱할 수 있죠. 순차적으로 보이는 문제도 누적 연산으로 재정의하면 병렬화의 길이 열린다는 것이 이 글의 진짜 교훈입니다.