Hoon222y

이번 시간에는 최단거리 알고리즘인 다익스트라(Dijkstra)에 대해 알아보자. 다익스트라 알고리즘의 경우에는 크게 3개의 과정으로 나뉘게 된다. 1) 체크되어 있지 않은 정점 중에서 dist의 값이 가장 작은 정점x를 선택한다.2) x를 체크한다.3) x와 연결된 모든 정점을 검사하며 간선을 (x,y,z)라고 했을 때 dist[y]>dist[x]+z 이면 갱신한다. 그런데 보통 1번과정에서 가장 dist값이 작은 경우를 찾는 과정을 효율적으로 구현하기 위해 priority_queue를 사용한다.- priority_queue 자체가 max heap이기 때문에 -1을 곱해서 음수로 체크를 한다. 123456789101112131415161718192021222324for(int i=1;i

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

MST 는 Minimum Spanning tree 인데 용어를 간략히 정리하자면 스패닝 트리 : 그래프에서 일부 간선을 선택해 만든 트리최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리 (트리의 정의 : 정점이 N개라면 간선은 N-1개인 경우 ) MST를 구현하는 방법에는 크게 3가지로 나누어 볼 수 있는데1) 프림 (Prim) - 정점을 중심으로 2) 크루스칼 (Kruskal) - 간선을 중심으로 3) 솔린 알고리즘 (sollin's algorithm)으로 나누어 볼 수 있다. 근데 보통은 같은 시작 복잡도를 가지고 있으므로 간단한 크루스칼을 많이 사용하는것 같다. 해당 포스팅에서는 크루스칼까지만 언급을 하도록 하겠다. 먼저 프림(Prim algorithm)의 경우1. 그래..

간간히 문제를 풀다보면 주어진 수열을 전부 검색해봐야 하는 경우가 있다. 혹은 그 다음의 배열을 구해야 하는 경우가 있는게 STL에 있는 next_permutation, 혹은 prev_permutation을 통하여 쉽게 구할수 있다. https://www.acmicpc.net/problem/10972 문제 혹은 https://www.acmicpc.net/problem/10973 해당문제가 가장 간단한 예가 될 것이다. 1234567891011121314151617181920212223#include #include #include #include using namespace std; int n;vector v;int main(){ scanf("%d" , &n); v.resize(n); for(int i=..

이번 시간에는 Set 과 MultiSet 에 대해 알아보도록 하겠다. Set과 Multiset을 사용하는 가장 큰 이유는 Binary Tree로 구현되어 있기 때문에, Search를 O(logN)에 할 수 있다는 이유로 사용을 하게 된다.하지만 차이점은 Set은 중복을 허용하지 않고 , Multiset은 중복을 허용하기 때문에 중복시 MultiSet 을 통해 구현해야 한다. 12345678910111213141516171819202122232425262728293031#include #include #include using namespace std; set s;int main(){ s.insert(10); s.insert(20); s.insert(5); s.insert(7); auto it = s.be..

LIS(Longest Increasing Subsequence) 알고리즘이란 번역하자면 최장 증가 수열이다.예를들어 1,4,6,2,3,4,9,8 이런 수열이 있다고 하면 이 수열의 LIS는 1,2,3,4,8이 될 것이다. 이러한 LIS알고리즘을 구현하는 방법은 크게 2가지가 있는데 1) O(N^2)의 방법2) O(N*logN)의 방법 으로 나누어 볼 수 있다. 먼저 O(N^2)의 방법이다. 가장 간단하고 직관적으로 알 수 있는 방법으로 자기 자신을 기준으로 자신 앞에 있는 모든 수를 다 확인해보는 방법이다. 주어진 수열에서 개수를 x는 1~x-1까지의 모든 수열중 자신보다 작은 개수의 최대값 +1을 해주는 과정이다. 또한 최장 증가 수열에 포함되는 수들을 확인하기 위해서는 해당 그림처럼 각각의 개수를 저..

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) 를 해..