# DP
백준 2775번 부녀회장이 될거야
https://www.acmicpc.net/problem/2775수열의 합 공식을 14까지 써야 하나 생각도 했지만결국 아래 층 바로 전호수까지 합은 같은 층 전호수에 저장되어있다는 걸 이용하는 문제였다.약간 dp 가장 기초예제 같은 느낌도..?
[알고리즘] 동적계획법(DP)과 memoization 2
1. 동적계획법 Dynamic Programming, 메모리를 누적하거나 적절히 활용하여, 알고리즘을 수행하는 시간을 최소화할 수 있는 알고리즘 기법이다. 프로그래밍 분야에서 Dynamic은 프로그램이 실행되는 도중을 의미하는데, DP에서의 Dynamic은 프로그래
백준 - 11048번 이동하기
https://www.acmicpc.net/problem/11048기본적인 DP 풀이법핵심은 DP\[nextX]\[nextY] < DP\[x]\[y] + Array\[nextX]\[nextY]를 판단해서 더 큰 경우 DP배열을 갱신해주고출력할 때는 마지막
[BOJ] 7579 앱
BOJ 7579골드 3어플의 수 N 필요한 여유공간 M이 주어지며, 1번째 줄은 각 어플의 메모리 mi, 2번째 줄은 각 어플이 다시 실행될 때의 비용인 ci가 주어진다.5 6030 10 20 35 403 0 3 5 41 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,
[Algorithm] BOJ 17626
BOJ 17626번 Four Squares처음에는 Python으로 dp를 사용하여 풀이하려 하였으나 계속해서 시간초과가 발생했습니다.구글링을 통해 DP를 사용한 Python 풀이를 찾아보았으나 거의 동일한 코드를 돌려도 시간초과가 발생했습니다. (테스트케이스가 최근 추
백준 12865번: 평범한 배낭 - Swift
https://www.acmicpc.net/problem/12865knapsack의 정석과도 같은 문제로, 정형화된 유형입니다.문제는 크게 2차원 dp, 1차원 dp로 풀 수 있고, 1차원 dp가 속도가 훨씬 빠릅니다.여기서는 1차원 dp를 이용해서 문제를 풀
[BOJ] 7579. 앱 - c++
https://www.acmicpc.net/problem/7579C++풀이dpi= 앱 1~i까지만 고려하고 소요 비용이 c일때의 최대 메모리\-knapsack 문제에서 value배열=>memory배열, weight배열=>cost배열\-2차원 dp배열에서 가로축
[Baekjoon] - 1463. 1로 만들기(S3)
📚 출처 - 1463 - 1로 만들기 문제 설명정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해
[BOJ] 12865. 평범한 배낭 - c++
https://www.acmicpc.net/problem/12865dp 풀이dpi=물건 1~i까지만 고려하고 임시 배낭 용량이 w일 때의 최대 가치
[백준/C++] 2193번_이친수
문제는 다음과 같습니다.먼저 구해야하는 문제의 초항(초기 세팅)은 다음과 같습니다.자리수가 하나일 경우는 1만 가능=> 1자리수가 두자리일 경우는 10만 가능=> 1자리수가 세자리일 경우는 100, 101 가능 => 2이렇게 나아갑니다.그리고 저는 바로 점화식의 조건이
[알고리즘] 백준 15988 - 1, 2, 3 더하기 3
분류 : DPhttps://www.acmicpc.net/problem/15988정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n
[백준/C++] 11053번_가장 긴 증가하는 부분 수열
문제는 다음과 같습니다.먼저 전역배열 dn에 n번째 항까지 도달하였을 때의 가장 긴 증가 수열의 항의 수를 담자고 생각했습니다.위의 예시를 그대로 빌려 보면,10 20 10 30 20 50 에서첫번째 경우는 10 -> d1=1 (자기 자신 하나)두번째 경우는 10, 2
[백준/C++] 16194번_카드 구매하기2
문제는 다음과 같습니다.앞에서 보았던 카드 구매하기1번 문제와 모든 원리가 같구요, 앞에서는 최댓값을 구했더라면 이번에는 최솟값을 구하면 됩니다.원리가 같기에, 따로 설명을 덧붙이지는 않겠습니다!max -> min으로만 바꾸면 됩니다.