99클럽 코테 스터디 22일차 TIL + 동적계획법(DP)

오늘의 문제 - 동적계획법(DP)

프로그래머스 - 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

---

내 풀이 및 접근 방식

이 문제의 점화식을 찾으면 피보나치 수열 점화식과 같다. n칸을 가기 위한 방법은 n-1칸에서 한 칸을 가는 방법과 n-2칸에서 두 칸을 가는 방법을 더해주는 것이다. 식으로 표현하면 f(n) = f(n-1)+f(n-2)이다.

def solution(n):
    
    if n == 1:
        return 1
    elif n == 2:
        return 2
    
    answer = 0
    prev1 = 1
    prev2 = 2
    
    for i in range(3, n+1):
        answer = prev1 + prev2
        prev1 = prev2
        prev2 = answer
        
    return answer % 1234567

 

풀이

1. 기본 케이스 처리: n이 1, 2인 경우를 먼저 처리한다.
2. n이 3이상인 경우부터 for루프를 통해 피본나치 수열 점화식을 계산한다. i가 증가할 때마다 answer에 현재의 피보나치 수를 계산한 값을 저장하고, prev1과 prev2를 업데이트한다. prev1은 n-2칸을 가는 방법 수, prev2는 n-1칸을 가는 방법 수이다.
3. answer를 1234567로 나눈 나머지를 반환한다.

시간 복잡도

• for 루프가 3에서 n-2번까지 반복되며 각 반복에서 상수 시간 연산이 수행된다.

따라서, 시간복잡도는 O(n)이다.

---

다른 풀이

재귀+메모이제이션

import sys
sys.setrecursionlimit(5000)

def solution(n):
	memo = {}
    
    def dfs(steps):
    	if steps in memo:
        	return memo[steps]
        if steps == n:
        	return 1
        if steps > n:
        	return 0
        memo[steps] = dfs(steps+1) + dfs(steps+2)
        return memo[steps]
        
    return dfs(0) % 1234567

 

풀이

1. 메모이제이션 설정: memo라는 딕셔너리를 사용하여 이미 계산된 결과를 저장한다. 이를 통해 동일한 steps 값에 대해 중복 계산을 하지 않고, 저장된 결과를 바로 사용할 수 있다.
2. dfs: dfs는 현재 steps 만큼의 칸을 이동한 상태에서 나머지 steps 칸을 이동하는 방법의 수를 계산한다.
   - 이미 계산된 steps가 memo에 있다면 해당 값을 반환
   - steps가 n과 같다면 모든 칸을 이동하느 것이므로 1을 반환
   - steps가 n을 초과하면 칸 이동을 초과한 것으로 0을 반환
   - 위 경우가 모두 아니라면, dfs(steps+1)(한 칸 이동하기)과 dfs(steps+2)(두 칸 이동하기)의 결과를 더하여 memo[steps]에 저장하고 반환
3. dfs(0)을 호출하여 0에서 시작해 모든 칸을 이동하는 방법의 결과를 반환한 후 1234567로 나눈 나머지를 구한다.

시간 복잡도

• 재귀 호출이 최대 n번 일어나며, 메모이제이션 덕분에 각 호출은 한 번만 계산된다. 즉, dfs 함수는 n개의 서로 다른 steps에 대해 한 번씩 호출된다.

따라서, 시간복잡도는 O(n)이다.

 

sys.setrecursionlimit

python의 재귀 함수 호출 한도를 설정하는 함수이다. python은 기본적으로 재귀 호출의 깊이에 제한이 있어서, 이를 초과할 경우 RecursionError가 발생한다. 일반적으로 1000으로 제한되어있다. 무한 재귀를 방지하고, 메모리 초과를 예방하기 위해 재귀 깊이에 제한을 두고 있으나 깊은 재귀 호출이 필요한 경우가 있다. 이때 재귀 깊이 한도를 더 늘려 설정하기 위해 사용한다.

---

회고

TIL 피드백으로 DP 문제에서 1234567과 같은 숫자를 나누어 나머지를 반환하는 이유에 대해서 알고 넘어갈 수 있었다.

1234567로 나누는 이유

• 결과값이 너무 커지는 것을 방지한다. 결과값이 매우 커지면, 해당 값을 저장하거나 계산하는 데 있어서 오버플로우가 발생할 수 있고 계산 속도가 느려질 수 있는데 이를 방지하기 위함이다.
• 1234567은 비교적 큰 소수이다. 큰 소수로 모듈러 연산을 할 경우 여러 다른 수들이 같은 나머지를 가진느 충돌 가능성을 줄일 수 있다.
• 정수 범위 초과 방지이다. python은 큰 정수를 다룰 수 있지만, 다른 언어나 상황에서는 정수 오버플로우 문제가 발생할 수 있다. 따라서 문제에서 1234567과 같은 특정한 값으로 나누어주면 결과값이 0~123456(특정한 값-1)과 같은 일정한 범위 내에 있도록 보장할 수 있기 때문에 사용한다.

 

CU 모바일 상품권 1만원 GET!!!