재귀함수 - 백준 24060, 2447, 11729

재귀함수란 조건을 만족하지 않으면 나 자신을 다시 호출하는 함수이다.

재귀함수는 반복문으로도 풀 수 있지만 반복하는 조건에 따라 재귀함수로 훨씬 간결하고 멋있게 풀 수도 있다.

다만 메모리 스택에 많이 쌓이는 것이 단점으로 꼽힌다.

 

재귀함수적 사고를 하는 건 매우 어렵다...나역시 아직까지도 완벽하지 않고 한참 부족하다고 생각한다...

그러나 문제를 풀어가면서 조금씩 나아지는 내 모습을 발견할 수 있었다.

 

이번에도 문제를 몇 개 리뷰해보면서 글을 마무리지으려한다.

 

https://www.acmicpc.net/problem/24060

24060번: 알고리즘 수업 - 병합 정렬 1

병합 정렬에 관한 문제였다

병합정렬이란 간단하게 설명하면 정렬되지 않은 한 배열을 작은 단위로 쪼개어 합쳐가는 방식이다.

병합이 이루어지는 단계는 쪼개는 단계에서가 아닌 합치는 단계에서 카운트가 되므로 이를 이해한다면

병합정렬은 100%이해했다고 볼 수 있다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

병합정렬에 대한 자세한 이해는 위 글을 참조하시길...

 

import sys
input = sys.stdin.readline

def merge_sort(L):	#병합정렬 함수로 매개변수로 length를 받는다.
    if len(L) == 1:	#매개변수L이 1이라면 L을 return해준다
        return L	#여기서 Len이 1인 L은 가장 작은 단위로 쪼개졌음을 의미한다.
    
    mid = (len(L)+1)//2	#Len에 1을 더해서 연산해주는 이유는 문제에서 원본 배열의 길이가 홀수라면left 배열이 더 작게 만들어지도록 풀었으므로
   						#예제 함수와 같게 동작하게끔 1을 더해주었다.
    left = merge_sort(L[:mid])	# L이 1이 아니라면 중간단위로 쪼개서 재귀함수 실행
    right = merge_sort(L[mid:])
    
    i,j = 0,0	#return할 배열에 넣은 갯수를 count해줄 변수
    L2 = []		#return할 배열
    while i < len(left) and j < len(right): #나눈 배열들의 길이가 i와j보다 작다면 실행된다 
        if left[i] < right[j]:	#왼쪽 배열과 오른쪽 배열에서 오른쪽 배열이 더 크다면
            L2.append(left[i])	#오름차순 정렬이므로 return배열에 left[i]값 추가
            ans.append(left[i])	#정답배열에도 추가해준다
            i+=1		#i의 값을 추가했으므로 i에 1을 더해준다
        else:
            L2.append(right[j])	#else라면 right값이 더 크므로 위와 같은 동작을 한다.
            ans.append(right[j])
            j+=1
    while i < len(left):	#위에 있는 while문이 끝났다면 어느 한쪽 배열은 모두 return배열에 들어갔음을 의미함
        L2.append(left[i])	#그럼에도 left나 right배열중에 남은 값이 있을 수 있으므로
        ans.append(left[i])	#남은 값을 전부 return할 배열에 넣어준다.
        i+=1
    while j < len(right):
        L2.append(right[j])
        ans.append(right[j])
        j+=1
    
    return L2		#모든 동작이 끝나면 L2배열을 return해줌

n, k = map(int, input().split()) 	
a = list(map(int,input().split()))

ans = []	#정답으로 쓸 배열
merge_sort(a)	#재귀함수 실행

if len(ans) >= k :	#함수의 길이가 k보다 크다면 조건을 만족하므로 print실행
    print(ans[k-1])
else :		#k보다 작다면 -1 출력
    print(-1)

꽤 긴 코드이지만 이해하기 쉬워서 풀고나서 만족도가 높았다!

 

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

처음 풀어본 골드5문제였다..

조금 겁먹기도 했고 꽤 오랜시간 고전했으나 혼자 힘으로 풀어내서 아주 좋았다!!

여기서 겪은 문제는 사각형 단위가 쪼개져도 주어진 input값만큼 실행을 시켰어야했는데

이 부분을 코드로 구현하기가 너무 헷갈렸다. for문을 이미 2개나 사용한 상태였는데 3개나 써도 될까?했지만 

이로써 정답을 구할 수 있었다. 다른 사람이 풀어낸 풀이가 훨씬 간결하고 좋았지만 스스로 풀어냄에 의의를 뒀다.

a = int(input())
arr = [['*' for _ in range(a)]for _ in range(a)] #input의 크기만큼 2차원 배열을 만든다.

def makeEmpty(C,target) :
    if C == 1 :    #n/3의 값이 1이라면 return해주는 조건
        return
    makeEmpty(C//3, target)    #1이 아니라면 재귀 실행
    idx = C//3            #index로 사용할 변수
    gap = C//3            #index에 더해줄 gap변수
    while idx < target :  #index가 input의 초기값인 target보다 크면 break
        for i in range(idx,idx + gap) :    #row값
            for j in range(gap,target,C) : #column값 C만큼 증가
                for k in range(j,j+gap) :  #row와 column을 받아 공백을 집어넣을 반복문
                    arr[i][k] =' '
        idx += C    #위 연산이 모두 끝나면 index에 해당 함수 내의 C값만큼 더해준다.

makeEmpty(a,a)
for s in arr :
    print(*s,sep='',end='\n') #2차원 배열이므로 원소를 출력하되 간격은 공백, 끝나는 지점은 줄바꿈

 

마지막 문제다

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

하노이 탑에 관한 문제였는데 원리도 이해했지만

정답을 출력하는 형식이 도저히 떠오르지 않았다... 그래서 다른 분의 풀이를 보고

아!!!를 외치면서 똑같이 작성했다. 내가 보고 참고한 글을 통해 정확히 이해하길 바란다.

def hanoi(n,start,end) :
    if n == 1 :
        print(start,end)
        return
    
    hanoi(n-1,start,6-end-start)
    print(start,end)
    hanoi(n-1,6-end-start,end)

a = int(input())
print(2**a - 1)
hanoi(a,1,3)

https://study-all-night.tistory.com/6

[백준 11729번] 하노이 탑 이동순서 - Python(파이썬) 자세한 풀이