C++ 재귀 함수로 풀어보는 문법의 K번째 기호 문제

첫 번째 행에는 숫자 0이 하나 있다고 가정해 봅시다. 그다음 행부터는 바로 앞 행을 참조하여, 각 0은 01로, 각 1은 10으로 바꾸어 나갑니다. 이렇게 생성된 수열에서 N개의 행과 인덱스 K가 주어졌을 때, N번째 행의 K번째 위치에 있는 기호를 찾는 것이 이번 문제의 목표입니다. (K 값은 1부터 시작합니다.)

예를 들어 N = 4, K = 5가 주어진다면 출력 결과는 1이 됩니다. 그 이유는 다음과 같습니다.

행 1: 0
행 2: 01
행 3: 0110
행 4: 01101001

문제 해결 접근 방법

이 문제는 재귀적 사고방식으로 접근하면 깔끔하게 해결할 수 있습니다. 해결 과정은 다음 단계와 같습니다.

kthGrammar라는 이름의 메서드를 정의하고, N과 K를 매개변수로 받습니다.
N이 1이라면 첫 행은 항상 0이므로 0을 반환합니다.
K가 짝수인 경우, kthGrammar(N - 1, K / 2)의 결과가 0이면 1을 반환하고, 그렇지 않으면 0을 반환합니다.
K가 홀수인 경우에는 kthGrammar(N - 1, (K + 1) / 2)를 그대로 반환합니다.

알고리즘 동작 원리

각 행은 이전 행의 길이를 두 배로 확장한 것이며, 홀수 번째 문자는 이전 행의 대응 문자와 같고, 짝수 번째 문자는 이전 행 대응 문자의 반대값이 됩니다. 따라서 K의 위치를 이전 행의 위치로 계속 매핑하며 거슬러 올라가면, 결국 첫 행의 0에서 출발해 원하는 값을 도출할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(N), 공간 복잡도 역시 재귀 호출 스택으로 인해 O(N)입니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int kthGrammar(int N, int K) {
        if(N == 1) return 0;
        if(K % 2 == 0){
        return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;
        }else{
            return kthGrammar(N - 1, (K + 1) / 2);
        }
    }
};
main(){
    Solution ob;
    cout << (ob.kthGrammar(4, 5));
}

입력

4
5