:: ADVANCE ::

BAEKJOON ONLINE JUDGE 2228 구간 나누기 https://www.acmicpc.net/problem/2228 DP 구간을 나눌 때 예를 들어 예제를 살펴보면 6개의 원소 중 2개의 구간을 만들어야 한다.이때 위의 조건을 만족하면서 합이 최대가 되는 경우는 { -1, 3, 1, 2, 4, -1 } 인 경우이다. 이 문제를 DP로 풀 때DP[n][m] = n개의 원소들의 집합에서 m개의 구간으로 나누었을 때 합의 최대값 1. i번 째 수를 포함하지 않는 경우 이는 i - 1까지의 원소들의 집합에서 구간 m개를 나눈 합의 최대값과 같다. -> dp[i][m] =dp[i - 1][m] 2. i번 째 수를 포함하는 경우i번 째 수를 포함하는 구간이 m번째 구간이 되어야 하며이전에 m - 1구간을..

BAEKJOON ONLINE JUDGE 1937 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1. Bottom up 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include using namespace std; struct Point { int x, y; int value;}; bool cmp(const Point &first, const Point &second) { return first.value

BAEKJOON ONLINE JUDGE 1520 내리막 길 https://www.acmicpc.net/problem/1520 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include int n, m;int map[510][510];int dp[510][510]; int solve(int y, int x){ int *res = &dp[y][x]; int i; int dy[4] = { -1, 0, 0, 1 }; int dx[4] = { 0, -1, 1, 0 }; int sum = 0; if (*res != -1) return *res; if (map[y][x]

BAEKJOON ONLINE JUDGE 1463 1로 만들기 https://www.acmicpc.net/problem/1463 DP 기본 문제 1234567891011121314151617181920212223242526272829303132333435#include #include #include #define Min(x, y) (x = 0) return dp[n]; if (n

BAEKJOON ONLINE JUDGE 1717 집합의 표현 https://www.acmicpc.net/problem/1717 상호배타적 집합의 예제 문제 (DisJointSet) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include int n, m;int parent[1000001];int rank[1000001]; void init(){ int i; for (i = 0; i rank[v]) parent[v] = u; else if (rank[u] == rank[v]) { parent[v] = u; rank[u]++; } else parent[..

BAEKJOON ONLINE JUDGE 2159 케익 배달 https://www.acmicpc.net/problem/2159 DP 입력 순서대로 좌표와 좌표 인접 지역을 가는 경우의 최소값을 각각 저장해 둔다.dp table [n 번째 입력] [5(0 : 좌표, 1~4 : 좌표 인접지역)] = 거리 최소값 dp[n][i] = min(dp[n - 1][i] + [n - 1][i] 번째에서 [n][i]번째로의 거리) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include int n;int beforex, beforey;l..

BAEKJOON ONLINE JUDGE 1328 고층 빌딩 https://www.acmicpc.net/problem/1328 DP dp[n][l][r] -> n : 건물의 수 l : 왼쪽에서 봤을 때 빌딩의 수 r : 오른쪽에서 봤을 때 빌딩의 수n - 1 건물의 수의 상태에서 건물을 추가하여 경우의 수를 구해나가는 과정이때, 길이 n 번째 건물을 추가하여 경우의 수를 따지기보다 길이 1의 건물을 추가한다고 생각하면 점화식을 구하기 쉽다. 예를 들어, 3개의 건물 2, 3, 4가 존재 할 때 l , r234 3, 1324 2, 1243 2, 2342 2, 2423 1, 2432 1, 3 이 경우에 길이 1인 건물을 추가해 보자1. 맨 앞에 추가하기 -> l + 1이 된다. l , r1 234 4, 11 ..

BAEKJOON ONLINE JUDGE 1916 최소비용 구하기 https://www.acmicpc.net/problem/1916 그래프 최소비용 구하는 문제 1. 다익스트라 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include using namespace std; #define INF 1000000000 int n, m;vector vertex[1001];priority_queue pq;int start, dest; void input(){ int from, to, cost; scanf("%d %d", &..

[STL] vector 생성자vector vvector v(n) : 초기화된 n개의 원소를 가진 vectorvector v(n, x) : x로 초기화된 n개의 원소를 가진 vectorvector v(v2) : v2 복사본. (복사 생성자 호출) vector v(b, e) : 반복자 구간 [b, e)로 초기화된 원소를 가진 vector 멤버 함수v.assign(n, x) : x값으로 n개의 원소를 할당v.assign(b, e) : 반복자 구간 [b, e)로 할당v.clear() : 모든 원소를 제거q = v.erase(p) : p가 가리키는 원소를 제거. q는 다음 원소를 가리킴q = v.insert(p, x) : p가 가리키는 위치에 x값을 삽입한다. vector의 size()는 unsigned int ..

[STL] 어댑터 어댑터는 구성 요소의 인터페이스를 변경한다.일반 컨테이너(반복자나 함수)를 기반으로 특수(특정한 기능을 가진) 컨테이너(반복자나 함수)를 제공하는 느낌? * 컨테이너 어댑터 (container adaptor) : stack, queue, priority_queue* 반복자 어댑터 (iterator adaptor) : reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator* 함수 어댑터 (function adaptor) : 바인더(binder), 부정자(negator), 함수 포인터 어댑터(adaptor for pointers to functions) stack 대표적인 컨테이너 어댑터일반 컨테이너를 L..