알고리즘 문제풀이를 위해 다이나믹 프로그래밍을 공부하면서 이해한 내용을 정리한 포스트

동적계획법이란?

나는 대략적으로 파악하고 깊게 공부하며 이해하는 공부법을 좋아하기 때문에, 일단 동적계획법을 설명하는 글들을 찾아보았다.

• 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법
• 특정 범위까지 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 법
• 조금 장난스럽게 말해서 답을 재활용 하는것
• 문제를 여러개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달
• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용

여러곳에서 동적계획법을 쉽게 표현하려고 글을 작성해 주신것들인데,
살펴보니

1. 문제를 잘게 나눔
2. 나온 값으로 다음 문제를 해결하는데 사용

정도로 이해하고 깊게 공부해보면 좋을거 같다.

사용하는 방법

사용하는 방법은 재귀함수로도 할 수 있고, 반복문으로도 처리 할 수 있다.
재귀함수는 결과를 다시 계산 하지 않도록 값을 저장해두고, 똑같은 문제를 만났을때 기존에 저장해둔 값을 사용하는 방식으로 사용하며, 탑다운 방식이라고 한다.
반복문은 아래서 위로 계산하면서 계산한 값을 다음 함수에서 사용하면서 올라간다. 그래서 바텀업 방식이라고 한다.

하지만 일반적으로 동적계획법은 반복문을 이용한 바텀업 방식으로 문제를 해결한다고 함

동적계획법을 사용한 알고리즘 문제 풀이

문제링크

문제를 풀기전에 확인할 것

• 큰문제를 작은문제로 나눌수 있는가?
  다 더해서 제일 큰 숫자를 구한다(큰문제)
  두개중의 큰 숫자를 구하고, 다음 두개중에서 큰 숫자를 구하고 하면서 올라가다보면 제일 큰 숫자를 구할수 있다(작은문제)

• 작은문제를 해결한 결과를 다음 문제에서 사용한다.
  두개중의 큰 숫자를 구했던걸 외부 변수에 저장하고 있다가 다음 줄을 풀때 사용

문제 해결 코드

제 나름의 해석으로 동적 계획법을 사용해서 풀었다고 생각합니다.
더 좋은 코드는 언제나 존재한다고 생각하기 때문에 나중에 더 발전해서 수정 하겠습니다.(댓글로 틀린부분이나 개선할부분 알려주시면 수정하겠습니다!)

function solution(triangle) {
    const _triangle = [...triangle];
    let sumNumArr = [];
    
    for(let i = _triangle.length-2; i >= 0; i--){
        for(let j = 0; j < _triangle[i].length; j++){
            const leftNum = _triangle[i+1][j]
            const rightNum = _triangle[i+1][j+1]
            const targetNum = _triangle[i][j]
            sumNumArr.push(checkBicNum(leftNum, rightNum, targetNum))
        }
        _triangle[i] = [...sumNumArr];
        sumNumArr = []
    }
    
    return _triangle[0][0];
}

function checkBicNum(ln, rn, tn){
    const leftNum = ln + tn;
    const rightNum = rn + tn;
    return leftNum > rightNum ? leftNum : rightNum;
}

checkBicNum: 작은문제 해결 코드
sumNumArr: 이전에 구한 값 재사용

자주 쓰이는곳

• 피보나치 수열 구할 때
• 최단 경로 문제
• 행렬의 제곱 문제

참고자료

나무위키
위키백과
블로그