λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
Language/Python

[Python]파이썬 ν•¨μˆ˜ ν™œμš©ν•˜κΈ°: μž¬κ·€ ν•¨μˆ˜λΆ€ν„° 리슀트 ν‰νƒ„ν™”κΉŒμ§€

by YJ Dev 2024. 4. 15.
728x90
λ°˜μ‘ν˜•
SMALL

python μž¬κ·€ ν•¨μˆ˜λŠ” 자기 μžμ‹ μ„ ν˜ΈμΆœν•˜μ—¬ 문제λ₯Ό ν•΄κ²°ν•˜λŠ” 데에 μ‚¬μš©λ©λ‹ˆλ‹€. 이λ₯Ό 톡해 μ½”λ“œμ˜ κ°„κ²°μ„±κ³Ό 가독성을 높일 수 μžˆμŠ΅λ‹ˆλ‹€. python μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ νŒ©ν† λ¦¬μ–Ό, ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄, 그리고 리슀트 평탄화λ₯Ό κ΅¬ν˜„ν•˜λŠ” 방법에 λŒ€ν•΄ μ•Œμ•„λ³΄κ² μŠ΅λ‹ˆλ‹€.

ν•¨μˆ˜ ν™œμš©


1. μž¬κ·€ν•¨μˆ˜πŸŽ‘

μž¬κ·€ ν•¨μˆ˜μ—μ„œ κΈ°λ³Έ 단계와 μž¬κ·€ λ‹¨κ³„λŠ” 문제λ₯Ό ν•΄κ²°ν•˜λŠ”λ° μ€‘μš”ν•œ κ°œλ…μž…λ‹ˆλ‹€.

  • κΈ°λ³Έ 단계(base case) : κΈ°λ³Έ λ‹¨κ³„λŠ” μž¬κ·€ ν•¨μˆ˜μ—μ„œ λ¬΄ν•œ λ°˜λ³΅μ„ 막기 μœ„ν•œ μ€‘μš”ν•œ μš”μ†Œμž…λ‹ˆλ‹€. ν•¨μˆ˜κ°€ 더 이상 μžμ‹ μ„ ν˜ΈμΆœν•˜μ§€ μ•Šκ³  μ’…λ£Œλ˜λŠ” 쑰건을 λ§ν•©λ‹ˆλ‹€. κΈ°λ³Έ 단계λ₯Ό 톡해 μž¬κ·€ ν•¨μˆ˜κ°€ λλ‚˜κ³  κ²°κ³Όλ₯Ό λ°˜ν™˜ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
  • μž¬κ·€ 단계(recursive case) : μž¬κ·€ λ‹¨κ³„λŠ” μž¬κ·€ ν•¨μˆ˜μ—μ„œ 자기 μžμ‹ μ„ ν˜ΈμΆœν•˜μ—¬ 문제λ₯Ό ν•΄κ²°ν•˜λŠ” 과정을 λ§ν•©λ‹ˆλ‹€. 이 κ³Όμ •μ—μ„œλŠ” 주어진 문제λ₯Ό 더 μž‘μ€ ν•˜μœ„ 문제둜 λ‚˜λˆ„κ³ , 이 ν•˜μœ„ 문제λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄ μž¬κ·€μ μœΌλ‘œ 자기 μžμ‹ μ„ ν˜ΈμΆœν•©λ‹ˆλ‹€. 이 과정은 κΈ°λ³Έ 단계에 도달할 λ•Œ κΉŒμ§€ λ°˜λ³΅λ©λ‹ˆλ‹€.

μœ„ 두 가지 단계λ₯Ό νŒ©ν† λ¦¬μ–Όμ„ κ΅¬ν•˜λŠ” 예제λ₯Ό 톡해 확인해 λ³΄κ² μŠ΅λ‹ˆλ‹€.


πŸ™Œ μ—¬κΈ°μ„œ 잠깐!

νŒ©ν† λ¦¬μ–Όμ΄λž€?

μ–‘μ˜ μ •μˆ˜ n에 λŒ€ν•΄ n!둜 ν‘œν˜„λ˜λ©°, nλΆ€ν„° 1κΉŒμ§€μ˜ λͺ¨λ“  μ–‘μ˜ μ •μˆ˜λ₯Ό κ³±ν•œ κ°’μž…λ‹ˆλ‹€.

κ°„λ‹¨νžˆ 말해 n!은 1λΆ€ν„° nκΉŒμ§€μ˜ λͺ¨λ“  μ–‘μ˜ μ •μˆ˜λ₯Ό κ³±ν•œ κ°’μž…λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, 5의 νŒ©ν† λ¦¬μ–Όμ€ 5! = 5 x 4 x 3 x 2 x 1 = 120μž…λ‹ˆλ‹€.

# μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ νŒ©ν† λ¦¬μ–Όμ„ κ³„μ‚°ν•˜λŠ” ν•¨μˆ˜
def factorial_recursive(n):
    # κΈ°λ³Έ 단계: n이 0일 λ•Œ 1을 λ°˜ν™˜ν•˜μ—¬ μž¬κ·€ ν˜ΈμΆœμ„ 멈좀
    if n == 0:
        return 1
    # μž¬κ·€ 단계: n에 λŒ€ν•œ νŒ©ν† λ¦¬μ–Όμ„ n-1에 λŒ€ν•œ νŒ©ν† λ¦¬μ–Όκ³Ό κ³±ν•˜μ—¬ λ°˜ν™˜
    else:
        return n * factorial_recursive(n - 1)

# νŒ©ν† λ¦¬μ–Ό 계산 예제
print(factorial_recursive(5))  # 좜λ ₯: 120

2.νŒ©ν† λ¦¬μ–Ό κ΅¬ν•˜κΈ°πŸŽ²

νŒ©ν† λ¦¬μ–Ό κ³„μ‚°μ—μ„œλŠ” λ°˜λ³΅λ¬Έμ„ μ‚¬μš©ν•˜λŠ” 방법과 μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜λŠ” 방법이 μžˆμŠ΅λ‹ˆλ‹€.

두 가지 μ ‘κ·Ό λ°©μ‹μ˜ 차이λ₯Ό μ΄ν•΄ν•˜κΈ° μœ„ν•΄ 예제λ₯Ό 톡해 확인해 λ³΄κ² μŠ΅λ‹ˆλ‹€.

# λ°˜λ³΅λ¬Έμ„ μ‚¬μš©ν•˜μ—¬ νŒ©ν† λ¦¬μ–Όμ„ κ³„μ‚°ν•˜λŠ” ν•¨μˆ˜
def factorial_iterative(n):
    result = 1  # κ²°κ³Όλ₯Ό μ €μž₯ν•  λ³€μˆ˜ μ΄ˆκΈ°ν™”
    for i in range(1, n + 1):  # 1λΆ€ν„° nκΉŒμ§€ 반볡
        result *= i  # 각 숫자λ₯Ό μ°¨λ‘€λ‘œ κ³±ν•˜μ—¬ 결과에 λˆ„μ 
    return result  # μ΅œμ’… κ²°κ³Ό λ°˜ν™˜

# μž¬κ·€ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ νŒ©ν† λ¦¬μ–Όμ„ κ³„μ‚°ν•˜λŠ” ν•¨μˆ˜
def factorial_recursive(n):
    # κΈ°λ³Έ 단계: 0! = 1
    if n == 0:
        return 1
    # μž¬κ·€ 단계: n! = n * (n-1)!
    else:
        return n * factorial_recursive(n - 1)

# νŒ©ν† λ¦¬μ–Ό 계산 예제
print(factorial_iterative(5))  # 좜λ ₯: 120
print(factorial_recursive(5))  # 좜λ ₯: 120

반볡문으둜 νŒ©ν† λ¦¬μ–Ό κ΅¬ν•˜κΈ°
μž¬κ·€ν•¨μˆ˜λ‘œ νŒ©ν† λ¦¬μ–Ό κ΅¬ν•˜κΈ°


μœ„ 예제λ₯Ό 톡해 ν•œ 가지 문제λ₯Ό ν•΄κ²°ν•˜λŠ” λ‹€μ–‘ν•œ μ•Œκ³ λ¦¬μ¦˜μ΄ μ‘΄μž¬ν•œλ‹€λŠ” 것을 이해할 수 μžˆμŠ΅λ‹ˆλ‹€.

μž¬κ·€ ν•¨μˆ˜μ™€ λ°˜λ³΅λ¬Έμ€ 같은 문제λ₯Ό ν•΄κ²°ν•˜μ§€λ§Œ, 각각의 방식은 μ‹€ν–‰ μ†λ„λ‚˜ λ©”λͺ¨λ¦¬ μ‚¬μš© λ“±μ—μ„œ 차이가 μžˆμ„ 수 μžˆμŠ΅λ‹ˆλ‹€.

일반적으둜 νŒ©ν† λ¦¬μ–Ό κ³„μ‚°μ—μ„œλŠ” λ°˜λ³΅λ¬Έμ„ μ‚¬μš©ν•œ 방법이 μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•œ 방법보닀 νš¨μœ¨μ μž…λ‹ˆλ‹€.

μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜λ©΄ ν•¨μˆ˜ 호좜 μ‹œλ§ˆλ‹€ μŠ€νƒμ— 호좜 정보가 μ €μž₯λ˜λ―€λ‘œ, λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ΄ 더 λ§Žμ•„μ§‘λ‹ˆλ‹€. λ°˜λ©΄μ— λ°˜λ³΅λ¬Έμ„ μ‚¬μš©ν•˜λ©΄ 좔가적인 λ©”λͺ¨λ¦¬λ₯Ό μ‚¬μš©ν•˜μ§€ μ•Šκ³ λ„ λ™μΌν•œ μž‘μ—…μ„ μˆ˜ν–‰ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

일반적으둜 μž¬κ·€ ν•¨μˆ˜λŠ” ν•¨μˆ˜ ν˜ΈμΆœμ— λ”°λ₯Έ μ˜€λ²„ν—€λ“œκ°€ λ°œμƒν•˜κΈ° λ•Œλ¬Έμ— λ°˜λ³΅λ¬Έλ³΄λ‹€ 느릴 수 μžˆμŠ΅λ‹ˆλ‹€. 특히 νŒ©ν† λ¦¬μ–Όκ³Ό 같은 κ°„λ‹¨ν•œ κ³„μ‚°μ—μ„œλŠ” μž¬κ·€ ν•¨μˆ˜κ°€ λ°˜λ³΅λ¬Έλ³΄λ‹€ 더 λ§Žμ€ μ‹œκ°„μ΄ μ†Œμš”λ  수 μžˆμŠ΅λ‹ˆλ‹€.

λ”°λΌμ„œ 효율적인 μ•Œκ³ λ¦¬μ¦˜μ„ μ„ νƒν•œλ‹€λ©΄, νŒ©ν† λ¦¬μ–Ό κ³„μ‚°μ—μ„œλŠ” λ°˜λ³΅λ¬Έμ„ μ‚¬μš©ν•˜λŠ” 것이 μ’‹μŠ΅λ‹ˆλ‹€.

κ·ΈλŸ¬λ‚˜ μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•œ μ•Œκ³ λ¦¬μ¦˜λ„ 문제λ₯Ό ν•΄κ²°ν•˜λŠ” λ°μ—λŠ” 적합할 수 있으며, μ•Œκ³ λ¦¬μ¦˜μ˜ νŠΉμ„±κ³Ό 문제의 λ³΅μž‘μ„±μ— 따라 λ‹€λ₯Έ 선택이 ν•„μš”ν•  수 μžˆμŠ΅λ‹ˆλ‹€.;


3.ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄ κ΅¬ν˜„πŸ‘¨‍❀️‍πŸ‘¨πŸ‘¨‍❀️‍πŸ‘¨πŸ‘¨‍πŸ‘©‍πŸ‘§‍πŸ‘¦πŸ‘©‍πŸ‘¦‍πŸ‘¦πŸ‘¨‍πŸ‘¦‍πŸ‘¦

ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ€ 첫 번째 ν•­κ³Ό 두 번째 항이 각각 1이며, κ·Έ λ’€μ˜ λͺ¨λ“  항은 λ°”λ‘œ μ•žμ˜ 두항을 λ”ν•˜μ—¬ λ§Œλ“€μ–΄μ§€λŠ” μˆ˜μ—΄μž…λ‹ˆλ‹€. μ•„λž˜ 그림을 ν†΅ν•΄μ„œ ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ˜ κ·œμΉ™μ„ 확인해 λ³΄κ² μŠ΅λ‹ˆλ‹€.

κ·Έλ¦Όμ—μ„œ 각 쀄은 ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ˜ 각 항을 λ‚˜νƒ€λƒ…λ‹ˆλ‹€. 각 항은 λ°”λ‘œ μ•žμ˜ 두항을 λ”ν•œ κ°’μž…λ‹ˆλ‹€.

ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄

ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ€ μžμ—°μŠ€λŸ½κ²Œ μž¬κ·€μ μΈ νŠΉμ„±μ„ 가지고 μžˆμŠ΅λ‹ˆλ‹€. 각 항은 이전 두 항을 λ”ν•œ κ°’μ΄λ―€λ‘œ, 이λ₯Ό μž¬κ·€μ μœΌλ‘œ κ³„μ‚°ν•˜λŠ” 것이 μ§κ΄€μ μž…λ‹ˆλ‹€. 그럼 예제둜 μ‚΄νŽ΄λ³ΌκΉŒμš”?

# ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ„ μž¬κ·€ν•¨μˆ˜λ‘œ κ³„μ‚°ν•˜λŠ” ν•¨μˆ˜
def fibonacci_recursive(n):
    # κΈ°λ³Έ 단계: 첫 λ²ˆμ§Έμ™€ 두 번째 항은 각각 0κ³Ό 1
    if n = 1:
        return n
    # μž¬κ·€ 단계: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄ 계산 예제
for i in range(10):
    print(fibonacci_recursive(i), end=" ")  # 좜λ ₯: 0 1 1 2 3 5 8 13 21 34


μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ„ 계산할 λ•Œ, λ™μΌν•œ 값이 μ—¬λŸ¬ 번 κ³„μ‚°λ˜λŠ” κ²½μš°κ°€ λ§ŽμŠ΅λ‹ˆλ‹€.

μœ„μ˜ μ˜ˆμ œμ—μ„œλŠ” ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ„ κ³„μ‚°ν•˜λŠ” 과정을 μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ μ‹œκ°ν™”ν•˜μ˜€μŠ΅λ‹ˆλ‹€.

ν•˜μ§€λ§Œ μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•  경우, μˆ˜μ—΄μ˜ 값이 κ³„μ‚°λ˜λŠ” κ³Όμ •μ—μ„œ 쀑볡 계산이 많이 λ°œμƒν•˜κ³ , ν•¨μˆ˜ 호좜이 μ§€μˆ˜μ μœΌλ‘œ μ¦κ°€ν•˜μ—¬ μˆ˜μ—΄μ˜ μΌλΆ€λ§Œμ„ κ³„μ‚°ν•˜λŠ” κ²½μš°μ—λ„ 계산 μ‹œκ°„μ΄ 맀우 κΈΈμ–΄μ§ˆ 수 μžˆμŠ΅λ‹ˆλ‹€.

λ”°λΌμ„œ μœ„μ˜ μ˜ˆμ œμ—μ„œλŠ” ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ˜ 값이 λ„ˆλ¬΄ λ§Žμ•„μ§€λŠ” 것을 λ°©μ§€ν•˜κΈ° μœ„ν•΄ 3번째 μˆ˜μ—΄κΉŒμ§€ λ§Œμ„ κ΅¬ν•΄λ³΄μ•˜μŠ΅λ‹ˆλ‹€.

μ΄λ ‡κ²Œ ν•¨μœΌλ‘œμ¨ μˆ˜μ—΄μ΄ μ–΄λ–»κ²Œ ν˜•μ„±λ˜λŠ”μ§€λ₯Ό κ°„λ‹¨ν•˜κ²Œ 확인할 수 μžˆμ—ˆμŠ΅λ‹ˆλ‹€.

μž¬κ·€ν•¨μˆ˜λ‘œ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄ κ΅¬ν˜„


μž¬κ·€ ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•˜μ—¬ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ„ 계산할 경우, ν•¨μˆ˜ 호좜이 μ§€μˆ˜μ μœΌλ‘œ μ¦κ°€ν•©λ‹ˆλ‹€.

F(n)을 계산할 λ•Œ F(n-1)κ³Ό F(n-2)λ₯Ό 계산해야 ν•˜λ―€λ‘œ, ν•¨μˆ˜ 호좜 νšŸμˆ˜λŠ” 2ⁿ에 λΉ„λ‘€ν•©λ‹ˆλ‹€.

λ”°λΌμ„œ n이 컀질수둝 계산 μ‹œκ°„μ΄ κΈ‰κ²©ν•˜κ²Œ μ¦κ°€ν•©λ‹ˆλ‹€.

μ΄λŸ¬ν•œ μ΄μœ λ“€λ‘œ 인해 ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ„ μž¬κ·€μ μΈ λ°©μ‹μœΌλ‘œ 계산할 λ•Œ μ‹œκ°„μ΄ 였래 걸릴 수 μžˆμŠ΅λ‹ˆλ‹€.


4. λ©”λͺ¨ν™”πŸ“Œ

ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ„ 계산할 λ•ŒλŠ” 쀑볡 계산을 ν”Όν•˜κΈ° μœ„ν•΄ λ©”λͺ¨μ΄μ œμ΄μ…˜ 기법 즉, λ©”λͺ¨ν™”λ₯Ό μ‚¬μš©ν•©λ‹ˆλ‹€.

이λ₯Ό 톡해 λ™μΌν•œ 값을 반볡적으둜 κ³„μ‚°ν•˜λŠ” 것을 λ°©μ§€ν•˜κ³ , 계산 νš¨μœ¨μ„±μ„ 높일 수 μžˆμŠ΅λ‹ˆλ‹€.

# λ©”λͺ¨ν™”λ₯Ό μ‚¬μš©ν•˜μ—¬ 쀑볡 계산을 ν”Όν•˜λŠ” ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄ ν•¨μˆ˜
memo = {}  # κ²°κ³Όλ₯Ό μ €μž₯ν•  λ©”λͺ¨μ΄μ œμ΄μ…˜ λ”•μ…”λ„ˆλ¦¬
def fibonacci_memo(n):
    if n = 1:  # κΈ°λ³Έ 단계: n이 0 λ˜λŠ” 1일 λ•Œ
        return n
    if n not in memo:  # λ©”λͺ¨μ΄μ œμ΄μ…˜: κ²°κ³Όκ°€ 아직 μ €μž₯λ˜μ§€ μ•Šμ•˜μ„ 경우
        # n-1κ³Ό n-2의 ν”Όλ³΄λ‚˜μΉ˜ 수λ₯Ό μž¬κ·€μ μœΌλ‘œ κ³„μ‚°ν•˜μ—¬ λ”ν•œ ν›„, κ²°κ³Όλ₯Ό λ©”λͺ¨μ΄μ œμ΄μ…˜
        memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
    return memo[n]  # λ©”λͺ¨μ΄μ œμ΄μ…˜λœ κ²°κ³Ό λ°˜ν™˜

# ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄ 계산 예제 (λ©”λͺ¨ν™” μ‚¬μš©)
for i in range(10):
    print(fibonacci_memo(i), end=" ")  # 좜λ ₯: 0 1 1 2 3 5 8 13 21 34

ν”Όλ³΄λ‚˜μΉ˜ λ©”λͺ¨ν™”

  1. memo = {}: κ²°κ³Όλ₯Ό μ €μž₯ν•  λ”•μ…”λ„ˆλ¦¬λ₯Ό μ„ μ–Έν•©λ‹ˆλ‹€. 이 λ”•μ…”λ„ˆλ¦¬λŠ” 이미 κ³„μ‚°λœ ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ˜ 값듀을 μ €μž₯ν•˜λŠ” 데 μ‚¬μš©λ©λ‹ˆλ‹€.
  2. def fibonacci_memo(n):: ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ„ κ³„μ‚°ν•˜λŠ” ν•¨μˆ˜λ₯Ό μ •μ˜ν•©λ‹ˆλ‹€. 이 ν•¨μˆ˜λŠ” 인자 n에 λŒ€ν•΄ ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ˜ 값을 λ°˜ν™˜ν•©λ‹ˆλ‹€.
  3. if n <= 1:: κΈ°λ³Έ 단계(base case)λ₯Ό μ²˜λ¦¬ν•©λ‹ˆλ‹€. λ§Œμ•½ n이 0 λ˜λŠ” 1이면, ν•΄λ‹Ή κ°’ κ·ΈλŒ€λ‘œ λ°˜ν™˜ν•˜κ³  μž¬κ·€ ν˜ΈμΆœμ„ 멈μΆ₯λ‹ˆλ‹€.
  4. if n not in memo:: λ©”λͺ¨μ΄μ œμ΄μ…˜μ„ μœ„ν•œ μ‘°κ±΄λ¬Έμž…λ‹ˆλ‹€. λ§Œμ•½ ν˜„μž¬ κ³„μ‚°ν•˜λ €λŠ” ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ˜ 값이 이미 λ©”λͺ¨μ΄μ œμ΄μ…˜λœ 결과에 μ—†λ‹€λ©΄, μž¬κ·€μ μœΌλ‘œ κ³„μ‚°ν•˜μ—¬ λ©”λͺ¨μ΄μ œμ΄μ…˜λœ κ²°κ³Όλ₯Ό λ”•μ…”λ„ˆλ¦¬μ— μ €μž₯ν•©λ‹ˆλ‹€.
  5. memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2): ν˜„μž¬ κ³„μ‚°ν•˜λ €λŠ” ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ˜ 값을 μž¬κ·€μ μœΌλ‘œ κ³„μ‚°ν•©λ‹ˆλ‹€. μ΄λ•Œ, 이미 λ©”λͺ¨μ΄μ œμ΄μ…˜λœ 값이 μžˆλ‹€λ©΄ ν•΄λ‹Ή 값을 μ‚¬μš©ν•˜μ—¬ 쀑볡 계산을 ν”Όν•©λ‹ˆλ‹€.
  6. return memo[n]: λ©”λͺ¨μ΄μ œμ΄μ…˜λœ κ²°κ³Όλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
  7. for i in range(10):: ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ˜ 처음 10개 값을 κ³„μ‚°ν•˜κΈ° μœ„ν•œ λ°˜λ³΅λ¬Έμ„ μ„€μ •ν•©λ‹ˆλ‹€.
  8. print(fibonacci_memo(i), end=" "): 각 μΈλ±μŠ€μ— λŒ€ν•΄ κ³„μ‚°λœ ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄μ˜ 값을 좜λ ₯ν•©λ‹ˆλ‹€.

5. 리슀트 ν‰νƒ„ν™”πŸ‘œ

리슀트 ν‰νƒ„ν™”λŠ” μ€‘μ²©λœ 리슀트λ₯Ό ν•˜λ‚˜μ˜ ν‰νƒ„ν•œ(1차원) 리슀트둜 λ§Œλ“œλŠ” μž‘μ—…μ„ λ§ν•©λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, [1, 2, [3, 4], [5, [6, 7]]]와 같은 μ€‘μ²©λœ λ¦¬μŠ€νŠΈκ°€ μžˆμ„ λ•Œ, 이λ₯Ό [1, 2, 3, 4, 5, 6, 7]κ³Ό 같이 ν‰νƒ„ν•œ 리슀트둜 λ§Œλ“œλŠ” κ²ƒμž…λ‹ˆλ‹€.

리슀트 ν‰νƒ„ν™”λŠ” μž¬κ·€μ μΈ λ¬Έμ œμž…λ‹ˆλ‹€. 리슀트 μ•ˆμ— 또 λ‹€λ₯Έ λ¦¬μŠ€νŠΈκ°€ 포함될 수 있고, μ΄λŸ¬ν•œ μ€‘μ²©λœ 리슀트λ₯Ό ν‰νƒ„ν™”ν•˜μ—¬ ν•˜λ‚˜μ˜ λ‹¨μΌν•œ 리슀트둜 λ§Œλ“œλŠ” μž‘μ—…μ€ μž¬κ·€μ μΈ 접근이 μ ν•©ν•©λ‹ˆλ‹€.

def flatten_list(lst):
    """
    μ€‘μ²©λœ 리슀트λ₯Ό ν‰νƒ„ν™”ν•˜λŠ” ν•¨μˆ˜
    
    Parameters:
        lst (list): 평탄화할 리슀트
        
    Returns:
        list: ν‰νƒ„ν™”λœ 리슀트
    """
    flattened = []  # ν‰νƒ„ν™”λœ 리슀트λ₯Ό μ €μž₯ν•  λ³€μˆ˜ μ΄ˆκΈ°ν™”
    for item in lst:  # 리슀트의 각 μš”μ†Œμ— λŒ€ν•΄ 반볡
        if isinstance(item, list):  # μš”μ†Œκ°€ λ¦¬μŠ€νŠΈμΈμ§€ 확인
            flattened.extend(flatten_list(item))  # 리슀트면 μž¬κ·€μ μœΌλ‘œ ν‰νƒ„ν™”ν•˜μ—¬ μΆ”κ°€
        else:
            flattened.append(item)  # λ¦¬μŠ€νŠΈκ°€ μ•„λ‹ˆλ©΄ κ·ΈλŒ€λ‘œ μΆ”κ°€
    return flattened  # ν‰νƒ„ν™”λœ 리슀트 λ°˜ν™˜

example_list = [1, 2, [3, 4, [5, 6]], 7, [8, [9, 10]]]  # 평탄화할 예제 리슀트
print(flatten_list(example_list))  # 좜λ ₯: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

리슀트 평탄화

  1. flatten_list ν•¨μˆ˜λŠ” μ€‘μ²©λœ 리슀트λ₯Ό λ°›μ•„μ„œ ν‰νƒ„ν™”λœ 리슀트λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
  2. ν•¨μˆ˜λŠ” λ°˜λ³΅λ¬Έμ„ μ‚¬μš©ν•˜μ—¬ 리슀트의 각 μš”μ†Œλ₯Ό ν™•μΈν•©λ‹ˆλ‹€.
  3. μš”μ†Œκ°€ 리슀트인 κ²½μš°μ—λŠ” μž¬κ·€μ μœΌλ‘œ flatten_list ν•¨μˆ˜λ₯Ό ν˜ΈμΆœν•˜μ—¬ ν‰νƒ„ν™”ν•œ κ²°κ³Όλ₯Ό μΆ”κ°€ν•©λ‹ˆλ‹€.
  4. μš”μ†Œκ°€ λ¦¬μŠ€νŠΈκ°€ μ•„λ‹Œ κ²½μš°μ—λŠ” κ·ΈλŒ€λ‘œ κ²°κ³Ό λ¦¬μŠ€νŠΈμ— μΆ”κ°€ν•©λ‹ˆλ‹€.
  5. μ΅œμ’…μ μœΌλ‘œ ν‰νƒ„ν™”λœ 리슀트λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

이 ν•¨μˆ˜λŠ” μž¬κ·€μ μΈ λ°©μ‹μœΌλ‘œ μ€‘μ²©λœ 리슀트λ₯Ό λͺ¨λ‘ νŽΌμ³μ„œ ν•˜λ‚˜μ˜ λ‹¨μΌν•œ 리슀트둜 λ§Œλ“­λ‹ˆλ‹€.


6. 핡심 λ‚΄μš©πŸ‘€

μž¬κ·€ν•¨μˆ˜
νŒ©ν† λ¦¬μ–Ό
ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄
ν”Όλ³΄λ‚˜μΉ˜μˆ˜μ—΄ λ©”λͺ¨ν™”
리슀트 평탄화

728x90
λ°˜μ‘ν˜•