뜌릅

이번에 풀은 문제는 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(..

LCS문제 입니다. 저는 처음 봤는데, 구글링을 해본 결과, 유명한 문제 유형이더군요. 이 문제도 전에 풀었던 Knapsack문제와 매우 유사하게 풀었습니다. 역시 dp를 사용했습니다. Dp문제는 너무 어려운 것 같습니다. 보고나면, 쉬운데 발상 자체는 떠올리기가 힘듭니다. 이 문제를 풀기위해서는 한글자씩 비교하면서, 맞으면 갯수+1를 해야 합니다. 하지만, 단순히 모든걸 비교하면, 시간초과가 발생합니다. 결국에는 어떤 방식으로 비교하는 문제가 되는 겁니다. 이 문제는 BFS같은 느낌으로 풀었습니다. 둘이 비교해서 같으면 +1, 다르면 첫번째 문자열만 다음 문자로 넘긴것과 두번째 문자열만 다음 문자로 넘겼을 경우를 비교하여, 둘중 최댓값을 출력하는 겁니다. #import using namespace st..

이 문제는 knapsack유형의 문제라고 한다. 나는 이 문제를 처음 봤지만, 풀는데에 구글링을 해서 솔루션을 보았기에, 앞으로 dp유형과 knapsack유형이 익숙해질때까지 많이 풀고자 한다. 어느 dp문제가 그렇듯이, 점화식을 작성해야 한다. 처음 이 문제를 접했을 때, 기준점을 잡기가 어려웠다. 하지만, 구글링을 하게 된 결과, 기준은 내가 정하게 되는거란 것을 알게 되었다. 나는 기준을 입력순대로 정하였다. 이 기준대로, 물건의 종류를 처음에는1개에서 2개, ....... n개까지 1개씩 증가시키면서 그때마다의 최댓값을 얻어냈다. 1개일 때의 최댓값을 구하는건 쉽다. 무게보다 낮을경우 0, 높을 경우 해당 물건의 무게값. k개일 때의 최댓값은 k-1개일 때의 최댓값에서 k번째 물건을 추가시킨 경우..