# DP
[백준] 11052번 카드 구매하기 (Python, DP)
<문제 링크>백준 11052번 카드 구매하기1~N까지의 개수만큼 카드가 들어있는 카드팩이 있고, 각 카드팩마다 가격이 정해져 있다. N개의 카드를 얻기 위해 카드팩을 구매하는 여러가지 경우들 중, 가장 비싼 경우의 가격을 구해야 한다. (가격의 최대값)\-> 입력
[BaekJoon] 1520 내리막 길 (Java)
https://www.acmicpc.net/problem/1520지도는 직사각형 모양이며 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능합니다.제일 왼쪽 위 칸이 나타내는
boj - 2579 [java] 계단 오르기
Link : 계단 오르기계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.<그림 1>예를 들어 <
boj - 9095 [java] 1, 2, 3 더하기
Link : 1, 2, 3 더하기정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는
boj - 1463 [java] 1로 만들기
Link : 1로 만들기정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
Dynamic Programming 문제
Discuss 중에 추천 글 -> How to approach most of DP problems.DP문제 풀이의 정석임. 반드시 또 읽기!if a problem is asking for the maximum/minimum/longest/shortest of somet
Leetcode - 1155. Number of Dice Rolls With Target Sum
k개의 면을 가진 주사위 n개가 존재한다. 이 주사위 n개를 던졌을때, 그 합이 target값이 나오는 경우의 수를 구하라. 결과 값은 % 1000000007 으로 모듈러 연산해서 리턴하라(오버플로우 발생예방)각각의 주사위 값은 유니크하다. (1,6) (6,1)은 독립
[C++] Softeer : 징검다리
진짜 오랜만에 푼 DP 문제. 다 까먹었다...하나씩 비교하면서 가장 큰 경우를 찾는다. 전형적인 DP문제인데 엄청 헤맸네...
[백준] 1520 내리막길
📖 문제 https://www.acmicpc.net/problem/1520 💻 내 코드 💡 풀이 모르겠어서 다른 사람들 풀이 참고함 dfs를 돌면서 좌표가 x=n-1, y=m-1일때만 cnt를 더해주는 식을로 먼저 풀었었는데 그렇게 하면 시간초과가 난다 찾아보니깐 끝까지 갈 수 없는 경로도 계속해서 탐색하기 때문이라고 했다 그렇다고 이 탐색을 없애...
14852 - 타일 채우기 3
타일 채우기 3 N-1일 때 N-2일 때 예외 케이스 (남는 크기가 4일 때) ✔️ 점화식dp\[n] = dp\[n-1] x 2 + dp\[n-2] x 3 + (dp\[n-3] x 2 + dp\[n-4] x 2 + ~ + dp\[0] x 2) 💡 참고나동빈 수업
[백준] 14002 가장 긴 증가하는 부분 수열4
📖 문제 https://www.acmicpc.net/problem/14002 💻 내 코드 💡 풀이 먼저 가장 긴 증가하는 부분 수열의 길이를 구한다 현재 수와 그 뒤의 수를 계속해서 비교했을 때 자신보다 큰 수가 뒤에 나오면 1을 더해준다 마지막까지 비교하고 나면 dp배열에서 가장 큰 수가 가장 긴 증가하는 부분 수열의 길이가 된다 dp 배열에서 ...
백준 10844 쉬운 계단 수 (C++)
10844번: 쉬운 계단 수N이 주어졌을 때, N 자릿수에 해당하는 계단수의 갯수를 찾는 문제이다. N=2라고 생각해보자. 첫째 자리가 3일 경우, 둘째 자리에 올 수 있는 수는 2, 4이다. 즉 23, 43이다. N=3이면 둘째 자리는 2,4이고 2일 경우 셋째 자리
[Algorithm] DP 연습하기
SSAFY 알고리즘 수업 오늘의 주제는 dp다.DP는 차근차근 과정을 들으면 알 것 같은데 다시보면 어렵다.아래 두개의 문제는 DP 기본 개념을 연습해볼 수 있는 문제이다.자세한 내용 정리는 다음에..아파트를 각 층별로 파란색 또는 노란색 페인트로 칠하되 다음과 같은
Dynamic Programming 동적 프로그래밍
복잡한 하나의 문제를 작은 여러개의 문제로 나누어 푸는 방법이전의 값을 여러 번 불러와야 하기 때문에 메모이제이션이라는 기법을 주로 사용한다.구한 결과를 메모리에 저장해놓고 그때그때 불러오는 방법주로 배열에 저장DP 문제인지 확인점화식 세우기가장 작은 결과를 메모반복문