# dynamicprogramming

76개의 포스트

프로그래머스-등굣길(java)

🏫문제 프로그래머스-등굣길 * 다이나믹 프로그래밍이란? * 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 최단경로 문제도 기존 경로 값을 이용하여 쉽게 구할 수 있다.

2022년 8월 8일
·
0개의 댓글
·
post-thumbnail

<Baekjoon> #11659 #11660 구간 합 구하기

#11659 구간 합 구하기4 #11660 구간 합 구하기5 #11659 구간합4 Idea 구간 합 구하기 문제의 핵심은 누적합을 Memoization 기법을 사용하여 해결하는 것이다 N과 M이 최대 100,000이기 때문에 그냥 for문을 돌려서 찾을 경우 최악의

2022년 8월 3일
·
0개의 댓글
·

[백준] 1463번: 1로 만들기

점화식을 세워 동적으로 푸는 문제한 숫자가 정해지면 갈 수 있는 갈래는 최대 3갈래계산된 내용은 global하게 선언된 vector에 입력하고, 만약 해당 값이 없는 경우만 Recursive하게 계산https&#x3A;//beginnerdeveloper-lit.tist

2022년 8월 1일
·
0개의 댓글
·

프로그래머스 lv2 문자열 압축

문자열 압축첫 lv2의 문제. 풀긴 풀었다만 코드가 아주 지저분 한 것 같다.너무 라이브러리에 의존하는거 아닌가? 라는 생각이 들었다. 다음 문제는 최대한 사용하지 않고 풀어보도록 하자.다른 사람의 풀이를 보면 DP로 풀었고, 라이브러리는 사용하지 않았다. 보고 참고하

2022년 7월 5일
·
0개의 댓글
·
post-thumbnail

DynamicProgramming_2_00_주지수(15724)

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자

2022년 5월 1일
·
0개의 댓글
·

DynamicProgramming_1_23_징검다리 건너기(21317)

심마니 영재는 산삼을 찾아다닌다.산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가

2022년 4월 30일
·
0개의 댓글
·
post-thumbnail

DynamicProgramming_1_22_구간 합 구하기 5(11660)

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.여기서 (2, 2)부터 (3, 4

2022년 4월 29일
·
0개의 댓글
·

DynamicProgramming_1_21_동전2(2294)

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.첫째 줄에

2022년 4월 29일
·
0개의 댓글
·
post-thumbnail

DynamicProgramming_1_20_쉬운 계단 수(10844)

45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 1

2022년 4월 28일
·
0개의 댓글
·
post-thumbnail

DynamicProgramming_1_19_포도주 시식(2156)

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고,

2022년 4월 28일
·
0개의 댓글
·
post-thumbnail

DynamicProgramming_1_18_퇴사2(15486)

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

2022년 4월 28일
·
0개의 댓글
·

DynamicProgramming_1_17_스티커(9465)

DynamicProgramming117_스티커(9465) 문제 > 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질

2022년 4월 28일
·
0개의 댓글
·
post-thumbnail

DynamicProgramming_1_07_1,2,3 더하기(9095)

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작

2022년 4월 9일
·
0개의 댓글
·

DynamicProgramming_1_06_1로 만들기(1463)

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의

2022년 4월 6일
·
0개의 댓글
·

DynamicProgramming_1_05_Four Squares(17626)

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게

2022년 4월 6일
·
0개의 댓글
·

DynamicProgramming_1_04_돌 게임(9655)

돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하

2022년 4월 6일
·
0개의 댓글
·

DynamicProgramming_1_03_다리놓기(1010)

DynamicProgramming103_다리놓기(1010) 문제 > 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고

2022년 4월 5일
·
0개의 댓글
·
post-thumbnail

DynamicProgramming_1_02_피보나치 수2(2748)

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면

2022년 4월 5일
·
0개의 댓글
·

Dynamic Programming_1_01_설탕배달(2839)

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가

2022년 4월 5일
·
0개의 댓글
·

DynamicProgramming_1_00_피보나치 수5(10870)

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면

2022년 4월 5일
·
0개의 댓글
·