[go] go 언어에서의 플래그 값을 활용한 동적 프로그래밍

20 Dec 2023

동적 프로그래밍(Dynamic Programming)은 문제를 하위 문제(subproblem)로 분해하고, 하위 문제의 해결방법을 저장하여 중복 계산을 방지하는 알고리즘 기법입니다. 이때 플래그 값(Flag value)은 이러한 하위 문제를 해결하기 위한 변수로 활용되며, 특정 조건에 따라 상태를 변경하여 해결책에 영향을 미칩니다.

플래그 값 활용 예시

package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func knapsack(weights, values []int, capacity int, n int) int {
	flag := make([][]int, n+1)
	for i := range flag {
		flag[i] = make([]int, capacity+1)
	}

	for i := 0; i <= n; i++ {
		for w := 0; w <= capacity; w++ {
			if i == 0 || w == 0 {
				flag[i][w] = 0
			} else if weights[i-1] <= w {
				flag[i][w] = max(values[i-1]+flag[i-1][w-weights[i-1]], flag[i-1][w])
			} else {
				flag[i][w] = flag[i-1][w]
			}
		}
	}
	return flag[n][capacity]
}

func main() {
	weights := []int{2, 3, 4, 5}
	values := []int{3, 4, 5, 6}
	capacity := 5
	n := len(values)

	fmt.Println("배낭 문제의 최대 가치:", knapsack(weights, values, capacity, n))
}

위의 예시는 0/1 배낭 문제(0/1 Knapsack Problem)를 해결하는 동적 프로그래밍 알고리즘입니다. flag 배열을 활용하여 각 단계의 최대 가치값을 저장하고, 특정 조건에 따라 값을 갱신합니다.

동적 프로그래밍에서 플래그 값을 활용해 문제를 해결함으로써 복잡한 연산을 간소화하고, 효율적으로 해결책을 찾을 수 있습니다.

참고 문헌

Dynamic Programming
Skiena, S. S. (2008). The Algorithm Design Manual. Springer.