Prefix Sum (1) 썸네일형 리스트형 DP: Dynamic Programming 여러 개의 하위 문제를 풀고 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 예 ) 피보나치 -> 백트래킹 하기엔 n이 너무 클 경우 DP 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 찾기 구현은 쉽지만 점화식을 끌어내는 과정이 쉽지 않음 -> 많은 문제 풀이 필요 BOJ 1463. 1로 만들기 (세 방향(연산 종류)으로 전개되는 bfs로도 풀 수 있음) 1.테이블 정의하기 d[i] = i 를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 (최소 횟수를 만들기 위한 규칙 찾기) 3으로 나누기 : d[k] = d[k/3] + 1(3으로 나눈 횟수 추가) 2로 나누기 : d[k] = d[k/2] + 1(2로 나눈 횟수 추가) 1 빼기 : d[k] = d[k-1] +.. 이전 1 다음