알고리즘 5

[ICPC] Monotone Walkway(2015 대전 예선)

[ICPC] Monotone Walkway(2015 대전 예선) Monotone Walkway이번 ICPC 예선 문제이다. 예선 문제들 중 쉬운 문제였으며 유사한 문제가 많이 존재한다. 문제 요약첫 줄에는 테스트 케이스 개수가 주어진다. 각 테스트 케이스의 첫 줄에는 좌표의 개수가 주어지고, 개수 만큼의 좌표가 주어진다. 마지막 줄에는 출력해야 할 카페 좌표의 개수와 순서가 주어진다. 각 순서의 카페 좌표를 출력하면 된다. 풀이- 좌표를 저장할 자료구조를 정한다. 카페 좌표(x, y)는 같은 순서를 가져야 함을 명심한다.- 카페 좌표들의 x를 기준으로 오름차순 정렬한다. x가 같은 좌표들은 y 기준 오름차순 정렬한다.- (0,0)부터 마지막 카페까지 순차적으로 가면서, 바로 전 카페와 지금 위치한 카페의..

[재귀 알고리즘] Computing Powers & Fast Version

[재귀 알고리즘] Computing Powers & Fast Version Computing Powers (제곱 계산하기)제곱 계산을 재귀적으로 프로그래밍 해보고 더 빨리 계산하는 법도 프로그래밍 해 보겠다.일반적인 방법,$$ p(x,n) = x^n $$$$ p(x,n) = \begin{cases} 1 & \quad \text{n=0} \quad \text{(base case)} \\ x*p(x, n-1) & \quad \text{n>0} \quad \text{(recursive step)} \\ \end{cases} $$ 1234567891011121314151617double powerRecursive(double x, int n){ // Time Complexity : O(n) if (n==0) r..

[재귀 알고리즘] Reverse Array (배열 뒤집기)

[재귀 알고리즘] Reverse Array (배열 뒤집기) Reversing Array (배열 뒤집기)주어진 배열 $ [x_1, ... , x_n] $을 $ [x_n, ... , x_1] $로 바꾸는 것이 목적이다. 재귀의 개념을 이해하기 쉬운 예제라 재귀로 구현했지만 반복문으로 구현하는게 훨씬 효율적이다. 처음에는 1(a[0])과 7(a[6])을 바꾸고 2(a[1])와 6(a[5])를 바꾸는 함수를 호출한다.순차적으로 진행하다가 두 점이 만나거나 교차되면 종료한다. 12345678910111213141516171819202122232425262728293031323334353637383940#include using namespace std; void swap(int arr[], int a, int b..

[재귀 알고리즘] Linear Sum (순차합)

[재귀 알고리즘] Linear Sum (순차합) Linear Sum (순차합)순차합은 간단히 반복문으로 구현 가능하다. 하지만 재귀적으로 생각하는 것에 많은 도움을 줄 수 있는 예제이다.n개의 정수 $x_1, x_2, ... , x_n$가 있을 때, 주어진 정수의 합 $S(n) = \displaystyle\sum_{i=1}^{n} a_i$를 계산하는 문제이다. $$ S(n) = \begin{cases} a_1 & \quad \text{n=1} \quad \text{(base case)}\\ S(n-1)+a_n & \quad \text{n>1} \quad \text{(recursive step)}\\ \end{cases} $$ 코드를 먼저 보면,1234567891011121314151617#include ..

[소수 알고리즘] 소수의 특성과 에라토스테네스의 체

[소수 알고리즘] 소수의 특성과 에라토스테네스의 체 소수의 특성소수(Prime Number)는 약수로 1과 자기 자신만을 가지는 정수이다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현된다. 예를 들면,$$ 91 = 7 * 13 $$$$ 10164 = 7 * 11^2 * 12 $$이를 소인수 분해의 일의성이라고 하는데 이 특징은 최대 공약수를 구하는데 매우 유용하게 사용될 수 있다. 최대 공약수는 두 개 이상의 자연수가 가지는 약수 중 가장 큰 수이다. 약수 또한 자연수 이므로 하나의 소수들의 곱으로 표현된다. 즉 최대 공약수를 구하려는 수들의 공통된 소수들을 모두 곱해 주면 최대 공약수가 되는 것이다.$$ 300 = 2^2 * 3^1 * 5^2, 18 = 2^1 * 3^2 $..