Hoon222y

https://www.acmicpc.net/problem/1613 일의 우선순위를 물어보는 역사시간 문제이다 ㅋㅋ 처음 문제를 보고 접근방법으로 위상정렬로 하려고 했는데 .... 이게 왠건 플로이드 워셜이네 ....(어떤부분을 보고 플로이드 워셜로 접근하는 사람들이 있는지 궁금하긴 하다) 일단 플로이드로 구현하게 된다면 각각의 가중치를 두고 플로이드를 돌린 후 일정 조건에 따라 다르게 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #define INF 1000000000using namespace std; int n,m,arr[411][411],t;int a,b;..

https://www.acmicpc.net/problem/1201 N,M,K가 주어졌을때 1~N까지의 수중에서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 구하는 문제이다. 먼저 적어도 M개는 증가수열이 될것이고 , K는 감소수열이 될것이며 , 최대 겹칠수 있는 경우의 수는 1가지 경우이므로 N>=M+K-1의 전제조건을 만족 해야한다.이후에 접근 방법을 생각한다면1) 1~N까지의 숫자를 오름차순으로 정렬 후 해당 배열을 M개의 그룹으로 나눈다.2) 이 때, 각 그룹에 들어있는 수의 개수는 K보다 작거나 같아야 하며 , 주어진 조건을 만족시키기 위해서 한 그룹은 K개의 수를 가지고 있어야 한다. 3) 그 후 각 그룹을 뒤집어 주면 된다. 예를들어 5 3 2 라는 입력이..

https://www.acmicpc.net/problem/2293https://www.acmicpc.net/problem/2294 각각 동전 1, 동전 2 의 문제이다. n종류의 동전을 이용하여 m이라는 값을 만드는 문제였다. 처음에 접근했을때는 dp는 dp인데 2차원으로 dp[i][j] 를 i번째 숫자까지 이용해서 j를 만드는 방법으로 접근을 했는데 하다가 계속 삽질을 한.... 간단하게 접근해보면 1차원 dp로도 문제를 해결할 수 있다. 이렇게 기록하는 이유는 이러한 문제를 1차원으로도 2차원 dp느낌을 낼 수 있어서이다. 동전 1의 경우 점화식을 dp[j]를 j값을 만드는데 가능한 경우의 수 로 두고 식을 세우면 dp[j] +=dp[j-arr[i]] ( arr[i] = i번째 숫자 ) 라고 할 수 ..

https://www.acmicpc.net/problem/1509 입력되어진 문자열을 팰린드롬들로 분할하였을 때 그 분할개수의 최소값을 출력하는 문제이다. 최소값을 구하는 문제라고 적혀있는 것처럼 DP로 접근을 해보자. dp 배열의 개념을 먼저 잡고 가자면 dp[i] 는 문자열 i번째 문자까지 갔을 떄 필요한 최소한의 팰린드롬 개수이다. 따라서 점화식을 새운다면 dp[i] = min(dp[j-1])+1 ( 여기서 i와 j는 팰린드롬 일 경우 )이 될 것이다. 따라서 먼저 i와 j가 팰린드롬인지를 판별하는 함수를 먼저 만들고 점화식대로 문제를 해결해나가면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445..

https://www.acmicpc.net/problem/11729우리가 평소에 알고 있던 하노이 탑을 이동시키며 그 경로를 출력하는 문제이다. 처음 문제를 보았을때는 시뮬레이션 해보며 특정순서에는 특정 규칙에 따라 이동을 한다고 생각하였는데 .... 뭔가 삽질을 하는것 같았다. 해당문제는 분할정복, 즉 dnc로 접근을 해볼 수 있다. 해당 하노이의 탑에서 1번에서 3번으로 옮기려면 어떤 과정을 거쳐야 할까? n개의 탑을 옮기기 위해서는 먼저 1번부터 n-1번까지 2번으로 옮기고, n번째 탑을 3번으로 옮기고, 1부터 n-1개의 탑을 3번으로 옮기면 된다. 정리를 하자면 solve(n,x,y) 는 solve(n-1,x,6-x-y) 후 n번째 판을 3번으로 옮기고, solve(n-1,6-x-y,y) 를 해..

https://www.acmicpc.net/problem/10816해당 문제는 주어진 N개(1

이 문제를 풀기전에 이분그래프가 무엇인지 먼저 설명을 하도록 하겠다.이분 그래프란 위 그림처럼 A,B처럼 반반으로 나눌수 있는 그래프를 말한다. 즉, 모든 간선의 끝이 한쪽은 A 한쪽은 B에 속하는 그래프를 말한다.이분 그래프를 단순히 구현하는 문제가 바로 https://www.acmicpc.net/problem/1707 이다.해당 문제의 경우 bfs혹은 dfs를 통하여 방문하는 지점의 점수를 각각 1,2로 다르게 준 후 마지막에 비교를 하면 된다. 그리하여 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #incl..

https://www.acmicpc.net/problem/2156일렬로 있는 포도주를 일정 규칙에 따라서 마실 때 최대로 마실 수 있는 양을 구하는 DP문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include using namespace std;int n;int dp[3][22222];int arr[22222];int main(){ memset(dp,0,sizeof(dp)); memset(arr,0,sizeof(arr)); scanf("%d" , &n); for(int i=1;i

문제를 간단하게 정리하자면 친구관계로 묶여 있는 그래프가 있는데 그 그래프에서 모든쌍의 최단거리를 구하는 문제이다그래프끼리의 간선의 가중치는 같다고 본다. 가중치가 다르다면 다익스트라 방식으로 접근해야 할 것이다.플로이드 머셜에 대한 내용은 다음시간에 정리하는것으로 보고 이번시간에는 이 문제를 접근하는 방식에 대해서 먼저 생각해보도록 하자 그래프 내에서 각 간선들의 가중치는 같고 그 그래프 내에서의 모든쌍의 최단경로를 구하는 문제의 경우에는 플로이드 머셜 알고리즘을 사용하는데 알고리즘의 중요부분은 다음과 같다. for(int k=1;k

문제가 길어서 .... 문제를 짧게 설명하자면 책의 번호가 저렇게 정렬되어 있는데 순서대로 정렬을 할 때 최소의 노동력으로 정렬할 때 그때의 최소 노동력을 구하는 것이다.이번 문제의 경우도 해매고, 해매고 ... 이 문제는 LIS알고리즘을 활용 한 것 이라는데 Longest increasing Subsequence 알고리즘으로 이 문제의 포인트는 최소한의 노동력 = 전체값 - 그대로 두는 노동력의 최대값이라고 볼 수 있다는 것이다.대략의 과정을 설명 하자면 앞에서 부터 시작을 한다. 813.8을 마지막으로 하는 정렬된 수열은 당연히 하나이므로 절약할 수 있는 노동력은 6이다.그 다음 812의 경우에는 812보다 작은 수가 없으므로 6 혹은 자기 자신의 노동력 20 중 그대로 두는 노동력이 큰 20이 저장..