Programming
-
에라토스테네스의 체Programming/알고리즘 2020. 11. 15. 13:01
에라토스테네스의 체는 대표적인 소수(Prime Number) 판별 알고리즘이다. 에라토스테네스의 체 알고리즘은 한 두개의 소수를 판별하는 경우가 아닌 대량의 소수를 한꺼번에 판별할 때 사용한다. 에라토스테네스의 체는 우선 예를 들어 1부터 100까지의 수에서 소수를 판별한다고 하면 크기가 101인 int형 배열을 선언한다. 그리고 초기에 각 인덱스는 인덱스의 값으로 초기화를 시켜준다. 그 후 반복문을 통해 2의 배수, 3의 배수 ,4의 배수, ... 에 해당하는 인덱스의 값을 0으로 바꿔주는데 시간 복잡도를 줄이기 위해 이미 0인 부분은 continue를 사용하여 스킵되도록 한다. #include using namespace std; int number = 100; int a[101]; void isPr..
-
[c++] 백준 2133번 - 타일 채우기Programming/알고리즘 문제 2020. 11. 15. 10:50
#백준 2133번 URL 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 이번에는 3*N 크기의 벽을 2*1, 1*2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 마찬가지로 다이나믹 프로그래밍을 이용하여 문제를 해결해보자. n=1일 경우, 타일을 채울 수 있는 경우의 수가 0이다. 즉, d[1] = 0. n=2일 경우, 아래와 같이 3가지의 방법이 있다. 즉, d[2] = 3이다. n=3일 경우는 3*1의 타일이 세개가 연달아 나타나는 모양이므로 d[3]=0이다. n=4일 경우는 n=2일 경우에 3*2 타일을 배치하는 경우이므로 d[4] = 3*d[2]의 경우의 수가 있다고 할 수 있다. 또한, n=6일 경우 d..
-
[c++] 백준 11726번 - 2*n 타일링Programming/알고리즘 문제 2020. 11. 7. 21:56
# 백준 11726번 URL 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 다이나믹 프로그래밍 문제의 기본이라고 할 수 있는 '타일링' 문제이다. 기본적으로 다이나믹 프로그래밍에서는 규칙성을 찾아서 점화식을 찾는게 관건이라고 할 수 있다. 먼저, 수많은 타일이 이미 쌓여있고 1만큼 추가한다고 가정해보자! 위와 같은 경우, 이미 이전에 d(n-1)가짓 수로 타일을 배치한 상태에서 1가지의 방법으로 밖에 타일을 놓지 못한다. 두번째로, 2만큼 타일을 추가한다고 생각해보자. 이렇게 타일을 쌓는 방식은 앞서 고려했던 경우와 같으므로 고려..
-
다이나믹 프로그래밍 (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..