Algorithm/dp

백준 2098 외판원순회 c++ // 상태 비트기반 dp, 비트마스킹, 비트 1111 만드는법

https://www.acmicpc.net/problem/2098 1. 외판원순회 특징1. {a,b,c} 집합을 "방문"한 상태에서 d로 가는 최소값과{b,a,c} 집합을 "방문"한 상태에서 d로 가는 최소값은 같다.즉, {a,b,c} 집합안에서 최소값인 경로(a->b->c 등)는 dp를 채우면서 저장된다.2. 2->3->1->2와3->1->2->2 는 같은 경로이다.따라서, 출발점은 아무거나(1번도시) 로 하자. 1.5. 비트 1111 만드는법1 하면된다!10000 -1 == 1111이렇게하면, 모든도시방문한 비트가 만들어진다! 2. 의사코드1. dfs(현재도시, 방문한도시체크용 비트)dfs(0, 1) 로 시작한다. //(0번도시부터 시작, 0번도시 방문표시==1)2. 기저사례 : 모든도시를 방문한경우..

백준 15486 퇴사2 c++ // 탑다운디피, 재귀디피, 맨뒤에서오는 노드그림을 떠올려라!

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)www.acmicpc.net 1. 의사코드1. 완탐기반, 상태를 배열에 저장함2. 상태 : idx==해당날짜3. 아래 그림을 그리고 참고하면서 max 식을 만들어낸다.max { 상담하는경우는 그때 이익을 더함 vs return 받은 이전값을 그대로 씀 }이값을 배열에 저장한다.#include typedef long long ll;using namespace std;//dp[i] : i날짜일때 최대수..

백준 2240 자두나무 c++ // 탑다운디피, 재귀디피 형식, 비트연산자, memset사용법

https://www.acmicpc.net/problem/2240 2240번: 자두나무자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어www.acmicpc.net1. 탑다운디피1. 디피는 기본적으로 "상태"를 "배열"에 저장하고이미 저장된 경로는 더 연산안하고 배열에 저장된 값을 사용하는 것이다.2. 이문제에서 "상태"는 {idx, 위치, 이동제한} 이다. 그 값은 그상태일때, 획득가능한 자두의 최대값이다. 2.비트연산자1. 나무위치가 1,2로 주어졌지만 이를 0, 1로 바꾸면 코드가 매우 간결해지는 장점이 생긴다.2. 장점 : if(0) , if(1)로 바로 활용가능..

백준 1699 제곱수의 합 c++ // dp 2차원 to 1차원, 수학으로 시간복잡도줄이기

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 0. 시행착오 1. dp[104]로 선언해놓고 for(int i=0~104)로 초기화 -> out of bound... 2. 2중for문 100000 * 100000 으로 해놓고 왜안됨? 뻘짓.. 1. 수학으로 시간복잡도줄이기 문제 : i의 범위 100000 * j의 범위 100000 -> 시초 해결 : i의범위는 root n > n; //dp[i][j] :..

백준 11052 카드구매하기 c++ //dp 관찰방법

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1.dp 관찰방법 i행에 주머니(동전)을 한개씩 !추가! 하면서 target(N개 카드) 를 채워나간다. 2.의사코드 1. i행에 1번째 주머니, 2번째 주머니를 추가해나가면서 관찰한다. 2. 관찰결과 위쪽(이번에 추가된 주머니 미사용하는경우) 과 d[j-i] + arr[i]( j-i개 카드를 추가하기 위해 이번에 추가된 주머니 사용하는경우)를 비교해야함을 알아낸다. 3.전체코드 #include usin..

백준 1912 연속합 c++ // dp, 규칙발견, ox를 그때그때 선택해버리기

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1 . ox를 그때그때 선택해버리기 1.완탐 : i번째수를 선택함, 안함으로 2^n 탐색해야함 2. 선택한경우 vs 선택안한경우에서 최적인 경우를 그때그떄 선택한다. 3. 이전값 + 현재값() vs 현재값(나부터 연속합 새로시작) 중에 큰값을 선택하면 된다. 2.전체코드 #include using namespace std; long long d[100004], a[100004],n; //d[i]: i자리까지..

백준 11053 LIS c++ // dp, 규칙발견, 일반화

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 의사코드 1. dp[i]를 정의하고 2. 채워나가면서 규칙(점화식)을 발견하라. 2. 전체코드 #include using namespace std; int n,a[1004],dp[1004]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); c..

백준 1520 내리막길 c++ // top-down dp, dfsDp, 상하좌우탐색 문제점

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. top-down dp 위에서부터구하는 dp를말한다. 재귀로 구현한다. fibo(15)=fibo(14)+fibo(13) ... 2. bottom-up dp 위에서부터구하는 dp를말한다. 반복문으로 구현한다. fibo(3)=fibo(1)+fibo(2) / fibo(4)= ... / fibo(15)= ... 3. 상하좌우탐색 문제점 -> or 아래 or 5시대각선 탐색은 배열을 i,j 한칸씩 탐색하면서..