들어가는 말
얼마 전데 LeetCode의 Generate Parenthesis라는 문제를 풀었습니다. 문제를 보는 순간 예전에 풀었었고, DP 문제라는 건 알았습니다. 근데 아무리 생각해도 답이 기억나지 않더라구요. 결국 제가 풀었던 문제를 찾아봤었는데, BOJ의 10422번: 괄호였습니다. 그때 제 풀이에도 '이걸 어떻게 생각하냐고'라는 단말마와 함께 답지를 봤다고 적어놓았더라구요. 프로그래머스에도 올바른 괄호의 갯수라는 똑같은 문제가 있습니다. 세 번 당하기는 싫어서 이제는 좀 외우라고 이 글을 씁니다.
왜 증명은 안 외움?
개인적인 생각으로는 증명을 외우는 게 문제풀이의 이해에 도움이 된다고 생각하지 않습니다. 그리디 문제의 증명방법 세 가지를 학교에서 배우면서 느꼈는데요. 증명은 풀고 나서 이게 진짜로 맞다는 걸 보여줄 수 있습니다. 하지만 저에게 필요한 것은 '어떻게 풀 것인가'라는 아이디어를 빠르게 떠올려야 하는 거라 굳이 싶더라구요. 알고리즘을 잘 하시는 분들의 생각은 다를 수 있지만 저는 이렇습니다.
결국 이 문제를 풀려면 '카탈랑 수'라는 걸 알아야 하는데, 저에게는 '카탈랑 수를 처음 떠올린 카탈랑 씨의 사고과정'이 필요하면 필요했지 카탈랑 수의 점화식이나 생성함수의 정당성을 증명하는 과정은 필요가 없다고 느꼈습니다.
답
우선 이렇게 정의를 내려 봅시다. P_i 는 P_{i-1} 에 괄호쌍을 하나 더하면 됩니다. 그리고 i-1개의 괄호쌍이 있는 올바른 괄호 문자열을 다시 두 개로 나눈 다음, 앞의 '하나 더하는 괄호쌍'에 들어갈 친구를 구하면 됩니다.
식으로 나타내면 이렇게 되겠네요. 합쳐서 i개가 되는 괄호쌍의 중간 어딘가에 괄호를 하나 삽입한 모습입니다.
숫자가 생각보다 크기 때문에 대부분의 문제에서는 개수를 구해야 하는데요.
개수 자체는 이렇게 구할 수 있습니다. DP 문제로 치환하면 O(n^2)의 알고리즘이 나오겠네요.
사용 가능한 문제들
이 글에 따르면 카탈랑 수는 크게 아래 문제들을 푸는 데 쓸 수 있다고 합니다.
- 격자 형태의 직사각형에서 특정 대각선을 지나가지 않고 이동하는 경우의 수
- A와 B만으로 이루어진 단어에서 A의 개수가 B의 개수 이상인 경우의 수
- 올바른 괄호 문자열의 개수
- n+2각형을 서로 겹치지 않는 대각선을 써서 n개의 삼각형으로 나누는 경우의 수
- 단말 노드가 n개인 이진트리의 개수
위 글에서는 문제들을 격자에서 특정 대각선을 만나지 않고 이동하는 경우의 수 문제로 바꿔서 풀이하고 있습니다. 결국 문제를 보고 저걸로 치환시킬 수 있는지를 곰곰이 생각하는 게 제 숙제가 되겠네요.