# dynamicprogramming
다이나믹 프로그래밍
가장 기본적인 점화식 문제 우리는 zero와 one의 갯수를 구하는 것이기 때문에 주어진 변수로 0일 때와 1일 때를 카운트해서 주면 된다. 여기서 실수할 수도 있는 부분은 else에 관한 부분인데, else에는 아무처리를 안 해도 자동으로 0과 1에 도달하므로
프로그래머스-등굣길(java)
🏫문제 프로그래머스-등굣길 * 다이나믹 프로그래밍이란? * 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 최단경로 문제도 기존 경로 값을 이용하여 쉽게 구할 수 있다.
<Baekjoon> #11659 #11660 구간 합 구하기
#11659 구간 합 구하기4 #11660 구간 합 구하기5 #11659 구간합4 Idea 구간 합 구하기 문제의 핵심은 누적합을 Memoization 기법을 사용하여 해결하는 것이다 N과 M이 최대 100,000이기 때문에 그냥 for문을 돌려서 찾을 경우 최악의
[백준] 1463번: 1로 만들기
점화식을 세워 동적으로 푸는 문제한 숫자가 정해지면 갈 수 있는 갈래는 최대 3갈래계산된 내용은 global하게 선언된 vector에 입력하고, 만약 해당 값이 없는 경우만 Recursive하게 계산https://beginnerdeveloper-lit.tist
프로그래머스 lv2 문자열 압축
문자열 압축첫 lv2의 문제. 풀긴 풀었다만 코드가 아주 지저분 한 것 같다.너무 라이브러리에 의존하는거 아닌가? 라는 생각이 들었다. 다음 문제는 최대한 사용하지 않고 풀어보도록 하자.다른 사람의 풀이를 보면 DP로 풀었고, 라이브러리는 사용하지 않았다. 보고 참고하
DynamicProgramming_2_00_주지수(15724)
네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자
DynamicProgramming_1_23_징검다리 건너기(21317)
심마니 영재는 산삼을 찾아다닌다.산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가
DynamicProgramming_1_22_구간 합 구하기 5(11660)
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.여기서 (2, 2)부터 (3, 4
DynamicProgramming_1_21_동전2(2294)
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.첫째 줄에
DynamicProgramming_1_20_쉬운 계단 수(10844)
45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 1