Dynamic Programming

한국말로는 동적 프로그램입니다.

그런데 이게 말로만 동적이지 전혀 동적으로 뭘하는게 아니고 처음에 이름을 지은 분이 이게 멋있어서 지었다고 합니다. ㅎㅎ

 

문제의 최적해를 구할 경우에 불필요한 계산을 줄이고 효율적으로 최적해를 찾을수 있고

전체 문제를 작은 문제로 단순화 하고 점화식으로 만들어서 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식입니다.

 

잘 와닿지는 않습니다. 그래서 알고리즘 문제를 하나 풀어볼까 합니다.

 

경로의 최고의 합을 구하는 문제인데요.

문제는 0,0에서 시작해서 마지막까지 이동을 할 수 있는데 이동 조건은 오른쪽으로 가거나 아래로 갈수 있습니다.

let route = [
    [3, 7, 9, 2, 7],
    [9, 8, 3, 5, 5],
    [1, 7, 9, 8, 5],
    [3, 8, 6, 4, 10],
    [6, 3, 9, 7, 8]
]

이걸 잘 보면 first column 은 위쪽에서밖에 오지 못하고 first row는 왼쪽에서밖에 오지 못합니다.

그럼 다음과 같이 값을 채워놓고 시작을 하면 되겠죠.

var sum = Array(repeating: Array(repeating: 0, count: route[0].count), count: route.count)

sum[0][0] = route[0][0]

var colSum = sum[0][0]
var rowSum = sum[0][0]

for index in 1..<route.count {
    colSum += route[index][0]
    sum[index][0] = colSum
}

for index in 1..<route.count {
    rowSum += route[0][index]
    sum[0][index] = rowSum
}

일단 값을 이것들 밖에 안오기 때문에 이렇게만 채우고 점화식을 적용하도록 합니다.

for y in 1..<route.count {
    for x in 1..<route[0].count {
        if sum[y][x - 1] > sum[y - 1][x] {
            sum[y][x] = sum[y][x - 1] + route[y][x]
        } else {
            sum[y][x] = sum[y - 1][x] + route[y][x]
        }
    }
}

if문에서 위쪽의 값과 왼쪽의 값중에서 더 큰 값을 기준으로 sum에 넣어주게 되어있고요.

그렇게 되면 마지막 4,4에서 max 값을 가질수 있게 되는겁니다.

 

전체 코드는 이렇습니다.

let route = [
    [3, 7, 9, 2, 7],
    [9, 8, 3, 5, 5],
    [1, 7, 9, 8, 5],
    [3, 8, 6, 4, 10],
    [6, 3, 9, 7, 8]
]

var sum = Array(repeating: Array(repeating: 0, count: route[0].count), count: route.count)

sum[0][0] = route[0][0]

var colSum = sum[0][0]
var rowSum = sum[0][0]

for index in 1..<route.count {
    colSum += route[index][0]
    sum[index][0] = colSum
}

for index in 1..<route.count {
    rowSum += route[0][index]
    sum[0][index] = rowSum
}

for y in 1..<route.count {
    for x in 1..<route[0].count {
        if sum[y][x - 1] > sum[y - 1][x] {
            sum[y][x] = sum[y][x - 1] + route[y][x]
        } else {
            sum[y][x] = sum[y - 1][x] + route[y][x]
        }
    }
}

print(sum[4][4]) // 67

많은 문제들을 풀어봐야지 응용에 좋을거 같습니다.