알고리즘/자료구조 02 - 재귀 함수, 팩토리얼, 하노이 타워

재귀함수

 

팩토리얼

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

n = int(input())

def factorial(num):
    if num <= 1:
        return 1 # return 0 하니까 왜 에러나지?
    else:
        return num * factorial(num-1)

print(factorial(n))

 

하노이 타워 (재귀)

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

# n = 2일 경우 : 1, 2번 원판을
# 1) 1번 (1~n-1번) : From -> Sparse
# 2) 2번 (n번) : From -> To
# 3) 1번 (1~n-1번) : Sparse -> To
n = int(input())
move = []

def hanoi(num, F, S, T):
    if num == 1:
        move.append([F, T])
    else:
        hanoi(num-1, F, T, S)
        move.append([F, T])
        hanoi(num-1, S, F, T)

# hanoi(n, 'From', 'Sparse', 'To')
hanoi(n, 1, 2, 3)
print(len(move)) # 총 횟수
for m in move:
    print(m[0], m[1])

 

선택정렬 (재귀)

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

재귀를 쓰지 않는 선택 정렬

# 선택정렬
# 재귀를 쓰지 않는 선택 정렬

n = int(input())
Data = []
for _ in range(n):
    Data.append(int(input()))

def selectionSort(Data):
    for i in range(len(Data)):
        lowestIdx = i
        for j in range(i+1, len(Data)):
            if Data[j] < Data[lowestIdx]:
                lowestIdx = j
        Data[i], Data[lowestIdx] = Data[lowestIdx], Data[i]
    return Data

sortedData = selectionSort(Data)
for sd in sortedData:
    print(sd)

 

 

재귀를 사용하여 선택 정렬

# 런타임 에러!!!

# 선택정렬
# 재귀를 사용하여 선택 정렬

n = int(input())
Data = []
for _ in range(n):
    Data.append(int(input()))

def recursive(now):
    if now == len(Data) - 1:
        return
    # 현재위치 ~ 끝까지 중 가장 작은 원소의 위치
    minIdx = Data.index(min(Data[now:len(Data)])) 
    Data[now], Data[minIdx] = Data[minIdx], Data[now]
    recursive(now+1)

recursive(0)
for dt in Data:
    print(dt)