(내가 붙인 이름) get_k 문제 1

올해 1월 42 Seoul의 La Piscine 4주 과정에 참여하였다. La Piscine 과정에서는 알고리즘이 강조되지는 않지만, 주어진 과제 중 일부는 알고리즘을 필요로 한다. 기존에도 사용한 코딩방식이면서, 주변에 모르는 동료들에게 알려주면서 이번에 확실히 정립한 (이름하여) get_k 문제에 대해 적어본다.

(La Piscine 과정에서는 C언어를 사용했지만, 이번 포스팅에서는 편의상 Python 언어를 활용해 기술한다.)

get_k 문제

k번째 수행하기 위해 1 ~ k - 1번째 동작을 고려하는 문제를 의미한다.

N개의 반복문을 수행하는 코드 (유사한 코드를 처음 쓰게 된 계기)

get_k 문제 코드의 기반이 되는 코드는 입력으로 주어진 N만큼 반복하는 코드를 고민하는 과정에서 탄생했다. 예를 들어 고정된 값 N = 3 자리 숫자를 오름차순으로 출력하는 코드를 작성하는데에는 3개의 중첩된 반복문을 사용하면 된다.

 

for n1 in range(10):
  for n2 in range(10):
    for n3 in range(10):
      print(f"{n1}{n2}{n3}")

 

여기서 아직 정해지지 않은 N개의 반복문을 작성하려면 어떻게 해야할까? 다음과 동일한 동작을 하는 코드를 작성하고 싶다.

 

for n1 in range(10):
  for n2 in range(10):
    ...
      for nn in range(10):
        print(f"{n1}{n2}...{nn}")

 

내 해결방법은 조건문을 통해 반복문의 역할과 print의 역할을 모두 수행가능한 하나의 함수를 작성하는 것이다.

 

def solution(N):
  numbers = [-1] * N
  def get_k(k):
    if k == N:
      print("".join(numbers)
    else:
      for number in range(10):
        numbers[k] = number
        get_k(k + 1)
  get_k(0)

 

이렇게 만들어진 함수는 처음엔 N개의 반복문 역할을 수행하기 위해 사용하였다가, 점차 1 ~ k - 1번째의 행동을 고려한 k번째 수행을 하는 함수로서 발전했다.

아주 쉬운 get_k 문제

0~9의 숫자를 N개 조합하여 오름차순으로 출력하는 문제는 아주 간단한 get_k 문제이다. 위 N 자리 숫자를 오름차순 출력문제에서 하나 더 발전 된 문제로서, 이전까지의 수행을 고려해야하는 문제이다. 문제에서 조합이란 단어가 등장하지만, 단순한 반복문과 적절한 조건하나를 주어서 문제 해결이 가능하다.

N = 3자리 출력 예시를 살펴보면, 012, 013, 014, ..., 678, 679, 689, 789에서 규칙성을 발견할 수 있다. 높은 자리부터 숫자를 선택했을때, 낮은 자리 숫자는 이전의 높은 자리숫자보다 하나 더 큰 것을 살펴볼 수 있다. 즉, k번째 숫자는 0 ~ k - 1 번째 숫자보다 커야한다. (k - 1번째 숫자는 0 ~ k - 2 번째 숫자보다 크므로, k번째 숫자는 k - 1번째 숫자보다만 크면 된다.)

정리하면, get_k 문제는 k번째 수행을 위해 0 ~ k - 1번째 까지의 수행을 고려해야 한다. 아주 간단한 get_k 유형인 이 문제는, k번째 숫자를 선택할 때에 k - 1번째 수행만을 고려해도 된다. 마지막으로, get_k 함수를 처음 호출할때 prev_number에 적절한 초기값을 argument로 넘겨 주어야 한다.

 

def solution(N):
  # N: 1 ~ 9의 자연수
  numbers = [-1] * N
  def get_k(k, prev_number):
    if k == N:
      print("".join(numbers))
    else:
      for number in range(prev_number + 1, 10):
        numbers[k] = number
        get_k(k + 1, number)
        numbers[k] = -1 # 없어도 된다.
  get_k(0, -1) # prev_number + 1 = 0 이 되도록 -1을 초기값으로 준다.

 

get_k 문제에 대해 고찰하고, 조금 더 복잡한 문제에 적용하는 포스팅은 분리하여 작성하도록 한다.