뜌릅

오랜만에 백준 문제를 풀어 보았다. meet in the middle이라는 기법을 활용하여 푸는 문제이다. meet in the middle이라는 기법을 처음 접해 보았는데, 부분수열의 합1에서 모든 경우의 수를 구하여 풀었던 것을 같이 활용하여 문제를 풀 수 있었다. #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(int i=0;i> N >> S; vector v(N); rep(i, N)cin >> v[i]; int half = N / 2; vector first(1

위상정렬(Topological sort)의 아주 기초적인 문제입니다. 매우 기초적인 문제로, 메모리와 시간을 크게 신경 쓰지 않고 구현을 해도 되었으므로, 자료구조를 복습하는 차원에서 구현을 하였습니다. #import using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(int i=0;i>n>>m; vector v[1000]; queue q; vector result; rep(i,m){ int x,y,z; cin>>x; if(x == 0)continue; cin>>z; rep(j,x-1){ cin>>y; v[z-1].pb(y-1..

이번에 풀은 문제는 dp와 Sliding Window를 이용하여 풀는 문제였습니다. 문제는 1칸씩 내려가면서, bottom-top 내려오는 방식으로, 위의 dp값을 이용하여 아래의 dp값을 구하는 방식으로 풀었습니다. 메모리제한이 4메가 밖에 안되어, 입력은 반복을 할때마다 받았습니다. #import using namespace std; #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int main() { fast_io; int n; cin>>n; int arr[3]; int dp_max[3]; int dp_min[3]; for(int i =0;i>arr[i]; dp_max[i] = dp_min[i] = arr[i]; } int..

이번 문제는 꽤 머리가 깨졌습니다. 저는 Recursion와 Devide and Conquer(분할 정복기법)을 사용하여 풀었습니다. 제가 풀었던, 이런 류의 문제들중 제일 어려웠던거 같습니다. 문제의 규칙을 찾는게 저는 제일 어려웠습니다. 왼쪽으로 가는 경우와 오른쪽으로 가는 경우의 범위값을 inorder postorder에 대해 각각 나눠서 계산을 하였습니다. inorder의 범위는 postorder에서 구한 root(subroot)로 구해내어, root의 index값을 알아낼 수 있습니다. 저는 이렇게 하여 4가지 경우의 범위를 구해내었습니다. 1.왼쪽 subtree로 가는 경우의 inorder tree의 범위값: (instart, root_idx - 1) 시작지점은 그대로 두고, 끝지점은 root..

이번 문제는 최단거리를 구하는 문제였습니다. 처음에 다익스트라로 풀 수 있는 줄 알고 씨름을 했었는데, 알고 보니 벨만 포드 알고리즘(Bellman-Ford)을 사용하는 것이 더 군요. 이번 문제를 풀면서 최단 거리를 구할 때, 가중치중에 음수인 EDGE가 존재하는 네트워크에서는 다익스트라가 허용이 안된다는 것을 알았습니다. 문제에서는, 다시 되돌아 왔을 때, 0 혹은 음수인 값이 나오는 경우 YES 아닌 경우 NO을 출력하라고 하였습니다. 근데 0 혹은 음수가 나온다는 것은 문제안에 음수 값을 갖는 CYCLE이 존재한다는 것이고, 벤담 포드 알고리즘으로는 CYCLE이 있는 경우는 계산하지 못합니다. 따라서 본래 i을 N-1번 루프 시키는것과 달리, N번 루프를 시켜, 음수 값을 갖는 CYCLE이 있는지..

이번에 푼 문제는 조합 문제입니다. 입력으로 주어진 Combination에 대한 값을 출력하는 것인데, long long으로 설정하고 계산해도 크기를 크게 초과하게 되었습니다. 따라서 저는 string을 이용하여 구현했습니다. 처음에는 string을 이용해서 구해보자니, 곱셈이여서 코드를 도무지 어떻게 짜야하는지 몰랐습니다. 하지만 파스칼의 삼각형을 이용하여, 덧샘을 이용해서(덧셈은 recursive으로 구현합니다.) 조합의 값을 구할 수 있었습니다. #import using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,k; string factorial[1..

이번 문제는 다익스트라 알고리즘을 사용하였습니다. 단 이번에는 기존의 다익스트라 알고리즘을 사용하는 것에서, 알아야할 조건은 다음과 같습니다. 1. 그래프는 양방향 그래프이다. 2. 1에서 n까지 가는데에, v1,v2을 지나쳐야 한다. 3. 단 2번에서 v1 or v2 or n이 연결될 수 없이 고립되어 있다면 -1을 출력해라. 1번의 구현은 매우 쉬우니 넘어가고, 2번과 3번의 경우는 다익스트라 알고리즘을 다음과 같이 나눠서 구현하였습니다. int temp1 = solve(1, x);// 1 to x int temp2 = solve(1, y);// 1 to y int temp3 = solve(x, y);// x to y int temp4 = solve(x, n);// x to n int temp5 = ..

www.acmicpc.net/problem/1238 이번 문제는 다익스트라 알고리즘을 이용하여 풀었습니다. 다익스트라 알고리즘은 우선순위 큐를 이용하여 풀었고, 소가 시작지점에서 도착지점 그리고 도착지점에서 시작지점까지 가는데에 걸리는 시간의 최댓값을 구해야 했기에, 처음 했던 생각은 단순히 모든 각각의 노드에서 출발하는 경우를 구해서 그중 최댓값을 구했었습니다. 하지만, 더 시간을 줄이기 위해, 기존의 일방향 그래프 이외에도 반대방향의 그래프도 만들어내어, x를 기준으로 원래의 가중치 그래프에서의 각각의 노드에 가는데에 걸리는 시간을 구했고, 또 x에서 반대 가중치 그래프에서 각각 노드에게 가는데 걸리는 시간을 구했습니다. 그 두개에서 나온 거리합의 최대값은 답을 의미하기에, 시간을 더 줄일 수 있었습..

오늘은 9465번을 풀어봤습니다. 이전과 동일한 dp문제입니다. 의도치는 않지만, 계속 dp문제만 풀게 되네요. 이번 dp는 (0,0),(0,1),(1,0),(1,1)들을 arr값들로 채우고, top을 (0,n-1),(1,n-1)들로 잡은뒤, 올라가면서, 최댓값을 계속 구하는 방법으로 풀었습니다. 임의의 dp[0][k]에서 최댓값은 두가지로 나뉩니다. 하나는 dp[1][k-1] + arr[0][k]이고, 남은 하나는 dp[1][k-2] + arr[0][i]입니다. 따라서 코드는 아래와 같습니다. int n; vector arr; vector dp; void dfs(){ for(int i =2;i>n; arr = vector(2,vector(n)); dp =vector(2,vector(n)); int a;..

DFS문제 입니다. 처음에는 순서대로 입력받는 줄 알고, 풀었다가 틀린뒤, DFS()을 이용하여 풀었습니다. 입력을 받을 때, 뭐가 부모이고, 자식노드 인지 정해주지 않기 때문에, 입력을 모두 받은 다음에, 1(root node)부터 자식노드 순으로 내려오면서, 부모-자식관계를 연결하고자 했습니다. #import using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(int i=0;in; int x,y; rep(i,n-1){ cin>>x>>y; arr[x].pb(y); arr[y].pb(x); }//양방향으로 연결. Parent(..