블로그

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

[통계학 개요] 통계학이란.. 통계학(Statistics) 정의 - 많은 양의 수치 자료를 수집하고, 정리, 요약 및 해석하는 방법을 다루는 과학의 한 분야 - 관심의 대상에 대한 자료를 수집하여, 정리, 요약하고, 이들 자료에 포함된 정보를 토대로 불확실한 사실에 대해 과학적 판단을 내릴 수 있도록 그 방법을 제시해 주는 학문 - 관측 자료를 바탕으로 추론(inference)을 하는 과학의 한 분야로서 불확실성(uncertainty)하에서 보다 합리적인 의사 결정을 하는 방법을 제시해 주는 학문 정의에 공통적으로 자료의 수집, 정리, 해석이 들어가는데, 이 세가지가 통계학의 핵심이라고 볼 수 있다. 통계학은 우리 일상에서도 쉽게 접할 수 있는데, 정당 지지율, 경제성장률, 주가지수, 연간 강수량, 제품..

[재귀 알고리즘] 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 ..

[Clion OpenCV] Jetbrain Clion OpenCV 설정 Clion OpenCV 설정Clion은 Intellij로 유명한 Jetbrain에서 만든 C, C++ IDE이다. Clion에서 OpenCV 설정을 해보도록 하겠다. 우선, OpenCV가 설치되어 있어야 한다. 안되어 있다면 아래 링크를 참조하여 설치한다.(Ubuntu : http://ledgku.tistory.com/59)(Windows : http://ledgku.tistory.com/60) 설치가 되었다면, Clion을 실행하고 새 프로젝트를 생성한다.그 다음 CMakeLists.txt 파일을 열고 아래 두 줄을 추가한다. target_link_libraries에 example은 프로젝트 이름이다. 생성한 프로젝트 명을 넣어주도..

[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 $..

[OpenCV 설치] Windows OpenCV 설치, C++ 테스트 OpenCV 설치 - OpenCV 홈페이지(http://opencv.org/)에서 OpenCV 최신 버전을 다운로드한다. - 다운로드가 완료되면 파일을 실행한다. 실행하면 아래와 같은 창이 뜨는데 압축 해제할 경로를 지정하고 Extract버튼을 눌러준다. - 제어판 - 시스템(윈도우키 + Pause)에서 환경변수 설정을 한다. 시스템 변수에서 새로 만들기를 클릭한다. - 변수 이름 : OPENCV_BUILD 변수 값 : 위에 OpenCV 압축해제 경로 + \opencv\build 입력 후 확인 - 시스템 변수 중 Path를 선택하고 편집 클릭 후 맨 뒤에 ;%OPENCV_BUILD%\x86\vc12\bin; 입력 Visual Studi..

[OpenCV 설치] Ubuntu OpenCV 설치, C++ 테스트 OpenCV 설치OpenCV는 설치해야 하는 패키지가 많으므로 스크립트로 만들어서 실행시키는게 편하다.gedit을 실행 시키고 아래 내용을 붙여 넣는다.version="$(wget -q -O - http://sourceforge.net/projects/opencvlibrary/files/opencv-unix | egrep -m1 -o '\"[0-9](\.[0-9]+)+' | cut -c2-)" echo "Installing OpenCV" $version mkdir OpenCV cd OpenCV echo "Removing any pre-installed ffmpeg and x264" sudo apt-get -qq remove ffmpeg ..