개발/알고리즘

퀵정렬(Quick sort)

참고 블로그 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html [알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 퀵 정렬은 분할 정복 알고리즘의 하나로서, 평균적으로 매우 빠른 수행 속도를 가지는 정렬 방법 퀵 정렬 알고리즘 특징 - 합병 정렬(merge sort)과 달리 리스트를 비 균등하게 분할 - 분할 정복 알고리즘 - 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 - 분할 정복 방법은 재귀 함수를 이용하여 구현 퀵정렬 과정 1. 리스트에서 한..

합병 정렬(Merge sort)

머지 소트, 합병 정렬 여러가지 이름으로 존재한다. 이해하면서 분할합병 정렬? 이라고 하는게 옳지 않나 싶다. 제일 먼저 합병 정렬에 큰 도움을 받은 블로그의 링크를 올려 놓는다. 링크 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html [알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 합병 정렬은 '존 폰 노이만' 사람이 제안한 방법 -> 컴퓨터 구조를 배우면 먼저 볼 수 있는 사람. 합병 정렬은 분할 정복 알고리즘의 하나이다. -> 분할 정복 이란 -> 문제를 작은 2개의 문제로 분리하고 각각을 해..

최소 스패닝 트리 (Minimum Spanning Tree, MST)

참고 블로그 : https://www.crocus.co.kr/733 정의 : - 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미 - 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지는 못한다. 최소 스패닝 트리 알고리즘 1. 크루스칼 알고리즘 - 모든 간선에 대해 가장 가중치가 작은 간선부터 연결해주면서 최소 스패닝 트리를 만들어 나가는 알고리즘을 의미 - 크루스칼 알고리즘 자체가 유니온 파인드 자료구조 기반으로 생성된다 --> 유니온 파인드 자료구조를 공부한 경험이 있으나, 위에 참고한 블로그에서는 더 쉽고, 자세히 설명되어있어 다시 게시글을 올릴예정 - 크루스칼 알고리즘의 시간 복잡도 : O(ElogE) 2. 프림 알..

플로이드 와샬(Floyd Warshall) 알고리즘

다익스트라 알고리즘처럼 최단 경로 구하는 알고리즘이다. 차이점은, 모든 정점에서 모든 정점으로의 최단 경로를 구한다는 것. --> 다익스트라 알고리즘은 따로 게시글을 포스트할 예정입니다. 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 점. 그리고 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 기반을 두고 있습니다. 코드를 보면, 초기 경로에 대한 값을 넣어 초기화해줍니다. INF는 무한 값을 대체한 값입니다. 3중 for문으로 구현해, 최단 경로에 대한 비용을 갱신합니다. #include int number = 4; int INF = 10000000; int a[4][4] = { {0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF..

에라토스테네스의 체

에라토스테네스의 체는 대표적인 소수(prime) 판별 알고리즘이다. --> 지금까지 for문 돌려서 약수 있으면 break 하는식으로 했다. --> 더군다나 이 알고리즘은 중학교 수학에서 배울 수 있다고한다.. 먼저 언급했던 for문을 돌려 1과 본인을 제외한 약수가 있다면, break 하는 방법은 시간 복잡도 O(N)을 가지고 있다. 에라토스테네스의 체를 사용하면, O(N^(1/2))의 시간복잡도를 가진다고 한다. 에라토스테네스의 체의 중점은 특정한 숫자의 제곱근까지의 약수의 여부를 검증하는 방식이다. 에라토스테네스의 체를 구현하는 방법은, 1. 이차원 배열을 생성하여 값을 초기화. 2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지움. --> 지운다는 의미는 해당 배열의 값을 0으로 ..

다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘? 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있습니다. 1번. 큰 문제를 작은 문제로 나눌 수 있습니다. 2번. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일합니다. 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다. --> 분할 정복과 애매하게 다른 느낌이다? 이 과정에서 메모이제이션이 사용된다는 점에서 다르다고 합니다. --> 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면 되는 것. 대표적으로 피보나치 수열을 문제로 다이나믹 프로그래밍으로 해결해본다. #include int d[100]; long long dp(int ..

크루스칼 알고리즘 (Kruskal Algorithm)

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 최소 비용 신장 트리 Idea. 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함 유의사항. 사이클이 형성되면 안된다. --> 사이클이 발생하는지의 여부는 Union-Find알고리즘을 사용 순서. 1. 정렬된 순서에 맞게 그래프에 포함시킵니다. 2. 포함시키기 전 사이클 테이블을 확인. 3. 사이클을 형성하는 경우 간선을 포함하지 않습니다. #include #include #include using namespace std; int getParent(int parent[], int x) { if (parent[x] == x) return x; retur..

Union-Find(합집합 찾기)

대표적인 그래프 알고리즘 여러 개의 노드가 존재 시, 두 개의 노드를 선택해서 이 두 노드가 서로 같은 그래프에서 속하는지 판별하는 알고리즘 #include int getParent(int parent[], int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent, parent[x]); } // 두 부모 노드를 합치는 함수 void unionParent(int parent[], int a, int b) { a = getParent(parent, a); b = getParent(parent, b); if (a < b) { parent[b] = a; } else { parent[a] = b; } } int findParent(int..

깊이 우선 탐색(Depth First Search, DFS)

깊이 우선 탐색은 스택이 사용된다. 굳이 스택을 사용하지 않더라도, 구현이 가능하다. 간단한 알고리즘을 사용 1. 스택의 최상단 노드를 확인합니다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺍니다. #include #include using namespace std; int number = 7; int c[7]; vector a[8]; void dfs(int x) { if (c[x]) return; c[x] = true; cout

너비 우선 탐색(Breadth First Search, BFS)

너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 너비 우선 탐색은 '최단 경로'를 찾아준다는 점! 준비물은 큐 #include #include #include using namespace std; int number = 7; int checked[7]; vector a[8]; void bfs(int start) { queue q; q.push(start); checked[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); printf("%d ", x); for (int i = 0; i < a[x].size(); i++) { int y = a[x][i]; if (!checked[y]) { q.push(y); ..