9.6 예제 : 모스 부호 사전(Python)

문제 출처 : algospot.com :: MORSE

algospot.com :: MORSE

---

1. 모든 신호 만들기(완전 탐색 알고리즘)

(1) 문제 분석

• 이 문제처럼 문제의 모든 답을 사전순으로 나열했을 때, 이 중 k번째에 오는 답을 구하라는 문제가 종종 있다.
• 답의 개수가 적은 경우에는 모든 답을 만들어 정렬하고 k번째 답을 반환할 수도 있지만 현실은 그렇지 못 한 경우가 대부분이다.
• 기존의 동적 계획법 문제를 해결할 때, 완전 탐색으로 시작했던 것 처럼 이런 형태의 문제도 간단하고 무식한 알고리즘으로 부터 시작해 풀 수 있다.
• 이 때 역시 기반이 되는 무식한 알고리즘은 모든 신호를 사전 순서대로 만드는 완전 탐색 알고리즘이다.

(2) 코드 구현

n, m, k = map(int, input().split())

# code9.6 모든 모스 신호를 만드는 완전 탐색 알고리즘
# n : 필요한 장점(-)의 수
# m : 필요한 단점(o)의 수
# s : 지금까지 만든 신호
def generate(n, m, s):
    # 기저 사례 : n = m = 0
    if n == 0 and m == 0:
    	print(s)
        return
    
    if n > 0:
        generate(n-1, m, s + "-")
    
    if m > 0:
        generate(n, m-1, s + "o")

• 장점(-)이 우선적으로 나와야 하므로 장점의 개수를 의미하는 n에 대해 먼저 조건을 검사한다.
• 재귀적으로 모스 부호 신호를 만들고 필요한 장점과 단점의 수를 모두 소모했을 때(n = m = 0), 신호를 출력한다.

---

2. k-1개 건너뛰기

(1) 문제 분석

• 완전 탐색 알고리즘을 기반으로 이제 k번째 신호만을 출력하는 코드를 작성해야 한다.
• 사전순으로 모든 신호를 생성하면서 k-1개의 신호를 건너뛰고 k번째 신호를 출력하면 된다.
• 앞으로 건너뛰어야 할 신호들의 수를 저장하는 전역 변수를 만들고, 신호가 완성될 때마다 이 신호를 건너뛰어야 하는지 출력해야 하는지 결정하는 코드를 작성한다.

(2) 코드 구현

# code9.7 k-1개를 건너뛰고 첫 번째 신호를 출력하는 알고리즘
# skip개를 건너뛰고 출력한다.
# 일일이 코드를 만들기 때문에 k가 크면 시간 안에 답을 찾을 수 없다.
skip = k-1

def generate2(n, m, s):
    global skip
    # 기저 사례 1 : skip < 0
    # skip이 -1까지 감소했다는 의미는 이미 k번째 신호를 출력했다는 뜻이다.
    if skip < 0:
        return
    
    # 기저 사례 2 : n = m = 0
    if n == 0 and m == 0:
        # 더 이상 건너뛸 신호가 없는 경우 출력
        if skip == 0:
            print(s)

        skip -=1
        return

    if n > 0:
        generate2(n-1, m, s + "-")
    
    if m > 0:
        generate2(n, m-1, s + "o")

• 전역 변수로 skip을 만들고 그 값을 k-1로 초기화한다.
• 완전 탐색 알고리즘의 경우와 마찬가지로 n과 m이 모두 0인 경우를 기저 사례로 갖는다.
• 이 때, skip의 값이 0이 라면 만들어진 신호는 k번째 신호라는 의미가 된다.
• (예를 들어, k = 3라면 skip = 2가 되고, skip == 2일 때 1번째 신호, skip == 1일 때 2번째 신호 그리고 skip == 0일 때 3번째 신호가 완성되었다는 것을 확인할 수 있다.)
• 그리고 skip == -1이 되었다는 것은 이미 k번째 신호를 출력했다는 의미가 되어 이제 다른 신호를 생성할 필요가 없어져 더 이상 재귀 호출을 실행하지 않아도 된다.
• 그러나 여기서 문제는 완전 탐색 알고리즘과 마찬가지로 모든 신호들을 검사하므로 k가 크다면 시간 안에 답을 찾을 수 없게 된다.

---

3. 좀 더 똑똑하게 건너뛰기

(1) 문제 분석

• 위에서 차례로 모든 신호를 만들고 그 중 k번째 신호만을 출력하는 방법을 고안했다면, 이제는 모든 신호를 만드는 것이 아니라 앞에서부터 k-1개의 신호는 모두 건너뛰고 k번째 신호만을 출력하는 방법을 고안한다.
• 여기서 n개의 장점과 m개의 단점을 s뒤에 이어 붙여 모스 부호 신호를 만들어야 하는데, n개의 장점과 m개의 단점을 조합할 수 있는 방법(경우의 수)는 어떻게 알 수 있을까? 바로 이항 계수를 통해 표현할 수 있다. 

이항 계수, C(n, k)로 표현할 수 있다.(출처 : 위키백과)

• n과 k에 대한 이항계수를 C(n, k)로 표현할 때, 이 문제에 대한 n개의 장점과 m개의 단점에 대한 조합을 이항 계수를 이용하면 C(n+m, n)개의 경우의 수가 존재한다.
• (이항계수의 성질인 C(n, k) = C(n, n-k)를 통해 C(n+m, n) = C(n+m, m) 이기 때문에 C(n+m, m) 역시 상관없다.)
• skip >= C(n+m, n)인 경우 아직 답을 찾지 못한 상태일 것이다.
• 그렇다면 과감하게 skip에서 C(n+m, n)만큼 줄여버리고 반환해도 k번째 신호를 찾는 것에는 결과가 변함이 없다.

(2) 코드 구현

# code9.8 이항계수를 이용한 k-1개를 건너뛰고 k번째 신호를 출력하는 알고리즘
# n개의 장점과 m개의 단점을 s 뒤에 잇는 조합의 수는 이항계수 (n+m n)개

MAXIMUM = int(1e9)+100

# 계산에 필요한 모든 이항계수를 미리 계산한다.
bino = [[0] * (n + m + 1) for _ in range(n + m + 1)]

def calcBino():
    # bino = [[0] * (n + m + 1) for _ in range(n + m + 1)]
    for i in range(n + m + 1):
        bino[i][0] = bino[i][i] = 1
        
        for j in range(i):
            bino[i][j] = min(MAXIMUM, bino[i-1][j-1] + bino[i-1][j])

# skip개를 건너뛰고 출력
def generate3(n, m, s):
    global skip
    # 기저 사례 1 : skip < 0:
    if skip < 0:
        return
    
    # 기저 사례 2 : n = m = 0
    if n == 0 and m == 0:
        if skip == 0:
            print(s)
        
        skip -= 1
        return

    # 기저 사례 3 : skip이 (n+m m)보다 크거나 같으면 아직 답은 찾지 못하고 skip은 (n+m m)만큼 줄어있는 상태
    # 굳이 일일이 재귀 호출할 필요 없이 skip의 크기를 줄여버리고 종료해도 똑같은 결과가 나온다?
    if bino[n+m][n] <= skip:
        skip -= bino[n+m][n]
        return

    if n > 0:
        generate3(n-1, m, s + "-")
    
    if m > 0:
        generate3(n, m-1, s + "o")

• skip은 위의 코드와 마찬가지로 전역 변수로 먼저 k-1만큼 초기화 된 채로 선언되어야 한다.

 

• 경우의 수를 구하기 위해 사전에 이항 계수를 계산하는 과정이 반드시 필요하다.
• bino[i][0] = bino[i][i] = 1인 이유는 파스칼의 삼각형을 생각하면 쉽게 이해할 수 있다.
• 나머지 이항 계수 역시 파스칼의 삼각형에서 나오는 특징을 이용하면 계산할 수 있다.
• 경우의 수를 계산할 때, 오버플로우가 발생할 수 있는데 k의 입력값은 항상 10억 이하인 것을 이용하여 이항 계수의 계산값 결과는 min 함수 연산을 통해 무조건 10억 이하로 저장되게 한다.

 

• skip과 이항 계수 C(n+m, n)을 비교하여 skip이 더 큰 경우 C(n+m, n) 만큼 감소시키고 다음 재귀 호출시 줄어드는 n과 m에 대해 반복한다.
• skip보다 이항 계수 C(n+m, n)이 더 큰 경우 k번째 신호가 이항 계수로 계산된 경우의 수 내에 위치하고 있다는 의미이므로 더 이상 skip과 이항 계수의 비교를 하지 않고 재귀호출을 통해 지속적으로 k번째 신호를 찾으면 된다.

 

• 이 알고리즘의 시간 복잡도는 선형 시간인 O(n+m)이 된다.
• 그러나 이항 계수를 계산하는 과정에서 시간 복잡도가 O(nm)이기 때문에 전체 시간 복잡도는 O(nm)이 된다.

---

4. 좀 더 좀 더 깔끔한 구현

(1) 문제 분석

• 조금 더 깔끔하게 구현하기 위해서는 완전 탐색 알고리즘이 아닌 사전순으로 가장 먼저 오는 신호 하나를 계산하는 재귀함수에서 시작하는 것이다.
• n개의 장점과 m개의 단점 중 skip개를 건너뛰고 제일 먼저 오는 신호를 반환하는 함수 kth( )를 만든다.

 

• 사전순으로 만들 수 있는 모든 신호를 정렬했을 때, 앞에서 나오는 특정한 개수의 신호들의 첫 글자는 무조건 장점일 것이다.
• 장점으로 시작하는 신호들은 총 C(n+m-1, n-1)개가 존재한다.
• (첫 신호는 장점으로 정해졌으니 나머지 부분을 n-1개의 장점과 m개의 단점으로 채워야 한다.)
• 만일 skip이 C(n+m-1, n-1)보다 크다면 k번째 신호는 단점으로 시작하는 신호가 됨을 알 수 있다.
• 그렇다면 이제 남은 신호들 중 건너 뛰어야 할 신호의 개수는 skip - C(n+m-1, n-1)개이다.
• 위 아이디어를 토대로 다음과 같은 점화식을 얻을 수 있다.

kth( ) 함수의 점화식

(2) 코드 구현

# code9.9 n개의 -, m개의 o로 구성된 신호 중 skip개를 건너뛰고 만들어지는 신호를 반환
def kth(n, m, skip):
    # n == 0이면 나머지 부분은 o로 구성된 신호일 수 밖에 없다.
    if n == 0:
        return "o" * m

    if skip < bino[n+m-1][n-1]:
        return "-" + kth(n-1, m, skip)

    return "o" + kth(n, m-1, skip - bino[n+m-1][n-1])

• 위의 코드 처럼 매개변수로 사용하는 빈 문자열 부터 신호를 하나하나 붙이는 방법이 아닌, 함수의 반환 자체 과정에서 신호를 완성하는 과정으로 설계되어 있다.
• 그리고 기존의 문자열이 들어가는 매개변수 대신 skip을 매개변수로 지정하여 k번째 신호를 찾는다.
• 알고리즘 자체의 시간 복잡도는 위 함수와 마찬가지로 O(n+m)이다.
• 그러나 이 경우에도 이항 계수를 사전에 계산해야 하므로 총 O(nm)이 소요될 것으로 예상한다.(이 부분은 책에 따로 표기되어 있지 않아 정확하지 않을 수 있다.)

---

5. k번째 답 계산하기 레시피

• 1. 완전 탐색 알고리즘을 설계하고, 메모이제이션을 적용해 경우의 수를 세는 동적 계획법 알고리즘으로 바꾼다.
• 2. 모든 답들을 사전순으로 생성하며 skip개를 건너뛰고 첫 번째 답을 반환하는 재귀 호출 함수를 구현한다. 재귀 함수는 각 조각들에 들어갈 수 있는 값을 하나씩 고려하면서 이 값을 선택했을 때 만들어지는 답의 수 M과 건너 뛰어야 할 답의수 skip을 비교한다.

• a) M <= skip : M개의 답은 모두 우리가 원하는 답보다 앞에 있으므로 이들을 건너뛰고 skip을 M만큼 줄인다.
• b) M > skip : M개의 답 중에 우리가 원하는 답이 있으므로 이 값을 선택한다. M개의 답 중 앞에서 부터 skip개를 건너뛴 것이 우리가 원하는 답이다. 이 값을 답에 추가하고 재귀 호출로 답의 나머지 부분을 만든다.

---

6. 후기

  먼저 책에서 문제를 보고 다시 블로그에 포스팅하면서 한번 더 보지만 정확하게 이해가 되지 않는 상태이다.. skip을 줄이는 과정은 이해가 된다. 근데 코드에서 보면 따로 n과 m에는 별다른 조치를 하지 않고 있다. 이 별다른 조치가 없이 skip의 값을 검사하면서 재귀 호출을 진행하면 실제로 k번째 값이 나올까? 근데 실제로 예시 입력에 대한 출력은 바르게 나오는 것을 확인할 수 있었다.. 두루뭉실하게 이해는 되는데 명확하게는 이해가 되지 않는 부분이 있다.

  그리고 이항 계수가 조금 머리를 골치아프게 하는데, 이항 계수의 의미와 문제에서의 역할은 이해가 된다. 그런데 솔직하게 C(n+m, n)이 어떻게 남은 n과 m에 대한 조합으로 표현되는이 되는지는 확실하게 감이 잡히지는 않는다. 현재는 조합의 개념을 토대로 n+m개 중 n개를 조합한다?는 정도로 이해하고 있다. 물론, 경우의 수를 세는 경우는 여러 가지 방법이 있긴 할 테지만 이렇게 이항 계수를 통해 경우의 수를 세는 것은 생소하여 문제를 이해하는데 어려움을 겪었다.

---

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

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies