정화 코딩

https://www.acmicpc.net/problem/6549 히스토그램에서 가장 넓이가 큰 직사각형은 다음의 셋 중 하나이다. 1. 최솟값을 포함하면서 전체 구간의 직사각형 2. 최솟값 기준 왼쪽 구간에서의 가장 큰 직사각형 3. 최솟값 기준 오른쪽 구간에서의 가장 큰 직사각형 왜냐하면 최대 직사각형은 최댓값을 포함할 수도 있고 포함하지 않을 수도 있다. 만약 최솟값을 포함한다면 구간을 최대로 잡아도 좌우로는 잘리지 않기 때문에, 양쪽 끝까지 구간을 잡는 것이 최대이다. 만약 최솟값을 포함하지 않는다면 해당 최솟값을 기준으로 구간이 이미 잘렸다고 생각하면 된다. 그렇기 때문에 그 값 기준 왼쪽에서의 최대와 오른쪽에서의 최대를 구한다. 따라서 세그먼트 트리로 저장해야 하는 정보는 구간 별 최소값을의..

https://www.acmicpc.net/problem/2042세그먼트 트리란?세그먼트 트리는 구간에 대한 정보를 트리 구조로 저장하여, 구간의 갱신과 조회를 효율적으로 처리할 수 있도록 설계된 자료구조이다.세그먼트 트리의 원리1번 노드는 1~8 구간의 정보를 담고 있고2번 노드는 1~4 구간의 정보를, 3번 노드는 5~8 구간의 정보를 담고 있고...이런 구조로 되어 있다. 3~7 구간의 정보를 알고 싶다고 생각해보자. 우선 루트 노드에서 시작해서 쭉 내려간다. - 내 구간이 목표 구간에 완벽히 포함되지 않으면 절반으로 쪼개서 자식 노드로 전달한다.- 만약 완벽히 포함된다면 내가 가지고 있는 정보를 그대로 위로 다시 올리면 되고, 만약 전혀 겹치지 않는다면 항등원을 반환한다. 세그먼트 트리 구현아래 ..

https://www.acmicpc.net/problem/7579 0-1 냅색 문제이다. 기본적인 0-1 냅색에 대한 내용은 이 글의 평범한 배낭 문제 부분에 잘 정리되어 있다. 기본적인 0-1 냅색에서의 dp 배열은 다음과 같다.dp[i][j] : 가방의 무게가 i이고, j번째 물건까지 살펴봤을 때, 가방에 담을 수 있는 최대 가치 그래서 다시 이 문제로 돌아오면... 이 문제는 크게 두 가지 방법으로 해결할 수 있다.1. 2차원 dp 배열로 해결하기dp[i][j] : i만큼의 비용으로 j번째 앱까지 확인했을 때, 얻을 수 있는 최대 메모리#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.t..

https://www.acmicpc.net/problem/1562 10844번 쉬운 계단 수 문제의 어려운 버전인가 보다. 그 문제에 대한 풀이는 이 글에 있다. 쉬운 계단 수와의 다른 점은 0부터 9까지의 수가 모두 등장해야 한다는 것이다. 그러면 어떤 어떤 수를 사용했는지 비트마스킹으로 표시해주면 되겠네! dp[i][j][k]: 길이가 i이면서 j로 끝나는데, 현재까지 사용한 수가 k 상태인 계단 수의 개수(0을 사용했으면 2^0으로, 1을 사용했으면 2^1으로... 표현하고 그걸 모두 합한 값을 k로 사용한다. 즉 k는 0 이상 1023 이하의 값이다.)0으로 끝나는 수 → dp[i][0][k | 2^0] += dp[i - 1][1][k]9로 끝나는 수 → dp[i][j] = dp[i][9][k |..

https://www.acmicpc.net/problem/10844 dp[i][j] : 길이가 i이면서 j로 끝나는 계단 수의 개수0으로 끝나는 수 → dp[i][0] = dp[i - 1][1]9로 끝나는 수 → dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]나머지로 끝나는 수 → dp[i][0] = dp[i - 1][1] #include #include using namespace std;int mod = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector> dp(n + 1, vector(10, 0)); ..

https://www.acmicpc.net/problem/17070 그냥 bfs 해주되, 파이프가 놓여 있는 방향까지 큐에 넣도록 했다. 그래서 현 상태를 기준으로 어떻게 움직일 수 있는지를 체크해서 (n, n)에 도달하면 한번 카운트 해주는 식으로 구혔했다.어차피 움직이는 방향이 무조건 오른쪽 또는 아래이기 때문에 시간 안에 해결 가능하다고 생각했는데, 제출해보니 좀 간당간당하고 dp로 풀어야 했던 문제인 듯하다. #include #include #include using namespace std;// 파이프가 놓여 있는 방향 {가로, 세로, 대각선}int px[] = {0, -1, -1};int py[] = {-1, 0, -1};vector>> d = { {{0, 1, 0}, {1, 1, 2}..

https://www.acmicpc.net/problem/30788 각도가 d인 축을 기준으로 대칭이동 시켰을 때 그림이 얼마나 회전하는지를 계산하기 위한 뻘짓...그래서 식은 nxt = (2 * d - cur) % 360 이다.(cur: 대칭이동 전의 그림의 각도, nxt: 대칭이동 후의 그림의 각도, d: 대칭이동 축의 각도) 이건 식 정리 과정...그래서 정리하면 다음과 같다. 우선 그림이 원래 상태로 돌아오려면 대칭이동은 짝수번 시켜야 한다.축이 홀수개이면 무조건 불가능하므로 생각해주지 않아도 된다. k번의 대칭이동 후의 그림의 각도는 2 * d(k) - 2 * d(k-1) + ... + 2 * d(2) - 2 * d(1) 가 된다. (k는 짝수)즉, 짝수 내에서와 홀수 내에서의 축의 배치 ..

https://www.acmicpc.net/problem/14938 우선 모든 노드와 노드 사이의 최단 경로를 구해 놓는다.그 후 각 지역에 떨어졌다고 가정했을 때, 얻을 수 있는 아이템의 수를 구해서 최댓값을 찾는다. 모든 노드 간의 최단 경로가 필요하기 때문에 플로이드-워셜을 사용하였다. #include #include using namespace std;int MAX_SIZE = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, r; cin >> n >> m >> r; vector item(n + 1); for (int i = 1; i > item[i];..