[Swift] DP(다이나믹 프로그래밍) 2*n 타일링 문제해설

안녕하세용 오랫만의 포스팅이에요.. 요즘 알고리즘 문제도 풀고.. 프로젝트랑 최근에 수술도 해서.. 정신없이 지냈어요..(잘 끝났어요 ^_^) 마무튼간 오늘의 포스팅. 바로

DP(다이나믹 프로그래밍)

의 문제를 여러 문제 풀면서 느낀 꿀팁과 함께 문제풀이를 작성해볼까 합니다.

꿀팁1: 규칙을 찾아라!! 직접 0부터 한 3까지..? 그려봐서 규칙을 찾아 보자(점화식)

그럼 문제 들어갑니다..

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

예) n == 5일 경우

바로 꿀팁을 적용해 보죠.. 우선

1. n == 0일 때: 당연히 0개죠?? -> 0
2. n == 1일 때: 2*1의 틀에서 하나밖에 안들어가죠?? -> 1
3. n == 2일 때: 2*2의 틀에서 총 2가지 경우의 수가 있어요(그림참조). -> 2
4. n == 3일 때: 2*3의 틀에서.... ??? 자세히 보면 n == 2일때 틀 + n == 1일때 틀 이 더해진걸 할 수 있어요!! -> 3

 

이렇게 그려보면서 규칙(점화식)을 찾으면 거의 다 푼거에요...

핵심(점화식): dp[n] == dp[n-1] + dp[n-2]

그럼 이걸가지고 코드를 짜보겠습니다요..

Code

import Foundation

let n: Int = Int(readLine()!)!
// n까지를 볼꺼기 때문에 n+1까지의 크기의 array를 만들어 줄꺼에요.
var dp: [Int] = Array(repeating: 0, count: n+1) 

// dp[2] = dp[1] + dp[0]이 아니기 때문에(예외조건)
// 따로 구분해서 작성해줄게요.
if n < 3 {
    for i in 0 ... n {
        dp[i] = i
    }
    print(dp[n])
} else {
  // 1과 2에 초기값을 세팅해주고
    dp[1] = 1
    dp[2] = 2
  // for문으로 돌려줍니다.
    for i in 3 ... n {
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 10007 // 문제에서 나눠주라네요..
    }
    print(dp.removeLast()) //마지막값이 결과값이죠?? removeLast()를 해서 더 빠르게 마지막값에 접근해줍시다.
}

그래서 DP 풀이방식을 정리해서 말하면...

DP 풀이방식

1. 규칙찾기
2. dp라는 array를 n+1크기로 만들어주기
3. 규칙으로 찾은 점화식을 가지고 for문을 돌려주기
4. 마지막값을 return!

이 될 것 같습니다.

DP라는 유형의 알고리즘 설명이 부족한.. 단순 문제풀이방법을 중점으로 설명한 포스팅이였는데.. 다음에 시간이 되면 DP 알고리즘이 어떻게 해서 저렇게 사용하는건지 알려드리도록 포스팅을 작성해보겠습니다.

아직 코로나가 완전히 끝난게 아니기때문에,, 다들 건강관리 잘 챙기시고.. 마스크는 필수!! 에요..

불편하긴 하지만 마스크는.. 나를 지키기도 하고, 상대방을 지켜주기도 하고, 그렇게 해서 가족을 지키는 하나의 배려라고 생각해요. 다들 힘들지만.. 참고 화이팅 해 봐요! 긍정의힘...

그럼 이만...