[코드트리 조별과제] 3주차 정리(출력결과 18 / 출력결과 29 / 재귀함수를 이용한 최소공배수)

 

재귀함수는

한 번 꼬이게 되면

헷갈리기 때문에

확실한 이해, 설계가 중요한 것 같다.

 

자주 접해도 헷갈리는 재귀함수다......🤣

 

 

 

학습내용

출력결과 18

 

[코드트리] 출력결과 18

 

 

각 함수의 기능은 다음과 같다.

• g(): _list의 a~b범위 중 x이하의 숫자 개수 카운트
• f(): _list의 a~b범위 중 x이하의 숫자 중 인덱스가 k번째인 숫자 이분 탐색 

f(0, 9, 5, 6)일때를 표로 진행상황을 아래의 표처럼 나타낼 수 있다.

 

 

return f(a, mid, x, k) if cnt >= k else f(mid + 1, b, x, k - cnt)

if의 True, False따라 인자가 달라지는 점을 유의해야한다.

 

각 값에 대한 g()의 범위는 다음과 같다.

f(7, 7, 5, 1)때

_list[7]인 2가 return된다.

 

 

 

 

 

---

 

출력결과 29

 

[코드트리] 출력결과 29

 

 

 

 

그림으로 나타냈을 때 우측에 있는 함수에

*b를 해준다는 점을 빠트리면 안된다.

 

풀기엔 쉬운 문제였지만

계산실수를 조심해야한다.

 

 

 

728x90

 

---

 

재귀함수를 이용한 최소공배수

 

[코드트리] 재귀함수를 이용한 최고공배수

 

n = int(input())
arr = list(map(int, input().split()))

def lcm(num, idx):
    if idx == -1:
        return num
    for i in range(max(arr[idx], num), arr[idx]*num + 1):
        if i % arr[idx] == 0 and i % num == 0:
            return lcm(i, idx-1)

print(lcm(arr[n-1], n-2))

 

n번 인덱스의 요소부터 n-n까지의 요소를

비교하는 방식으로 코드를 작성했다.

 

최소공배수는 for문을 사용해서 구한다.

 

num 👉 현재 최소공배수

idx 👉 현재 인덱스

 

현재 최소공배수, 인덱스의 최소공배수를 구하고

이와 함께 idx-1을 하여 재귀함수 진행한다.

 

list = [1, 2, 3, 4, 5, 6]인 경우