Hoon222y

예전 면접볼 당시에 이런 질문을 받은적이 있었다. "자료구조와 알고리즘의 차이점이 뭔가요?" 그때 자료구조는 데이터 저장이고 알고리즘은 그 방식이다? 이런식으로 답했던거 같은데 면접관님이 원하는 대답은 아니었다는 식으로 대답을 해주셨던적이 있다. 일년정도 지난 면접이지만 '나중에 알아봐야지.. 나중에 알아봐야지' 이러면서 미루다보니 ... 지금이다 ㅋ.... 참고한 사이트https://kldp.org/node/116364

정렬 알고리즘의 종류에는 여러가지가 있는데 이번 포스팅에서는 각 정렬 알고리즘에 대해 알아보도록 하겠다. [버블정렬 (bubble sort)] - 버블 정렬의 경우 두 인접합 원소를 비교하여 정렬하는 방법이다. 시간복잡도가 O(n^2) 이기 때문에 그냥은 잘 사용하지 않지만 단순구현하지 좋기때문에 사용하기도 한다. 해당 과정처럼 가장 인접한 두 원소들을 비교하고 바로 옆칸으로 이동하여 끝까지 이동하면서 비교를 하게된다. 버블소트의 경우 다른 정렬들과는 다르게 비효율적이라고 했는데 그 이유는 해당과 같다. 간단하게 총정리 느낌으로 본다면 [선택정렬 (selection sort)] - 주어진 원소에서 정렬되어지지 않은 부분의 가장 작은 값을 앞으로 보내는 방식이다. 버블소트와 비슷하게 모든 부분에 대해서 비..

lower_bound 와 upper_bound 모두 정렬되어진 컨테이너에서 원하는 값을 찾는것이다. 즉 먼저 정렬이 되어있다는것이 기본이다. 이 두함수는 비슷한듯 차이가 있는데 1. lower_bound - 반환값이 이터레이터이므로 원하는 index를 반환받기 위해서는 distance(v.begin(), lower_bound())를 통해 인덱스를 반환2. upperr_bound - 반환값이 이터레이터이므로 원하는 index를 반환받기 위해서는 distance(v.begin(), upper_bound())를 통해 인덱스를 반환 이 둘의 차이점은 바로 둘다 binary search를 통해서 값을 찾아주기는 하지만lower_bound는 value를 포함한 이상인 값을 , upper_bound는 value를 포..

이번 시간에는 최단거리 알고리즘인 다익스트라(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

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

이번 시간에는 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을 해주는 과정이다. 또한 최장 증가 수열에 포함되는 수들을 확인하기 위해서는 해당 그림처럼 각각의 개수를 저..

위상정렬 (Topological sort) 이란 어떠한 일을 하는 순서를 결정해주는 정렬이라고 할 수 있다. 간단하게 생각해보면 일의 우선순위를 결정하는 것이다.코드로 살펴보도록 하자 1234567891011121314151617181920212223242526272829for(int i=0;i

int find(int val, int node, int x, int y){ if (x == y) return x; if (seg[node * 2] >= val) return find(val, node * 2, x, (x + y) / 2); else return find(val - seg[node * 2], node * 2 + 1, (x + y) / 2 + 1, y); } 이런식으로도 구현을 하더라 ... 개쩐당 ... 은 합을 구하는 문제인데 https://www.acmicpc.net/problem/1321 #include #include #include #include #include #include #include #include #include #include #include #include #d..

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include using namespace std;void init(vector &tree, vector &a, int node, int start, int end) { if (start == end) { tree[node] = a[start]; } else { init(tree, a, node*2, start, (start+end)/2); init(tree, a, node*2+1, (start+end)/2+1, end); ..