정화 코딩

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];..

https://www.acmicpc.net/problem/1214 대충 이런식으로 써가면서 답을 어떤식으로 구해야 할지 생각해봤다. 일단 p d에서 q의 배수(tq)를 뺀 값(dif)을 p로 나누어서 나머지(rem)를 구했다. 이 때 나머지가 음수거나 0이면 p를 더해서 0보다 큰 값으로 바꾸어준다. 이 값이 가장 큰 경우에 지불할 수 있는 금액의 최소가 된다. 그래서 아까 구한 나머지(rem)가 가장 클 때 답을 구하면 되는데, d에서 뺐던 그 q의 배수(tq)에 몫(quo)을 더해주면 된다. 몫(quo)은 아까 나머지에 p를 더하는 과정을 거쳤으면 그냥 몫으로 계산하면 되고, 그렇지 않았다면 몫+1로 계산하면 된다. 아 그리고 아까 구한 나머지(rem)가 0일 때는 거스름돈 없이 딱 맞게 돈을 지..