정화 코딩

https://www.acmicpc.net/problem/9466 이 문제는 사이클을 판단하는 문제이다. 사이클이 있는지 없는지를 판단하기 위해서 chk 배열과 v 변수를 두었다.v 변수는 현재가 몇번째 연결 그래프인지를 저장하는 변수이고, chk 배열은 해당 노드를 방문 했는지 여부와 몇번째 연결 그래프에서 방문했는지를 저장하는 배열이다. 해당 연결 그래프에서 사이클이 존재하는지를 판단했다면 이제 어느 노드부터 어느 노드까지가 사이클인지 알아야 한다.이를 위해서 지나온 경로를 기록한 후 사이클의 기준점까지 역주척하면서 체크하면 되는데, 두 가지 방법이 있다. 하나는 재귀 함수의 콜 스택을 사용하는 방법이고, 다른 하나는 명시적 스택(stack 자료구조)을 사용하는 방법이다. 1. 재귀 함수 콜 스..

https://www.acmicpc.net/problem/7453 모든 (a, b, c, d) 쌍에 대해서 4중 반복문(시간 복잡도 = O(n^4))을 돌리면 4000^4 = 256,000,000,000,000번의 연산이 필요하고, 1초에 10^8번의 연산이 가능하다고 가정하면 2,560,000초가 걸린다. 즉, 시간 안에 해결 불가능하다. 그런데 모든 (a, b) 쌍에 대한 합을 ab로 구해두고, 모든 (c, d) 쌍에 대한 합을 cd로 구해둔 뒤, ab + cd = 0이 되는 (ab, cd) 순서쌍을 찾으면 2중 반복문으로 문제를 해결할 수 있다. ab 구하기: 시간 복잡도 = O(n^2)cd 구하기: 시간 복잡도 = O(n^2)ab + cd = 0이 되는 (ab, cd) 순서쌍 찾기: 시간 복잡도..

https://www.acmicpc.net/problem/2357 최솟값과 최댓값을 둘 다 구해야 하므로 세그먼트 트리를 구조체로 만들어보았다.세그먼트 트리를 구조체로 선언하면 세그먼트 트리가 여러개 필요한 문제에서 유용하다고 한다.이 문제에서는 MinSegTree와 MaxSegTree를 따로 만들어서 풀어보았다. 또한, init 함수 없이 update 함수만으로 세그먼트 트리를 초기화해줄 수 있다. #include #include using namespace std;int MIN_VAL = 0;int MAX_VAL = 1000000001;int n, m;struct MinSegTree { vector tree; int update(int idx, int l, int r, int target,..

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