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

올레 ~ 합격 이번주 일요일부터 시작이당

어이가 없네 ㅋㅋㅋㅋㅋ 물론 공부 안한거에 비해 잘나왔지만 LV.5 최고점이라니... 그리고 오픽보다 성적이 안나왓다니 ㅋㅋㅋㅋㅋ....... 둘다 보기를 잘했다 ...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 인생 실전이군 .....

휴학도 하였고 .. 인턴을 준비하려고 하였으나 대부분의 인턴인 여름방학때 이루어져서 그 전까지 시간이 조금씩 남게 되었다. 그런데 "Be a coding hero"라는 프로그램을 지원마감 하루전에 알게되었다ㅋㅋㅋㅋㅋ 그래서 ... 부랴부랴 자소서를 쓰고 제출을 함. 물론 자소서의 내용도 부실했을 뿐더러 프로그래밍 실력이 뛰어난게 아니라 광탈을 예상했는데 ... 이게 왠걸 오우예!!!! 붙었으 ㅋㅋㅋㅋ그런데 면접이 내일 11시반이네?ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 부랴부랴 작성했던 지원서를 다시 한번 읽어보고 면접을 갔다 . 편한복장이라고 해서 슬랙스+ 니트 조합 면접은 2명의 면접관님들과 5명의 지원자가 30분간 이루어졌다.가장 기본적인 자기소개와 몇가지 질문들이 오고갔는데 나는 아무생각없이 간단한 자기소개정도만 ..

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 라는 입력이..