[Swift/백준] 2167번 동적 프로그래밍(dp)으로 풀이

 

2167번: 2차원 배열의 합

2차원 배열이 주어졌을때 i,j 위치부터 x,y 위치까지의 합을 구하는 문제.

반복문을 이용해서 단순하게 풀수도 있는 쉬운문제이다.

 

 

let n = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [[Int]]()
for _ in 1...n[0] {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

for _ in 1...Int(readLine()!)! {
    let ijxy = readLine()!.split(separator: " ").map{ Int($0)! - 1 }
    let i = ijxy[0]
    let j = ijxy[1]
    let x = ijxy[2]
    let y = ijxy[3]
    var sum = 0
    for i in i...x {
        for j in j...y {
            sum += arr[i][j]
        }
    }
    print(sum)
}

 

 

그러나 다른사람 풀이를 참고하게 되면서 해당 문제를 동적 프로그래밍(dp)으로도 풀이할 수 있다는 사실을 알게되었다.

dp로 풀 경우 반복문보다 실행속도도 훨씬 빨라진다.

 

풀이법을 봐도 해당 알고리즘에 대해서 이해가 잘 가지않아 어떻게 다뤄야 하는지에 대해 다뤄보려고 한다.

 

✔️ 동적 프로그래밍이란?

Dynamic Programming으로, DP라고 많이 부른다.

상향식 접근법으로, 가장 작은 부분의 해답을 구한 후,

이를 저장하여, 저장한 값을 이용해 상위 문제를 풀어가는 방식

 

동적 계획의 핵심은 Memoization(메모이제이션)이라는 기법인데, 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장하여 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 한다는 것이다.

 

대표적 예시로 피보나치의 수열이 있겠다.

 

 

 

 

 

✔️ 1차원 배열의 합

 

array1 [1, 2, 3, 4, 5]

 

해당 1차원 배열이 있을때, index까지 배열의 합을 저장하는 dp는 다음과 같다.

 

dp       [1, 3, 6, 10, 15]

 

0번엔 array1[0…0]까지의 합 1

1번엔 array1[0…1]까지의 합 3

2번엔 array1[0…2]까지의 합 6

.

.

.

이런식으로 1차원 배열에서 dp는 매우 간단하다.

dp를 구하는 점화식은 다음과 같다.

dp[i-1] + array1[i]

 

만약 dp[3]을 구해야 한다면

array1 [1, 2, 3, 4, 5]
dp       [1, 3, 6, 10, 15]

위와 같이 dp[3-1] + array1[3]를 더한 값이 된다.

 

이걸 코드로 정리하여 적는다면 다음과 같다.

let array1 = [1, 2, 3, 4, 5]
var dp = array1
for i in 1..<dp.count {
    dp[i] = dp[i-1] + array1[i]
}

 

 

 

 

 

✔️ x…y 까지 배열의 합

 

만약 배열에서 index 0…1 을 제외하고 index 2…4 까지의 합을 구하고 싶다면

어떻게 할까?

 

dp[4]는 array1[0…4] 까지의 합이다.

여기서 array1[0..1] 까지의 합을 빼주면 된다.

[1 ,2, 3, 4, 5 ] - [1, 2]

 

따라서 점화식은 다음과 같다.

dp[j] - dp[i-1]
15 - 3

 

 

 

 

 

 

✔️ 2차원 배열의 합

 

 

let array2 = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]

 

해당 배열에서 index가 array2[2][3]을 오른쪽 끝점으로 하는 사각형 안에 있는 배열의 합이 dp[2][3]을 구하는 방법이다.

이게 뭔소리인가 싶었는데.. 좀더 이해하기 쉽게 설명하자면 아래와 같다.

 

dp[2][3] =  array[0~2][0~3] 
1 + 2 + 3 + 4 = 10
5 + 6 + 7 + 8 = 26
9 + 10 + 11 + 12 = 42

10 + 26 + 42 = 78  >>> dp[2][3]

 

그럼 도대체 저 노란박스 안에 있는 합을 구하려면 어떻게 해야 할까?

 

 

 

먼저 dp[i][j]를 구하기 위해서는 dp[i][j-1]의 값과 dp[i-1][j]의 갑을 합쳐준다. 

 

dp[i][j-1] = 54
[0, 0, 0]
[0, 0, 0]
[0, 0, 54]

 

dp[i-1][j] = 36
[0, 0, 0, 0],
[0, 0, 0, 36]

 

그런데 둘을 합치면서 dp[i-1][j-1]이 중복으로 더해졌다.

따라서 중복으로 더해진 값을 빼주고 마지막으로 

array2[i][j]를 더해주면 된다.

 

dp[i-1][j-1] = 24
[0, 0, 0]
[0, 0, 24]

 

array2[i][j] = 12
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]

 

54 + 36 - 24 + 12 = 78

 

 

점화식은 다음과 같다.

dp[i][j] = dp[i][j-1] - dp[i-1][j] - dp[i-1][j-1] + array2[i][j]

 

 

2차원 배열에서 dp를 구하는 코드로 작성해보자.

 

2차원 배열의 합에서 dp배열을 초기화 할때 1씩 더 크게 생성해줘야 한다. (Index out of range 방지차원)

let array2 = [[1, 2, 3, 4],
              [5, 6, 7, 8],
              [9, 10, 11, 12],
              [13, 14, 15, 16]]
              
var dp = Array(repeating: [Int](repeating: 0, count: array2[0].count + 1), count: array2.count + 1)

for i in 1...array2.count {
    for j in 1...array2[0].count {
       dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + array2[i-1][j-1]
// dp가 array2보다 size가 1씩 크기때문에 마지막 array2에 접근할때 -1씩 감소해줬다.
   }
}

 

 

 

 

 

 

✔️ (i, j) ~ (x, y) 까지 배열의 합

 

앞서 위 내용을 모두 이해하고 dp테이블을 생성에 성공했다면 dp는 아래와 같다.

 

[[0, 0, 0, 0, 0],

 [0, 1, 3, 6, 10],

 [0, 6, 14, 24, 36],

 [0, 15, 33, 54, 78],

 [0, 28, 60, 96, 136]]

 

[[1, 2, 3, 4],
 [5, 6, 7, 8], 
 [9, 10, 11, 12],
 [13, 14, 15, 16]]

 

만약 해당 부분의 합을 구하고 싶다면 어떻게 할까?

6이 dp[i][j]이고

16이 dp[x][y]라고 가정하자.

 

dp[x][y]는 이미 다음과 같은 사각형이 다 더해진 값이다.

[[0, 0, 0, 0, 0],
 [0, 1, 3, 6, 10], 
 [0, 6, 14, 24, 36],
 [0, 15, 33, 54, 78],
 [0, 28, 60, 96, 136]]        dp[x][y] = 136

 

여기서 필요없는 부분을 빼주는 것이다.

[[0, 0, 0, 0, 0],
 [0, 1, 3, 6, 10],                 dp[i-1][y] =  10
 [0, 6, 14, 24, 36],
 [0, 15, 33, 54, 78],
 [0, 28, 60, 96, 136]]      dp[x][j-1] = 28

 

그리고 중복으로 빠져버린 1을 다시 더해준다.

[[0, 0, 0, 0, 0],
 [0, 1, 3, 6, 10],                 dp[i-1][j-1] = 1
 [0, 6, 14, 24, 36],
 [0, 15, 33, 54, 78],
 [0, 28, 60, 96, 136]]  

 

따라서 점화식은

dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])

 

 

 

let n = readLine()!.split(separator: " ").map{ Int($0)! }
let h = n[0]
let w = n[1]
var arr = [[Int]]()
for _ in 1...h {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
var dp = Array(repeating: [Int](repeating: 0, count: w + 1), count: h + 1)
for i in 1...h {
    for j in 1...w {
        dp[i][j] = arr[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    }
}
for _ in 0..<Int(readLine()!)! {
    let ijxy = readLine()!.split(separator: " ").map{ Int($0)! }
    let i = ijxy[0]
    let j = ijxy[1]
    let x = ijxy[2]
    let y = ijxy[3]
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])
}