Explain.문제보기ApproachMerge sort, Heap sort를 활용하여 수를 정렬.본문에서는 Heap sort(MAX Heap)을 구현하여 Heap sort를 구현하였다.Code #include #include void swap(int arr[], int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } void heapfiy(int arr[], int n, int i) { int root = i; int left = i * 2 + 1; int right = i * 2 + 2; if (left < n && arr[root] < arr[left]) { root = left; } if (right < n && arr[root] ..
Explain문제보기본 풀이에서는 위 문제에서 결과로 요청한 최소 검은 방의 수 뿐만 아니라 해당결과의 경로까지 출력한다.Approachdijkstra algorithm을 활용하여 풀이하였으며shorter path를 구하기위한 자료구조로써 priority queue를 구현.자세한 내용은 추후 정리.Code #include #include #include typedef struct { int x; int y; int px; int py; int value; } heapNode; typedef struct { heapNode* heap; int size; } PQ; void insert(heapNode aNode, heapNode* heap, int size) { int idx; heapNode tmp; i..
ApproachN Queen Problem 문제를 가장 기본적인 Deterministic Algorithm(Backtraking) 을 이용하여 풀어본 코드. 자세한 내용은 추후 정리. Code #include #include #define TRUE 1 #define FALSE 0 int promising(int); void queens(int); void print(); int* col; int N; FILE *output; int main(void) { FILE *file; char file_name[255]; int i; printf("input file name?"); scanf("%s", &file_name); file = fopen(file_name, "r"); output = fopen("ou..
Explain.문제보기 Approach\( N = 3*2^k (k
Explaindynamic programming 기법 중 하나이며 주어진 연속되는 행렬의 곱셈에서 최적의 방법을 찾아내는것이 목표이다.\(q*p,p*r\) 크기의 행렬의 곱셈 연산의 횟수는 \( q*p*r \) 인점을 기억해야 한다.기본적으로 행렬의 곱은 associativity하므로 연속되는 행렬의 곱 ABCD 에 대해\(((AB)C)D = ((A(BC))D) = (AB)(CD) = A((BC)D)\)가 성립한다. 이때 각각의 연산마다의 곱셈 연산의 횟수는 다르므로 이중에서 최소 연산 횟수를 가지는 방법을 찾아야 한다. 예를 들어 \(A = 10*30, B = 30 * 5, C = 5 * 60 \) 의 크기를 가지는 행렬의 곱셈을 진행 할때$$(AB)C = (10*30*5) + (10*5*60) = 1..
ExplainFloyd-Warshall algorithm 또는 Floyd's algorithm 이라고 불리우며 negative cycles을 가지지 않은 weighted graph에서 임의의 두 vertex 사이의 최단 거리를 구하는 알고리즘이며 \(\Theta(n^3) \) 의 시간복잡도를 나타내며 optimal algorithm의 한 종류이다.Notation\(N :\) vertex 의 개수\(W :\) 인접 vertex 간의 weight \( |N^2| \) 이며 인접하지 않은 vertex 간의 거리는 \(\infty\)\( D_{(k)}[i,j] = \) from i to j 의 경로중 k 이하의 vertex만을 통과하여 얻을 수 있는 최단거리\( D_{(0)}[i,j] = W[i,j] \) 0이..
Explain양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75 + 7 + 5 = 87이다.이때 n을 d(n)의 생성자라고 하며 생성자가 없는 숫자를 셀프 넘버 라고 한다.10000보다 작거나 같은 셀프넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.Solution간단하게 1~10000까지의 수를 순회하며 d(n)을 실행 후 생성되는 n을 array를 활용하여 저장. 이때 array의 크기는 10001로 지정하며 array에 0이 저장되어 있는경우 생성자가 없는 수 이므로 셀프넘버이므로 해당 숫자만 출력.Code#define LIMIT 10000 int d(int n); int main(void) { int n = 1,i; char s..
Explain행렬의 곱셈 알고리즘에 대해서 정리행렬의 곱셈 알고리즘에는 여러 가지 방식이 존재한다 이 중에서도 단순한(Iterative, Divide and Conquer) 알고리즘과 스트라센(strassen) 두 알고리즘의 차이점을 비교.단순한 방식(Iterative) 의 알고리즘의 대부분은 \(\Theta(n^3) \)의 시간의 시간 복잡도를 가진다.이외에도 Pan, Bini, CW, SW 방식 등의 다양한 알고리즘이 존재한다.두개의 정사각형[n*n] 행렬의 곱은 \( 2n^2 \) 의 원소를 가지므로 두 행렬의 곱은 \( \Omega(n^2) \) 이다.Iterative AlgorithmC = AB, n * m 크기의 행렬 A와 m * p 크기의 행렬 B가 있을때 행렬 C 는 n * p의 크기를 가..
Explain피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞 두 피보나치 수의 합이된다. (\( F_n = F_{n-1} + F_{n-2} \))모든 문제를 Recursion 한 방식으로 생각하는 것뿐만 아니라 그 이후 반드시 다른방식(Iteration, Memozation) 등 과 비교하여 최적의 방법을 찾아내는 작업도 병행되어야 하는 점을 알아야 된다.이 문제는 Recursion 방식의 큰 위험성에 대해 파악할 수 있는 문제이다.Formula$$\begin{equation*} F_n=F_{n-1}+F_{n-2}, \quad F_1=1, \quad F_2=1 \end{equation*}$$ $$\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..
- Total
- Today
- Yesterday
- Kotlin
- 알고리즘
- Math
- algorithm
- 비트
- mathjax
- Highlighter
- 안드로이드
- mysql
- C
- highlightjs
- 행렬
- python
- 삼항연산자
- syntax highlighting
- DNS
- Bit
- 비트마스크
- robocopy
- Matrix
- Android
- 수식
- 도메인
- 비트연산자
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |