실습_1. 재귀호출

실습

k번째 수 찾기

nn개의 숫자가 차례대로 주어질 때, 매 순간마다 “지금까지 입력된 숫자들 중에서 k번째로 작은 수”를 반환하는 프로그램을 작성하세요.

프로그램의 입력으로는 첫째줄에 nn과 kk가 입력되고, 둘째줄에 nn개의 숫자가 차례대로 주어집니다.

• 입력 예시

10 3
1 9 8 5 2 3 5 6 2 10

• 출력 예시

-1 -1 9 8 5 3 3 3 2 2

• 문제 조건

nn은 100보다 작은 숫자입니다.
매 순간마다 지금까지의 입력중 kk번째로 작은 수를 출력하되, 없다면 -1을 출력합니다.

• 입출력 예시 설명

10개의 숫자가 차례대로 주어집니다. 맨 처음 1만 입력을 받았을 경우, 3번째로 작은 숫자가 없으므로 -1을 출력합니다. 그 다음 9도 마찬가지입니다. 세 번째로 숫자 8을 입력받는 순간, 지금까지 입력받은 숫자는 1, 9, 8 세 개이고, 이 중 3 번째로 작은 숫자인 9를 출력합니다. 마찬가지로 숫자 하나를 입력받을 때 마다 3번째로 작은 숫자를 출력합니다.

def findKth(myInput, k) :
    '''
    매 순간마다 k번째로 작은 원소를 리스트로 반환합니다.
    '''

    result = []
    
    arr = []
    
    for i in myInput:
        arr.append(i)
        if len(arr) < k:
            result.append(-1)
        else:
            arr.sort()
            result.append(arr[k-1])

    return result

def main():
    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    firstLine = [int(x) for x in input().split()]
    myInput = [int(x) for x in input().split()]

    print(*findKth(myInput, firstLine[1]))
if __name__ == "__main__":
    main()

quick sort

입력으로 nn개의 수가 주어지면, quick sort를 구현하는 프로그램을 작성하세요.

• 입력 예시

10 2 3 4 5 6 9 7 8 1 

• 출력 예시

1 2 3 4 5 6 7 8 9 10

def quickSort(array):
    '''
    퀵정렬을 통해 오름차순으로 정렬된 array를반환하는 함수를 작성하세요.
    '''
    
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    
    left = []
    right = []
    
    for i in range(1, len(array)):
        if array[i]<=pivot:
            left.append(array[i])
        else:
            right.append(array[i])
    print(left, right)
    return quickSort(left) + [pivot] + quickSort(right) 

def main():
    line = [int(x) for x in input().split()]

    print(*quickSort(line))

if __name__ == "__main__":
    main()

올바른 괄호인지 판단하기

본 문제에서는 입력으로 주어지는 괄호가 올바른 괄호인지를 판단하는 프로그램을 작성합니다.

예를 들어, ‘(())’ 은 올바른 괄호이지만, ‘(()))’, 혹은 ‘(()()(‘ 는 올바른 괄호가 아닙니다.

올바른 괄호일때 ‘YES’를, 올바르지 않은 괄호일때 ‘NO’를 출력해 봅시다.

• 입력 예시 1

(())()

• 출력 예시 1

YES

• 입력 예시 2

(((())())(()())((())()))

• 출력 예시 2

YES

• 입력 예시 3

(())())()

• 출력 예시 3

NO

• 입력 예시 4

((()())(()())))(())

• 출력 예시 4

NO

• 입력
  괄호 pp가 주어집니다.

• 출력
  pp가 올바른 괄호이면 YES, 그렇지 않으면 NO를 출력합니다.

def checkParen(p):
    '''
    괄호 문자열 p의 쌍이 맞으면 "YES", 아니면  "NO"를 반환
    '''
    
    if p == '':
        return 'YES'
    
    arr = ''
    for i in range(len(p)):
        if i-1>=0 and p[i-1] == '(' and p[i] == ')':
            continue
        if i+1<len(p) and p[i] == '(' and p[i+1] == ')':
            continue
        arr+=p[i]
    print(arr)
    
    if arr != '' and arr == p:
        return "NO"
    
    return checkParen(arr)

def main():
    '''
    Do not change this code
    '''

    x = input()
    print(checkParen(x))

if __name__ == "__main__":
    main()

미션

이진수 변환

10진수를 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단, 재귀호출을 이용하여 작성합니다.

• 입력 예시

19

• 출력 예시

10011

• 문제 조건 입력되는 10진수는 1,000,000 이하의 자연수 입니다.

import sys
sys.setrecursionlimit(100000)

def convertBinary(n) :
    '''
    10진수 n을 2진수로 변환하여 반환합니다.

    *주의* : 변환된 2진수는 문자열이어야 합니다.

    예를 들어, 19가 입력될 경우 문자열 "10011"이 반환되어야 합니다.
    '''
    
    if n == 1:
        return str(n%2)
    
    return convertBinary(n//2) + str(n%2)

def main():
    '''
    이 부분은 수정하지 마세요.
    '''


    n = int(input())

    print(convertBinary(n))

if __name__ == "__main__":
    main()

문자열 포함 관계 조사

두 문자열 A, B가 주어질 때, A의 모든 알파벳이 문자열 B에 존재하는지 판별하는 프로그램을 작성하세요. 예를 들어, A = “mef” 이고, B = “myself” 라면 A의 모든 알파벳이 B에 존재합니다. 하지만 A = “abca”, B = “acf” 일 경우에는 A의 모든 알파벳이 B에 존재하지 않습니다. 재귀호출을 이용하여 작성하도록 합니다.

프로그램에는 첫째줄에 A가, 둘째줄에 B가 입력됩니다.

A가 B에 포함된다면 “Yes”를 아니라면 “No”를 출력해 봅시다.

• 입력 예시 1

mef
myself

• 출력 예시 1

Yes

• 입력 예시 2

abca
acf

• 출력 예시 2

No

• 문제 조건 문자열의 길이는 100을 넘지 않습니다.

import sys
sys.setrecursionlimit(100000)

def strContain(A, B) :
    '''
    문자열 A의 알파벳이 문자열 B에 모두 포함되어 있으면 "Yes", 아니면 "No"를 반환합니다.
    '''
    
    if A in B:
        return 'Yes'
    
    strs = A
    if strs[0] in B:
        strs = strs[1:]
    print(strs)
    
    if strs != '' and strs == A:
        return "No"
        
    return strContain(strs, B)
    
def main():
    '''
    Do not change this code
    '''

    A = input()
    B = input()

    print(strContain(A, B))

if __name__ == "__main__":
    main()

최대공약수 구하기

두 자연수 xx, yy의 최대공약수를 출력하는 프로그램을 작성하세요.

이 문제에서는 유클리드 호제법을 이용하여 두 자연수의 최대공약수를 구합니다.

유클리드 호제법을 간단하게 이야기하면 다음과 같습니다.

gcd(xx, yy) 를 xx와 yy의 최대공약수라고 정의합니다. 그러면 다음의 식이 성립합니다.

gcd(xx, yy) = gcd(yy, xx%yy)

예를 들어, 1071과 1029의 최대공약수는 따라서 다음과 같이 구할 수 있습니다.

gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = 21

참고로 gcd(42, 21) = 21 인 이유는, 42가 21로 나누어 떨어지기 때문에 42와 21의 최대공약수는 21이 됩니다.

자세한 설명은 다음의 링크를 참고해주세요. 위의 예제 또한 이 링크에서 발췌되었습니다.

• 입력 예시

6 4

• 출력 예시

2

def GCD(x, y) :
    '''
    x, y의 최대공약수를 반환하는 함수
    '''
    if x % y == 0:
        return y

    return GCD(y, x%y)

def main():
    '''
    Do not change this code
    '''

    data = input()

    x = int(data.split()[0])
    y = int(data.split()[1])

    print(GCD(x, y))

if __name__ == "__main__":
    main()

순열 구하기

순열이란, nn개의 원소 중에서 rr개를 나열하는 것을 의미합니다. 예를 들어, 4개의 원소 중에서 2개를 나열한다고 하고, 우리가 갖고있는 원소가 ‘a’, ‘b’, ‘c’, ‘d’라면, 그 순열은 ‘ab’, ‘ac’, ‘ad’, ‘ba’, ‘bc’, ‘bd’, ‘ca’, ‘cb’, ‘cd’, ‘da’, ‘db’, dc’ 로써 총 12개의 서로 다른 경우가 존재합니다.

입력으로 nn과 rr이 주어질 때, nn개의 원소 중에서 rr개를 나열한 결과를 출력하는 프로그램을 작성하세요. 단, 원소는 항상 ‘a’부터 시작하여 nn개의 알파벳이라고 가정합니다.

• 입력 예시

4 2

• 출력 예시

ab
ac
ad
ba
bc
bd
ca
cb
cd
da
db
dc

def getPermutation(n, r) :
    '''
    n개의 알파벳 중에서 r개를 뽑아 나열한 결과를 리스트로 반환합니다.

    예를 들어, n = 4, r = 2 일 경우에는
    
    ["ab", "ac", "ad", "ba", "bc", "bd", "ca", "cb", "cd", "da", "db", dc"] 를 반환합니다.
    '''
    
    strs = 'abcdefghijklmnopqrstuvwxyz'
        
    result = []
    
    check = [False for i in range(26)]
    
    def ham(s, cnt, no):
    
        if cnt == r:
            result.append(s)
            return
        
        for i in range(n):
            if not check[i]:
                check[i] = True
                ham(s+strs[i],cnt+1,i)
                check[i] = False
    
    ham('', 0, -1)
    
    return result

def main():
    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    firstLine = [int(x) for x in input().split()]

    print('\n'.join(getPermutation(firstLine[0], firstLine[1])))

if __name__ == "__main__":
    main()

가로수

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있습니다. 도시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있습니다. 도시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶습니다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수입니다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 됩니다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 합니다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하세요. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있습니다.

• 입력 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 NN이 주어집니다. 둘째 줄부터 NN개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 주어집니다.

• 입력 예시

4
1
3
7
13

출력 예시

3

def howManyTree(n, myInput) :
    '''
    모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 리턴하는 함수를 구현하세요.
    '''
    
    min_len = 100000000
    max_len = 0
    
    myInput.sort()
    
    print(myInput)
    
        
    def ham(x, y):
        if x % y == 0:
            return y
        
        return ham(y, x % y)
        
    num = myInput[1] - myInput[0]
    
    for i in range(1,len(myInput)-1):
        print(num)
        num = ham(num,myInput[i+1] - myInput[i])
    
    print(num)
    
    
    cnt = (myInput[n-1] - myInput[0])/num + 1 - n
    
    return int(cnt)

def main():
    '''
    수정하시면 안됩니다.
    '''
    n = int(input())
    myInput = []
    for _ in range(n) :
        myInput.append(int(input()))

    print(howManyTree(n, myInput))
if __name__ == "__main__":
    main()