코딩 연습

(재귀함수) 자(ruler)의 눈금 그리기 본문

알고리즘

(재귀함수) 자(ruler)의 눈금 그리기

코딩중독 수악중독 2017.04.29 05:20

"자(ruler)의 눈금 그리기"는 자에서 사용할 가장 긴 눈금의 길이과 자의 크기를 입력하면 자의 눈금이 그려지도록 프로그래밍 하는 문제이다.


예를 들어, 

(1) 가장 긴 눈금의 길이를 3, 자의 크기를 3으로 입력하면 다음과 같은 눈금이 그려져야 한다. 

그림에서 볼 수 있듯이 주 눈금은 길이 3인  '---' 로 표시했고, 1단위를 4등분하여 2등점은 길이 2인 '--' 로, 4등분점은 길이 1인 '-' 로 표시하였다. 또한 주 눈금을 표시하고 나면 옆에 눈금에 해당하는 숫자를 표기해 주었다.


(2) 가장 긴 눈금의 길이를 4, 자의 크기를 2로 입력하면 다음과 같은 눈금이 그려져야 한다.

주 눈금은 길이 4인 '----'로 표시했고, 1 단위를 8등분하여 2등분점은 길이 3인 '---' 로, 4등분점은 길이 '2'인 '--' 로, 나머지는 길이 1인 '-' 로 표시하였다. 마찬가지로 주 눈금의 오른쪽에는 눈금에 해당하는 숫자를 표기해 주었다.


(3) 가장 긴 눈금의 길이를 5, 자의 크기를 1로 입력하면 다음과 같은 눈금이 그려져야 한다.

주 눈금은 길이 5인 '-----' 로 표시했고, 1 단위를 16등분하여 2등분점은 길이 4인 '----' 로, 4등분점은 길이 3인 '---'로, 8등분점은 길이 2인 '--' 로, 나머지는 길이 1인 '-' 로 표시하였다. 주 눈금 오른쪽에서는 눈금에 해당하는 숫자를 표기해 주었다.


이 문제를 풀어 본 분들은 다들 아시겠지만, 처음에 만만하게 보여도 결코 만만한 문제가 아니라는 것을 알 수 있다. 하지만 이 문제는 재귀함수를 써서 간단하게 (절대로 쉽지는 않다.) 해결할 수 있다.  다음의 파이썬 코드를 보도록 하자.

def print_gradation(gradation_length, gradation_label=''):
    gradation = '-' * gradation_length
    if gradation_label:
        gradation += ' ' + gradation_label
    print(gradation)


def make_interval(gradation_length):
    if gradation_length > 0:
        make_interval(gradation_length - 1)
        print_gradation(gradation_length)
        make_interval(gradation_length - 1)


def draw_ruler(ruler_size, max_gradation_length):
    print_gradation(max_gradation_length, '0')
    for j in range(1, 1 + ruler_size):
        make_interval(max_gradation_length - 1)
        print_gradation(max_gradation_length, str(j))


max_gradation_length = input("가장 긴 눈금의 길이를 입력하세요 : ")
ruler_size = input("자의 크기를 입력하세요 : ")

draw_ruler(int(ruler_size), int(max_gradation_length))


눈금이 그려지는 과정의 일부를 그림으로 표현하면 다음과 같다. 



위의 코드와 그림을 보면서 본인 스스로가 비슷한 그림을 그려본다면 아마 어떻게 재귀함수가 눈금들을 그려나가는지 이해할 수 있을 것이다.

 출력 결과는 다음과 같다.

가장 긴 눈금의 길이를 입력하세요 : 5
자의 크기를 입력하세요 : 1
----- 0
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 1
가장 긴 눈금의 길이를 입력하세요 : 4
자의 크기를 입력하세요 : 2
---- 0
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 2

재귀함수가 동작하는 원리를 이해하는 것은 결코 쉬운 일이 아니다.  대부분 재귀함수의 예제로 $n!$ 의 계산을 봤을 것이고, 이 부분은 이해하기 어렵지 않기 때문에, 재귀함수의 동작 원리를 만만하게 생각할 수 있는데 그림을 그려가면서 이해하려 해도 쉽지 않은 것이 재귀 함수이다. 그래도 언젠가는 익숙해 지겠지 하는 희미한 착각을 가지며 꾹 참고 보고 또 봐야겠다.

예전에 스도쿠 푸는 프로그램에 재귀함수를 사용했던 적이 있는데, 그냥 그러면 될 것 같아서 재귀함수를 사용했었지만, 아직도 정확한 원리를 나 자신도 이해하지 못한다. 코딩을 할 때, 프로그램이 어떻게 동작하는지는 프로그래머와 신만이 알 수 있지만, 한 달이 지나고 나면 오직 신만이 알 수 있다는 농담이 왜 생겨 났는지 이해가는 부분이다.



'알고리즘' 카테고리의 다른 글

Big-Oh Notation (빅-오 표기법)  (0) 2017.05.05
(재귀함수) $n!$ ($n$ 의 계승) 구하기  (0) 2017.04.29
(재귀함수) 자(ruler)의 눈금 그리기  (0) 2017.04.29
N-queens 문제  (0) 2016.03.31
달팽이 배열  (0) 2016.03.29
하노이의 탑  (0) 2016.03.19