9.9 문제 : 드래곤 커브(Python)

문제 출처 : algospot.com :: DRAGON

algospot.com :: DRAGON

---

1. p번째 글자를 찾는 함수 작성하기

(1) 함수 설계하기

• 우선 맨 앞에서 전체 드래곤 커브 문자열을 생성하는 알고리즘을 만들고, 이것을 기반으로 p번째 글자를 찾는 알고리즘을 작성해본다.
• 드래곤 커브 문자열을 만드는 방법을 재귀적인 구현으로 만든다.
• 처음 주어진 정보는 0세대 문자열인 FX(=seed)와 세대 수 n(=generations)이다.
• 이를 전달받는 함수 curve( )를 다음과 같이 정의한다.

 

• curve(seed, generations) = 초기 문자열 seed를 generations세대 진화시킨 결과를 출력한다.

 

• curve( )는 seed의 각 글자를 순회하면서 X나 Y인 경우 재귀 호출을 이용해 해당 문자가 진화한 결과를 계산하고 F, +, -인 경우에는 출력한다.

(2) 코드 구현

# 드래곤 커브 문자열을 생성하는 재귀 호출 알고리즘
# curve(seed, generations) = 초기 문자열 seed를 generations세대 진화시킨 결과를 반환
def curve(seed, generations):
    # 기저 사례 
    if generations == 0:
        print(seed)
        return

    for i in range(len(seed)):
        if seed[i] == 'X':
            curve("X+XF", generations-1)
        
        elif seed[i] == 'Y':
            curve("FX-Y", generations-1)
        
        else:
            print(seed[i])

• curve("FX", n) 부터 시작해 문자열을 검사하면서 X나 Y를 만나면 문제에서 제시된 치환된 문자열로 n을 감소시키며 재귀호출을 진행한다.
• 이 코드에서 p번째 글자만을 출력하도록 하는 방법은 skip을 이용하면 된다.
• 건너뛰어야 하는 글자의 수 skip을 전역 변수에 유지하면서, 문자열 혹은 문자를 출력할 때마다 skip과 출력할 부분의 길이를 비교한다.
• curver( )에는 기저 사례와 문자열이 F, +, -를 만날때 문자열 혹은 문자를 출력하는데, 출력할 문자열의 길이가 skip보다 작거나 같은경우에는 출력을 하지 않고 skip만 감소시킨 뒤 재귀 호출을 계속 진행하면 된다.

---

2. 계산 결과 길이 미리 계산하기

(1) 점화식 유도하기

• p번째 글자를 출력하는 재귀 호출 코드를 최적화하려면, 재귀 호출할 때마다 이 재귀 호출이 몇 글자를 출력할지를 미리 알고 skip과 이 값을 비교할 수 있어야 한다.
• curve(seed, generations)가 몇 글자를 출력할지 계산하는 동적 계획법 알고리즘을 만들어야 한다.
• seed로 들어갈 수 있는 매개변수의 값은 항상 "FX", "X+YF", "FX-Y"의 셋 중 하나이므로 비교적 수월하게 만들 수 있다.
• 이를 해결하기 위해 다음과 같은 부분 문제를 정의한다.

 

• xLength(n) = 문자열 "X"를 n세대 진화시킨 결과의 길이를 반환
• yLength(n) = 문자열 "Y"를 n세대 진화시킨 결과의 길이를 반환

 

• X의 치환 문자열과 Y의 치환 문자열은 문제에서 정해져 있어 점화식을 다음과 같이 정의할 수 있다.

 

• xLength(n) = xLength(n-1) + yLength(n-1) + 2
• yLength(n) = xLength(n-1) + yLength(n-1) + 2

• X = X+YF로 치환되는데 다음 세대 문자열의 길이를 구하면 X+YF에서 다시 X => xLength(n-1)가 되고 Y => yLength(n-1)이 되며 나머지 +와 F의 2개 문자가 추가되니 뒤에 +2가 붙게 된다.
• Y = FX-Y에서도 마찬가지로 이해할 수 있다.

 

• 위 점화식을 보면 xLength(n) = yLength(n)인 것을 알 수있기 때문에 점화식을 단순화 할 수 있다.
• length(n) = 2 * length(n-1) + 2

 

• 이를 바탕으로 문자열의 길이를 미리 계산해서 배열에 저장하는 과정이 필요하다.
• 이 배열에는 경우의 수가 p의 최댓값인 10억을 크게 벗어나지 않도록 MAX를 설정하고 경우의 수가 MAX를 벗어나는 경우에는 MAX만을 저장하도록 해야한다.
• 경우의 수가 p보다 크다면 그 뒤에는 얼마나 크던 상관 없기 때문에(p번째 글자를 찾는것이 중요하기 때문에 경우의 수가 p보다 크기만 하면 문제될 것이 없다.) 이런 방법을 통해 오버 플로우를 피할 수 있다.

(2) 코드 구현

1) precalc( ) : n 세대의 드래곤 커브 문자열의 길이를 사전에 배열에 저장

MAX = int(1e9) + 1
EXPAND_X = "X+YF"
EXPAND_Y = "FX-Y"

# n 세대의 dragonCurve 문자열의 길이를 저장한다.
def precalc():
    length[0] = 1
    for i in range(1, 51):
        length[i] = min(MAX, length[i-1] * 2 + 2)

• 처음 책에서 이 부분을 공부하면서 코드 주석에는 precalc( )를 n 세대의 dragonCurve 문자열의 길이를 저장한다고 기록했다.
• 사실, 잘못된 것으로 정확하게는 X나 Y를 i번 치환한 후의 길이를 의미하는게 맞다.
• 오답 노트의 일환으로 여기에 명시하고 따로 고치지는 않음...

2) expand(dragonCurve, generations, skip) : 드래곤 커브를 generations세대 진화시킨 결과에서 skip번째 문자를 반환한다.

# dragonCurve를 generations 세대 진화시킨 결과에서 skip번째 문자를 반환한다.
def expand(dragonCurve, generations, skip):
    # 기저 사례
    # 재귀 호출을 모두 완료 했을 때 남아있는 skip보다 dragonCurve의 길이가 길어야 해당 dragonCurve 내에서 skip번째 이상의 문자열을 생성할 수 있다.
    if generations == 0:
        # 가정 설명문 assert 조건, (message): assert 뒤의 조건이 True가 아니면 (message와 함께) AssertError를 발생한다.
        # 단순히 에러를 찾는것이 아닌 실수를 가정하고 어떤 조건에 해당하는 값들을 보증하기 위한 '방어적 프로그래밍' 기법의 일종
        assert skip < len(dragonCurve)
        
        return dragonCurve[skip]

    for i in range(len(dragonCurve)):
        # 문자열이 X나 Y를 만나 확장(치환)되는 경우
        if dragonCurve[i] == 'X' or dragonCurve[i] == 'Y':
            # skip이 현재 세대의 드래곤 커브 문자열의 길이보다 크거나 길다면 skip에서 현재 드래곤 커브 문자열의 길이만큼 감소
            if skip >= length[generations]:
                skip -= length[generations]

            # skip이 현재 세대의 드래곤 커브 문자열의 길이보다 작다면 현재 세대의 문자열에서 p번째 문자를 찾을 수 있다는 의미
            # 현재 세대에 대한 드래곤 커브 문자열을 재귀적으로 만듦
            elif dragonCurve[i] == 'X':
                return expand(EXPAND_X, generations - 1, skip)

            else:
                return expand(EXPAND_Y, generations - 1, skip)

    
        # 확장(치환)되지는 않지만 건너뛰어야 할 경우
        # 문자열에서 F, -, +를 만나고 skip이 1이상이면 해당 문자를 건너뛴다는 의미
        elif skip > 0:
            skip -= 1

        # 답을 찾은 경우
        # skip == 0인 경우 해당 글자가 skip번째 문자가 된다.
        else:
            return dragonCurve[i]

    return '#' # 이 줄은 수행되지 않는다?

• 유의해야 될 부분이 몇 가지 있다.
• 드래곤 커브 문자열이 X나 Y를 만났을 때, skip이 length[generations]보다 큰 경우 재귀 호출을 진행하지 않는다는 점을 잘 봐야 할 것 같다.
• 그 외에 조금 낯선 문법인 가정 설명문(assert)이 있는데 skip의 값이 재귀 호출이 끝날 때 드래곤 커브 문자열의 길이보다 크다면 skip번째 글자를 찾을 수 없으므로 이를 방지하기 위해 assert의 조건문을 만족하지 못 하면 에러를 발생시키는 안전 벨트로 생각하면 되겠다.
• 함수의 마지막 반환 값으로 수행되지 않는 줄인 return '#'이 존재한다.
• 아주 아주 만약에 출력된 문자열 중에 '#'이 들어가있다면 코드 내의 어딘가 문제가 있다는 의미로 받아드리면 될 것같다.

 

• expand( )는 최대 n번 재귀 호출되고, 그 안에서는 길이가 최대 5인 반복문을 실행하기 때문에 O(n)의 시간이 소요된다.
• p부터 시작해 길이가 l인 문자열을 출력해야 되는데 l이 최대 50인 경우에서도 부담없는 실행 속도다.

3) 문제 입-출력

for tc in range(int(input())):
    n, p, l = map(int, input().split())
    
    length = [-1] * 51
    precalc()

    # expand 함수는 문자를 반환하기 위해 문제에서 원하는 문자열을 생성하기 위해서는 l번 반복해야 한다.
    # 문제에서 요구하는 p와 l은 1이상의 정수이기 때문에 실제 p번째 문자를 구하기 위해서는 p-1번째 문자를 출력해야 한다.
    for i in range(p, p+l):
        print(expand("FX", n, i-1), end = "")

    print()

• 문제에서 p부터 시작하는 길이가 l인 드래곤 커브 문자열을 요구하기 때문에 이를 문자열 인덱스에 적용하면 p-1번째 문자부터 p+l-2번째 문자열까지 출력하면 된다.
• 지금 코드를 다시 보니 반복문의 range를 (p-1, p+l-1)로 설정하고 expand("FX', n, i)로 설정하는게 더 직관적이지 않았을까 생각하게 된다.

---

3. 후기

  앞에서 두 개의 k번째 답 계산하기 문제를 해결하고 이 문제를 보니 서서히 재귀 호출을 통해 k번째 답을 계산하는 방법에 대해 감이 오기 시작했다. 솔직히 아직도 애매하게 이해되는 부분이 없지 않아 있긴 하지만 이제 비슷한 문제들을 보면 이런 참고 자료를 통해 해결할 수 있을것 같은 자신감이 든다. 그리고 8장부터 시작해 동적 계획법 문제들을 많이 봐왔던 경험들을 토대로 동적 계획법 문제들 역시 쉬운 문제들은 어떻게 설계해야 될지 어렴풋이 알 것 같다.

  이 문제도 그렇고 일단 문제들을 해결하는 과정에 있어서 항상 배열의 범위와 문자열의 인덱스, 함수의 기저 사례등을 꼼꼼하게 살펴야 하는 습관이 중요한 것 같다. 책에서는 보통 문제 입-출력을 제외한 핵심 함수에 대한 부분만을 알려주기에 입-출력 단계에서 핵심 함수를 토대로 코드를 작성해야 하는데 위의 나열한 사안들에 대해 골치가 아픈 경우가 많았다. 문제가 해결 안될때 마음을 급하게 먹기 보다는 천천히 그리고 꼼꼼하게 하나하나 살펴보며 복습할 때도 마찬가지로 눈으로 대충 읽고 넘기는 것이 아니라 한 줄 한 줄의 의미를 이해하는 것에 중점을 두는 것이 중요함을 느낀다.

---

github: Algorithmic_Problem_Soving_Strategies/q9_9.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies