[24.06.07] 99클럽 코테 스터디 19일차 TIL - 점화식과 대표적인 예제

1. 점화식

점화식이란 수열의 각 항이 이전 항들의 값을 이용해서 정의되는 식을 말한다. 즉 이전 항들의 값을 이용하여 다음 항의 값을 계산하는 방법을 말한다.

 

1.1 대표적인 점화식

대표적인 점화식에는 등차수열, 등비수열, 팩토리얼, 피보나치 수열 등이 있다.

 

1.1.1 등차수열

• 연속하는 두 항 사이의 차이가 일정한 수열이다.
• 점화식(일반항) : a_n = a_1 + (n-1)d
  첫째항을 a_1, 공차를 d라고 했을 때 n번째 항은 구하는 수식이다.

def arithmetic_sequence(n, a_1, d):
    if n == 1:
        return a_1
    else:
        return arithmetic_sequence(n-1, a_1, d) + d

# 예시: 등차수열의 5번째 항을 구하는 경우 (첫 번째 항이 2이고, 공차가 3인 경우)
print(arithmetic_sequence(5, 2, 3))  # Output: 14

 

1.1.2 등비수열

• 연속하는 두 항 사이의 비가 일정한 수열이다.
• 점화식(일반항) : a_n = a_1 * r^{n-1}
  첫째항을 a_1, 공비를 r이라 했을 때 n번째 항을 구하는 수식이다.

def geometric_sequence(n, a_1, r):
    if n == 1:
        return a_1
    else:
        return geometric_sequence(n-1, a_1, r) * r

# 예시: 등비수열의 5번째 항을 구하는 경우 (첫 번째 항이 2이고, 공비가 3인 경우)
print(geometric_sequence(5, 2, 3))  # Output: 162

 

1.1.3 팩토리얼

• 양의 정수 n에 대해 n부터 1까지의 모든 양의 정수를 곱한 값을 말한다.
• 점화식 : n! = n * (n-1)!

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

# 예시: 5!을 구하는 경우
print(factorial(5))  # Output: 120

 

1.1.4 피보나치 수열

• 첫번째 항과 두번째 항의 값은 1이고, 그 이후의 항은 이전 두 항의 합으로 이루어진 수열이다.
• 점화식 : F(n) = F(n-1) + F(n-2), F(1) = 1, F(0) = 1 (0부터 시작한다고 가정)

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# 예시: 피보나치 수열의 7번째 항을 구하는 경우
print(fibonacci(7))  # Output: 13

 

1.2 점화식을 세우는 방법

1. 패턴 파악 : 주어진 문제에서 어떠한 패턴이 있는 지 파악한다. (전체 문제를 부분 문제로 어떻게 나눌 수 있는지 파악한다.)
   n번째 항이 n-1번째 항과 어떤 연관이 있는지를 중점으로 패턴을 파악해보는 연습이 필요하다.
2. 점화식 정의 : 발견한 패턴을 바탕으로 각 항을 이전 항들의 함수로 정의한다. 
3. 초기 조건 설정 : 수열의 시작 부분인 초기의 항을 정의한다. (대부분의 경우 첫 번째 몇 개의 항을 직접 지정해주어야 한다.)
4. 점화식 검증 : 점화식이 주어진 문제를 저확히 모델링하는지 확인한다.