전체 글
-
다이나믹 프로그래밍 (Dynamic Programming)Programming/알고리즘 2020. 11. 7. 21:10
다이나믹 프로그래밍이란 '하나의 문제는 한번만 풀게 하는 알고리즘'이다. 즉, 이미 해결한 문제를 중복적으로 수행하는 것을 방지하는 알고리즘이다. 일반적으로 대부분의 분할 정복 기법은 동일한 문제를 다시 풀게 된다는 단점이 있다. (정렬과 같은 경우는 이러한 문제가 일어나지 않는다. 그 예시로 퀵 정렬과 병합 정렬은 매우 빠르게 정렬을 수행할 수 있다.) 분할 정복 기법의 단점이 드러나는 대표적인 예로는 '피보나치 수'가 있다. *피보나치 수열의 점화식 : D[i] = D[i-1] + D[i-2] 만약 15번째 피보나치 수를 구하고자 한다면 14번째 피보나치 수와 13번째 피보나치 수를 더해야 한다. 그럴 경우, 14번째 피보나치 수를 또 구해야 하는데 이 과정에서 이미 구한 13번째 피보나치 수를 구하..
-
이진 트리와 순회 방식Programming/알고리즘 2020. 11. 7. 20:14
이진 트리는 가장 많이 사용되는 비선형 자료구조다. 이진 트리를 사용하는 목적은 데이터의 탐색 속도의 증진을 위해 사용하는 것이다. 트리를 구현할 때는 배열이 아닌 포인터를 사용한다. ▷왜 포인터를 사용할까? ▶힙 정렬을 구현할 때는 완전 이진 트리 형식이기에 배열로 표현할 수 있었으나, 완전 이진 트리가 아닌 이진 트리는 배열로 구현하기 힘들기에 포인터를 사용하여 왼쪽 자식과 오른쪽 자식을 나타낸다! 1. 전위 순회(Preorder traversal) 1) 자기 자신을 처리한다. 2) 왼쪽 자식을 방문한다. 3) 오른쪽 자식을 방문한다. 2. 중위 순회(Inorder traversal) 1) 왼쪽 자식을 방문한다. 2) 자기 자신을 처리한다. 3) 오른쪽 자식을 방문한다. 3. 후위 순회(Postord..
-
크루스칼 알고리즘 (Kruskal)Programming/알고리즘 2020. 11. 7. 18:11
크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결할 때 쓰이는 알고리즘이다.(ex : 도시를 도로로 연결하고자 할 때 가장 적은 비용으로 연결을 위해 사용) ▷노드 : 출발지와 도착지를 나타내는 지점. ▷간선 : 각 노드를 잇는 선으로 간선마다 비용이 있다. 위와 같이 비용 그래프가 이루어져 있다고 해보자. 크루스칼 알고리즘에서는 총 (노드의 갯수 - 1)개의 간선을 비용이 적은 순서대로 뽑는다. 단, 여기서 중요한 점은 사이클을 형성하지 않는 간선만 선택하는 것이다.(여기에서 앞서 배웠던 Union-Find 알고리즘이 사용된다.) #include #include #include using namespace std; int parent[8]; class Edge { public: int node[..
-
Union-FindProgramming/알고리즘 2020. 11. 7. 17:00
Union-Find는 대표적인 그래프 알고리즘이다. 각 노드들이 서로 같은 그래프에 속해있는지 확인하는 알고리즘으로 서로소 집합(Disjoint-set)이라고도 부른다. 위와 같이 노드가 존재한다고 하자. 초기에 각 노드는 본인의 값을 부모로 가진다. 노드 1 2 3 4 5 6 7 8 9 10 부모 1 2 3 4 5 6 7 8 9 10 Union-Find에서는 보통 부모가 작은 것으로 통일 시켜준다. 만약 위와 같이 1번 2번 노드가 연결되고, 5번과 8번 노드가 연결되면 노드 1 2 3 4 5 6 7 8 9 10 부모 1 1 3 4 5 6 7 5 9 10 위와 같이 테이블이 변경된다! #include using namespace std; int parent[11]; // 부모를 찾는 함수 (재귀 사용)..
-
깊이우선탐색 (DFS)Programming/알고리즘 2020. 11. 7. 16:24
스택을 사용할 수 있지만 재귀 또한 스택의 특성을 가지고 있으므로 더 빠른 프로그래밍을 위해 재귀를 사용하였다. 코드는 아래의 그래프를 참고하여 구현하였다. #include #include using namespace std; int n; int flag[8]; vector dfs[8]; void dfs_search(int start) { if (flag[start]) return; flag[start] = true; printf("%d ", start); for (int i = 0; i < dfs[start].size(); i++) { int x = dfs[start][i]; dfs_search(x); } } int main() { dfs[1].push_back(2); dfs[1].push_back(3..
-
너비우선탐색(BFS)Programming/알고리즘 2020. 11. 7. 16:03
너비우선탐색(Breadth first search, BFS)은 탐색을 할때 너비를 우선으로 탐색하는 기법이다. BFS는 '맹목적인 탐색 기법'에 속하며 '최단 경로'를 보장해줍니다. 또한, BFS는 자료구조인 Queue(FIFO)에 기반하여 구현할 수 있습니다. 코드는 아래와 같은 그래프를 기준으로 작성하였다. #include #include #include using namespace std; int n; int flag[8]; vector bfs[8]; queue q; void bfs_search(int start) { q.push(start); flag[start] = true; while (!q.empty()) { int x = q.front(); printf("%d ", x); q.pop(); ..
-
[c++] 백준 10989번 - 수 정렬하기 3Programming/알고리즘 문제 2020. 11. 7. 01:49
# 백준 10989번 URL 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 숫자를 N개 만큼 입력 받는다. (각 숫자는 10000보다 작거나 같은 자연수) 이 문제는 속도가 O(nlog)이 나오는 퀵 정렬, 병합정렬, 힙정렬을 사용하게 되면 메모리 초과가 나오게 된다. 입력값이 10000보다 작다는 조건이 있으므로 여기서는 계수정렬을 사용한다. (계수정렬은 O(n)의 시간복잡도를 가진다) 또한 c++의 입력, 출력 방식인 cout, cin을 사용하게 되면 시간초과가 일어나므로 여기서는 printf()와 scanf()를 사용하였..
-
[c++] 백준 1431번 - 시리얼 번호Programming/알고리즘 문제 2020. 11. 7. 00:59
# 백준 1431번 URL 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 문자열의 수 N을 먼저 입력하고, N만큼 문자열을 입력한다. 1. 길이가 짧은 것 2. 길이가 같다면, 각 자리의 합이 작은것(숫자만 더할 것) 3. 각 자리의 합 또한 같다면 사전 순으로.. 위의 세가지 조건을 만족시켜 c++ STL의 sort를 사용하여 정렬한다. sort의 세번째 인자에는 compare 함수가 들어가며, compare 외에도 각 자리의 숫자의 합을 반환하는 integer_sum이라는 함수를 따로 구현하였다..