블로그

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

[재귀 알고리즘] 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 (배열 뒤집기) 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 (순차합)순차합은 간단히 반복문으로 구현 가능하다. 하지만 재귀적으로 생각하는 것에 많은 도움을 줄 수 있는 예제이다.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 ..

[ICPC] Goldbach's Conjecture(2011 대전 예선) Goldbach's Conjecture골드바흐의 추측(Goldbach's Conjecture)는 오래전부터 알려진 정수론의 미해결 문제이다. 모든 2보다 큰 짝수는 두 개의 소수의 합으로 표시될 수 있다는 것이다. 정의나 이론이 아닌 추측인 이유는 모든 짝수에서 두 소수의 합으로 표현 가능한지는 증명되지 않았기 때문이다.(참조 - [소수 알고리즘] 소수의 특성과 에라토스테네스의 체 http://ledgku.tistory.com/61)예를 들어,$$ 4 = 2 + 2 $$$$ 6 = 3 + 3 $$$$ 8 = 3 + 5 $$$$ 10 = 3 + 7 = 5 + 5 $$$$ 12 = 5 + 7 $$$$ 14 = 3 + 11 = 7 + 7..

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

Maximum Contiguous Subsequence Sum(MCSS) 알고리즘 분석 Maximum Contiguous Subsequence Sum(MCSS) - n개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어졌을 때, 연속적인 부분 수열의 합 $\sum_{k=i}^{j} a_k$ 이 최대가 되는 구간 (i, j)와 그 구간의 합을 계산하는 문제. 5 -7 2 3 -4 5 2 -7 8 -7 $\sum_{k=3}^{9} a_k = 9$ MCSS 알고리즘 (Time complexity : O($n^3$))1234567891011121314151617181920212223unsigned long int mcssN3(int a[], int n, int *start, int *end){ int ..

[알고리즘 사이트] 알고리즘 문제 풀이 사이트 오일러 프로젝트(Project Euler)수학적인 문제들을 프로그래밍으로 해결하는 퀴즈 풀이 사이트 Synap에서 한글로 번역한 사이트를 제공하고 있다. 본 사이트의 모든 문제가 번역되어 있진 않지만 현재 100여개의 문제가 번역되어 있고 많은 사람들이 사용하고 있다. 자신이 원하는 언어로 문제를 풀고 답만 입력하면 된다. 입력한 답이 정답일 경우 다른 사람들이 문제를 푼 코드들을 볼 수 있다.(Project Euler @kr : http://euler.synap.co.kr/)(Project Euler @net : https://projecteuler.net/) 알고 스팟(Algospot)프로그래밍 대회에서 배우는 '알고리즘 문제해결 전략'의 저자 구종만씨가..

[재귀 알고리즘] 하노이 타워(The Tower of Hanoi) - 재귀, 스택 하노이 타워 문제하노이 타워 문제는 재귀적으로 해결할 수 있는 대표적인 문제이다. 조건 : 원반은 한번에 한 개씩 옮길 수 있고 큰 원반이 작은 원반 위에 올라가서는 안된다.원반을 A에서 C로 모두 옮기면 된다. 하노이 타워 패턴- A에 있는 n개의 원반 중 맨 아래에 있는 n번째 원반을 제외한 나머지 원반을 모두 B로 옮긴다. - A에 남은 하나의 원반을 C로 옮긴다.- B의 모든 원반을 C로 옮긴다.결론을 먼저 말해서 헷갈릴 수도 있지만 하노이 타워를 원반 2개부터 하나씩 증가시키면서 해보면 같은 패턴이 반복 되는 걸 알 수 있다.하노이 타워의 최소 단위는 2개의 원반이 있을 때인데 작은 원반을 A->B로 옮기고, 큰 ..

[재귀 알고리즘] 피보나치 수열(재귀, 꼬리 재귀, 반복문) 피보나치 수열피보나치 수열은 앞에 두 수를 더해서 현재 위치의 수를 만드는 수열이다. $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... $$수학적으로 표현하면,\[ Fibonacci(n) = \begin{cases} 0 & \quad \dots \text{ n = 1}\\ 1 & \quad \dots \text{ n = 2}\\ Fibonacci(n-1) + Fibonacci(n-2) \quad \dots \text{ otherwise}\\ \end{cases} \]아래는 피보나치 수열을 일반적인 재귀, 꼬리 재귀, 반복문으로 구현한 코드이다.(꼬리 재귀 설명 : http://ledgku.tistory.com/37)C..