8.7 문제 : 원주율 외우기(Python)

문제 출처 : algospot.com :: PI

algospot.com :: PI

---

1. 문제 분석

• 입력의 크기가 최대 10,000인 것을 보면 완전 탐색으로 이 문제를 해결하기란 어려움
• 그러나 메모이제이션으로 이 문제를 해결할 수 있다.
• 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어 보며 그중 난이도의 합이 가장 작은 조합을 찾는다.
• 재귀 함수는 한 번 불릴 때 마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 마찬가지로 재귀 호출을 통해 분할한다.
• 첫 조각의 길이는 3, 4, 5 중 하나이므로 각 경우 마다 하나씩의 부분 문제를 해결해야 한다.
• 먼저 세 부분 문제에 대한 최적해를 각각 구했다고 하면, 전체 문제의 최적해는 다음 세 경우 중 가장 작은 값이다.

 

• 길이 3인 첫 조각의 난이도 + 3글자를 제외한 나머지 수열에 대한 최적해
• 길이 4인 첫 조각의 난이도 + 4글자를 제외한 나머지 수열에 대한 최적해
• 길이 5인 첫 조각의 난이도 + 5글자를 제외한 나머지 수열에 대한 최적해

 

• 나머지 수열을 다시 길이가 3, 4, 5인 첫 조각을 분리하여 재귀적으로 최적해를 구한다.
• 최적 부분 구조(부분 문제의 최적해가 전체 문제의 최적해로 이루어지는 경우)가 성립되므로 같은 시작위치가 주어졌을 때, 항상 같은 값을 반환하므로 메모이제이션으로 최적화할 수 있다.

 

• 주어진 수열 N에 대해서 L이 3에서 5까지인 정수 일 때 다음 점화식에 의한 최소값을 찾는다.
• memorize(begin) = min(memorize(begin + L) + classify(N[begin : begin + L]))
• begin : 시작 위치
• memorize() : 최소 난이도를 반환하는 함수(실제 메모이제이션 구현)
• classify() : 해당 조각의 난이도를 반환하는 함수

---

2. 해설 풀이 방법

(1) classify()

# N[a:b] 구간의 난이도를 반환
def classify(a, b):
    # 숫자 조각을 가져옴
    m = n[a:b+1]

    # 난이도가 1인 경우(모든 숫자가 같은 경우)
    if m == (m[0] * len(m)):
        return 1

    # 등차수열의 형태를 이루는지 검사
    progressive = True

    for i in range(len(m)-1):
        if (int(m[i+1]) - int(m[i])) != (int(m[1]) - int(m[0])):
            progressive = False

    # 난이도가 2인 경우(등차수열이며 모든 숫자가 등차가 1 or -1)
    if progressive and abs(int(m[1]) - int(m[0])) == 1:
        return 2

    # 난이도가 4인 경우(두 수가 번갈아 등장)
    alternating = True
    for i in range(len(m)):
        # (0, 0), (1, 1), (2, 0), (3, 1), (4, 0), (5, 1).....
        # 0,1의 인덱스에 해당하는 값과 홀수, 짝수의 인덱스에 해당하는 값이 같은지 검사하여 번갈아 나오는지 알 수 있음
        if m[i] != m[i%2]:
            alternating = False

    if alternating:
        return 4

    # 난이도가 5인 경우(등차가 1, -1이 아닌 등차수열의 형태)
    if progressive:
        return 5

    # 그 외의 경우는 모두 난이도가 10
    return 10

• 위 점화식에서 classify(N[begin : begin + L])에 해당하는 부분
• 점화식에서는 시작 위치가 begin이고 길이가 L인 부분 문자열에 대해 그 난이도를 반환하지만
• 코드에서는 구간 a부터 b까지의 난이도를 반환하는 것으로 구현되어 있다.
• Python 문자열 슬라이싱을 이용해 문자열의 a인덱스 부터 b 인덱스까지의 부분 문자열을 쉽게 생성할 수 있었다.

 

• 두 수가 번갈아 나오는지 검사(난이도가 4인 경우)하는 형태가 조금 생소하다.
• m[i]는 0번 인덱스의 원소부터 차례로 검사하고 m[i%2]는 0번 인덱스의 값과 1번 인덱스의 값이 반복되서 나올것이다.
• 만약 두 수가 번갈아서 나온다면 모든 짝수번째 원소들은 m[0]의 값과 같을 것이고, 모든 홀수번째 원소들은 m[1]과 값이 같을 것이다.

 

• 그 외 다른 난이도를 비교하는 부분은 꼼꼼하게만 작성한다면 크게 복잡한 것은 없다.

(2) memorize()

# N[begin:]을 외우는 방법 중 난이도의 최소 합을 반환
def memorize(begin):
    # 기저 사례 : begin이 문자열의 끝인 경우
    if begin == len(n):
        return 0

    if cache[begin] != -1:
        return cache[begin]

    cache[begin] = INF
    for L in range(3, 6):
        if begin + L <= len(n):
            cache[begin] = min(cache[begin], memorize(begin + L) + classify(begin, begin + L - 1))

    return cache[begin]

• 문제 분석에서 유도한 점화식을 메모이제이션을 적용해 구현한 부분이다.
• 한 가지 유의해야 될 부분이 classify(begin, begin + L - 1)인데 왜 -1을 하는지 그 이유를 생각해봤다.
• 간단하게 -1을 제외하고 begin = 0이라고 하고 길이 3인 첫 조각의 난이도를 검사하기 위해 L = 3이라고 하자
• 그렇다면 classify(0, 3)인데 classify에서는 0부터 3까지의 부분 문자열을 검사할 것이다.
• 그러나 우리는 문제 분석에서 첫 조각은 3글자, 4글자, 5글자로 쪼개어 검사를 진행한다고 했다.
• 근데 classify() 함수에 (0, 3)을 인자로 넘기면 0번, 1번, 2번, 3번 총 길이가 4인 수열을 검사하게 된다.
• 처음 의도는 조각(혹은 부분 수열)의 길이가 3인 경우를 검사하길 원했는데 -1을 하지 않으면 4글자, 5글자, 6글자를 검사하게 된다.
• 따라서 -1을 꼭 입력해줘야 한다.
• 그리고 memorize(begin + L)의 경우 자연스럽게 조각을 제외한 다음 부분 문자열의 첫 인덱스를 가리키므로 상관없다.

(3) 시간 복잡도

• 사실 정확히 이해하지는 못했지만 책의 설명에 따르면 다음과 같다.
• 알고리즘은 최대 n개의 부분 문제가 있고 각 부분 문제를 해결하는데 최대 3개의 부분 문제를 본다.
• 따라서 시간 복잡도는 O(n)이다.
• 각 부분 문제를 해결하는데 최대 3개의 부분 문제를 본다는 말은 길이가 3, 4, 5인 조각으로 나눈경우를 말하는 것 같다.
• 근데 최대 n개의 부분 문제가 있다는 말을 이해하지 못 하겠다.. 

---

3. 후기

  classify() 구현 부분을 보고 내가 문제를 너무 복잡하게만 바라보는게 아닌가 생각이 들었다. 아마 내가 처음 문제를 봤다면 등차수열과 번갈아 나오는 수를 확인할 때, 매번 새롭게 갱신되는 4개의 인덱스에 차이를 이용해서 검사했을 것 같은데 단순하게 첫 번째, 두 번째 인덱스에 나오는 값을 고정하고 새롭게 갱신되는 2개의 인덱스만으로 등차수열인지 혹은 수가 번갈아서 나오는지 검사하는 것을 보고 내가 왜이렇게 어렵게 문제를 대할까 하는 생각이 들었다. 그리고 난이도에 따른 반환 역시 '그냥 그대로 구현하면 되는구나' 라는 생각이 들었다. 이전에 문제들이 대부분 코드를 보고 직관적으로 이해되는 경우가 많지 않아서 오히려 이렇게 단순히 구현하면 되는 코드를 생각하지 못하는 역효과가 발생한 것 같다.

  그래도 다른 문제들과의 공통점을 찾자면 문제해결을 위한 설계과정이 어렵다는 점이다. 분명 책의 저자나 실제 프로그래밍 대회에서 문제를 해결한 사람들도 설계가 어려웠을 것이다. 그러나 막상 내가 새로운 문제에 대해서 이를 분할하고 점화식을 만들고 이를 코드로 구현하라고 하면 난이도가 '하'라고 해도 제한 시간안에 해결할 수 없을거라는 생각이 든다. 일단 해당 단원과 관련된 단원들을 풀고 다른 코딩 테스트 문제 사이트에서 새로운 문제를 나 혼자서 설계해보는 과정이 꼭 필요할 것 같다.

---

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

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies