[PGS] 멀리뛰기 최적화, DFS 완전탐색, 동적계획법(DP) #99클럽11일차 #TIL

---

#99클럽 #99일지 #코딩테스트 #개발자스터디 #항해 #TIL #프로그래머스
 

✅ 멀리뛰기 설명

✅ 해결 방법

✅ 발생한 문제와 방안

✅ 최종적인 해결 방법

✅ 최적화 방안

 
 

그래서 오늘의 TIL(Today I Learned) 학습 키워드 
 

✨ DFS

✨ DP 동적계획법

---

 

✅ 멀리뛰기 설명

 

99클럽 미들러 난이도 멀리뛰기로 ✨완전탐색, 전수조사를 DFS로, 동적계획법(DP)로 메모이제이션✨ 하는 방법을 알아보겠습니다.
 
https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 
 

---

✅ 문제설명

 

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항
n은 1 이상, 2000 이하인 정수입니다.

 

 

---

✅ 해결 방법

 

1, 2칸 둘 중의 하나를 고르면서 찾아낼 수 있는 경우의 수를 모두 찾는 문제입니다. 따라서 분기점은 2갈래이면서 DFS를 이용한 완전탐색으로 도착하거나 넘어갔을 때 return을 하면 될 거 같습니다. 여기서 dfs를 할 때, visited를 사용해선 안 됩니다. 특정칸을 여러번 움직여서 도착할 수 있다는게 문제이며, 중복순열로 생각하면 됩니다.

 

def dfs(n, ans, answer):
    if ans == n: return 1
    if ans > n : return 0
    for i in range(1, 3):
        ans += i
        result = dfs(n, ans, answer)
        if result is not None:
            answer += result
        ans -= i
        
def solution(n):
    answer = 0
    ans = 0
    dfs(n, ans, answer)
    return answer

---

✅ 발생한 문제와 방안

 

생각외로 0이 return 되고 있습니다. 경우의 수가 2개밖에 없기 때문에 for문을 사용하지 않는 좀 더 간단한 방법을 찾았습니다. 하노이탑과 비슷한 해결법입니다. 1칸 가거나, 2칸으로 가서 도착하면 return하는 방법이며 이는 depth에 따라서 동일한 시간간격으로 기록되기 때문에 중복될 우려도 없습니다. (1,1,1) (2,1) (1,2) 모두 다른 방법입니다.

 

def dfs(n, ans):
    if ans == n: return 1 #경우의 수를 찾음
    if ans > n : return 0

    return dfs(n, ans + 1) + dfs(n, ans + 2)
        
def solution(n):
    answer = dfs(n, 0)
    return answer

 

 

문제는 재귀적인 호출이 너무 오래 걸린다는 점입니다. 2000이하의 정수일때, 분기점이 2^2000개까지 나뉠 수 있겠네요. 이럴 때 사용할 수 있는 기술은 메모이제이션, 계산한 값을 다시 사용하는 방법입니다. 동적 계획법(Dynamic Programming)를 통해 5까지 계산을 할 때, 1+1+2+1, 1+1+1+1+1 1+1+1+2 반복되는 계산이 있는 것을 확인할 수 있습니다. 숫자 5가 아닌 2000인 경우에는 굉장히 많은 계산을 단축할 수 있습니다.

 

 

def dfs(n, ans, memo):
    if ans == n: return 1 #경우의 수를 찾음
    if ans > n : return 0

    if memo[ans] != -1:
        return memo[ans]
        
    memo[ans] = dfs(n, ans + 1, memo) + dfs(n, ans + 2, memo)
    return memo[ans]
        
def solution(n):
    memo = [-1] * (n + 1)
    answer = dfs(n, 0, memo)
    return answer% 1234567

 

윗 코드에서 런타임에러만 확인하면 될거 같습니다. DP를 사용하므로 dfs코드를 다시 solution으로 옮겨 재귀함수를 없애고 DP만 살리겠습니다.

 

---

✅ 최종적인 해결 방법

def solution(n):
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
    
    return dp[n]

---

✅ 최적화 방안

 

최적화하는 방안으로, 피보나치 수열을 사용하는 방법이 있습니다. 두 변수만 사용하므로 공간복잡도가 O(1)이 됩니다. 

 

def solution(n):
    if n <= 2:
        return n
    
    a,b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, (a+b) % 1234567
    
    return b

 

 

피보나치 수열은 빠르게 증가하므로 %1234567로 나머지를 구해주지 않으면 너무나도 큰 수가 생길 수 있습니다. 피보나치 수열의 특징으로 (a+b)  mod 1234567 이나 ((a mod 1234567) + (b mod 1234567) mod 1234567)의 값이 같기 때문에 수열을 생성하는 과정에서 나머지를 구해도 결과에 영향을 미치지 않습니다. 애초에 빠르게 계산되기 때문에, 공간이나 속도 차이가 크진 않습니다.

 

최적화전 / 최적화 후