HEUNG BLOG

https://www.acmicpc.net/problem/15681 -풀이이 문제는 dp + tree문제이다. 우선 해당 문제의 입력으로는 트리가 주어진다고 써있다. 하지만 트리라는 것은 그래프의 종류 중 하나이다. 그렇기 때문에, 컴퓨터의 입장에서 코드적으로 그래프와 다를게 없어, 우리가 트리의 특징을 이용해서 해당 그래프를 트리처럼 문제를 해결해 나가야 한다. 트리의 특징인 계층적 구조(부모노드-자식노드)를 이용하여 dp를 채워나가면 된다. -코드#include #include #include using namespace std;int n, r, q, dp[100005], visited[100005];vector adj[100005];void dfs(int cur, int parent) { fo..

https://www.acmicpc.net/problem/1094 -풀이해당 문제는 간단한 구현문제이다. 이떄, 2의 배수를 반으로 자르면 오른쪽 쉬프트 연산을 통해 표현할 수 있으므로, 2의 배수를 반으로 자르는 등의 문제가 나올 경우, 비트마스킹을 고려해보는 것도 좋을 것이다. -코드#include using namespace std;int n = 64, x, ret = 1, sum = 64;int main(void) { cin >> x; if (x == 64) { cout > 1); ret += 1; if (sum - n >= x) { sum -= n; ret--; if (sum == x) b..

https://www.acmicpc.net/problem/14890 -풀이이 문제는 100프로 구현문제이다. 특별한 알고리즘이 필요한 문제가 아니니, 해답을 알고자 블로그를 들어왔다면 조금 더 생각해보면 좋을 것 같다.문제는 크게 두가지로 나누어 진다. 오르막 경사로를 놓아야 하는지, 내리막 경사로를 놓아야 하는지를 판단하여 문제를 해결하면 된다.해당 문제를 풀 때, 모든 경우에 대하여 코드를 길게 늘여뜨려 문제를 해결할 수도 있겠지만, 문제를 분석할 때 최대한 간결하게 문제를 쪼갤 수 있도록 노력하는 것이 좋다고 생각한다. -코드#include #include using namespace std;int n, l, a[102][102], b[102][102], ret;void go(int c[102][1..

https://www.acmicpc.net/problem/1074 -풀이이 문제는 분할정복문제이다. 문제 설명에서도 분할정복이라는 워딩이 나오지는 않았지만, 왼쪽위->오른쪽위->왼쪽아래->오른쪽아래로 순서가 고정되어있기 때문에, 이러한 특징을 보고 분할정복문제임을 알면 된다. 단, 고려해야할 점이 한 가지 있다.이 문제를 보고 아무생각 없이 배열을 만들어 하나하나 번호를 매기려고 했다면, 잘못 접근한 것이다. 문제가 너무 쉬워보인다고, 간단하게라도 해당 로직에 대한 시간복잡도에 대해 생각하는 과정을 건너뛰게 된다면, 정답의 정답률은 현저히 떨어질 것이다.문제에서 주어진 최대 범위로 배열을 만들게 되면, 2^15 * 2^15인데, 이를 계산하기 어렵지만 2^10 * 2^10 * 2^10으로 쪼개서 간단하게..

https://www.acmicpc.net/problem/2213 -풀이이 문제는 dp + tree문제이다.우선, 문제에서 루트노드를 따로 설정하지 않았기 때문에, 임의로 하나를 선택해서 문제를 해결하면 된다.현재 노드가 독립집합에 포함되는지, 안되는지를 판단해야 하기때문에 2차원으로 dp배열을 정의해 주었다.dp[cur][0] -> 현재 노드를 독립집합에 포함되지 않을 때, 다음 노드가 포함되는 경우, 그렇지 않을 경우를 모두 고려해야함 dp[cur][1] -> 현재 노드를 독립집합에 포함될 때, 다음 노드는 무조건 독립집합에 포함되지 않는 경우만 고려하면 됨최대 독립집합에 포함되는 노드를 출력하고자 할 때는, dp값이 어떻게 갱신됬는지 역추적하여 문제를 해결하면 된다.이때, 현재 노드가 독립집합에 포..

https://www.acmicpc.net/problem/11723 -풀이이 문제는 비트마스킹를 이용한 구현문제로, 비트마스킹을 연습하고 싶을 때 간단하게 문제를 풀어보면 좋을 것 같다.풀이는 따로 없고 아래 코드를 보고 이해가 안될 경우, 비트마스킹에 대해 더 공부를 해보길 바란다. #include #include #include using namespace std;int n, m, x;string s;int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> m; for (int i = 0; i > s; if (s[0] == 'a' && s[1] == 'd') { cin >> x; n |= (1 > x;..

https://www.acmicpc.net/problem/2629 -풀이이 문제는 n번쨰 추를 가지고 할 수 있는 행동이 총 3가지가 있다. (구슬은 저울의 왼쪽에 놓는다고 가정)1. 추를 오른쪽에 놓는다.2. 추를 놓지 않는다.3. 추를 왼쪽에 놓는다.위와 같은 3가지 상태로 나누어 재귀를 돌려 문제를 해결하면 된다. 다만, 이 문제에서 dp를 사용하는 이유와 1차원이 아닌 왜 2차원 dp를 정의해야 하는지에 대해 더 알아보고자 한다. 첫 번째 의문, dp를 사용해야할까? dp를 사용하는 근본적인 이유는 바로 같은 작업이 반복됨을 막고자 위함이다. 예를 들어, 추 1g, 4g이 있다고 가정하자.첫번째 작업에서 1g의 구슬의 무게 판별 여부를 알고자 할 때, 저울에 1g 추를 올려 판별이 가능할 것이다...