아주 멋진 닭 내가 그와 눈을 마주쳤을 때, 그는 나에게 다가왔다. 오, 아주 멋진 닭이여! '꼬끼오' 하고 울어다오. 직접 쓴 시이다.

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net divide and conquer 문제인데, 다소 까다로운 부분이 있다. 직접 2차원 배열을 돌면서 수를 일일이 입력하고 다니면 N>=15라는 조건 때문에 시간 초과가 발생한다. 따라서 4개의 사분면으로 분할하여 계산을 생략해주는 과정이 반드시 필요하다. 나는 sizeRec에 미리 작은 사분면의 넓이를 저장한 후에 어느쪽 사분면이냐에 따라서 0, 1, 2, 3을 곱해 주어 직접 계산하는 과..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net divide and conquer로 해결할 수 있는 문제이다. start에서 end까지의 부분 히스토그램을 보았을 때, 그 안에서 만들 수 있는 직사각형의 최대 넓이는 세 경우 중 하나에서 구할 수 있다. 편의상 mid = (start+end)/2 로 정의한다. 1. start ~ mid까지의 부분 히스토그램 중 최대 넓이 2. mid+1 ~ end까지의 부분 히스토그..

매우 간단한 greedy와 sort 문제이다. 입력받은 물이 새는 위치를 정렬하고, 정렬된 값을 앞에서부터 테이프를 가장 많이 남기는 방식으로 붙여나가면 된다. 이것의 정당성 증명은 간단하다. 특정 물이 새는 위치 leak[i]까지만 보았을 때, leak[i]가 이미 테이프로 cover되어 있다면 테이프를 붙이지 않는 것이 자원을 가장 아끼는 방법이고, 테이프가 cover되어 있지 않다면 테이프를 가장 많이 남기는 방식으로, 즉 leak[i]-0.5 지점부터 붙이는 것이 가장 자원을 아끼는 방법이다. leak[i]까지만 보았을 때는 이보다 효율적인 방법은 없고, leak[n]까지 이를 반복하면 된다. 시간복잡도는 NlogN + N = O(NlogN)이다. 1 2 3 4 5 6 7 8 9 10 11 12 ..

• 예언의 종류 예언의 종류는 두 가지가 있다. 1. 현재까지 나타난 경향성을 바탕으로 미래를 개연적으로 예측하여 말하는 것, (개연적 예언) 2. 어떠한 방식으로든 미래를 직접 또는 간접적으로 체험하여 그 이야기를 전달해주는 경우가 있다. (체험적 예언) • 개연적 예언(미래예측적 예언) 첫 번째 개연적 예언의 경우는 앨빈 토플러같은 미래학자들의 미래예측이 그에 해당하고, 단조롭고 예측 가능한 삶 속에서 일상적으로 회자되는 예언까지도 이에 해당한다. 개연적 예언의 특징은 다소간 추상적이며, 확률을 기반으로 이루어지므로 예언자의 개인적 능력에 적중률이 좌우된다. • 체험적 예언(미래경험적 예언) 문제가 되는 것은 두 번째의 경우인데, 체험적 예언은 실제로 미래에 대한 이야기를 절대자로부터 전해듣거나, 직..

• gradient descent(경사 하강법) · gradient descent 신경망의 최적화(optimization) 과정에서는 gradient descent를 사용한다. gradient는 결과값에 대한 weight의 편미분 벡터이다. 기하적으로는 기울기가 가장 가파른 접선 벡터를 의미하여 steepest descent(최급경사법)이라고도 한다. 예컨대 다음과 같은 간단한 이변수 함수를 정의하자. 이 함수 f의 gradient는 다음과 같이 쓸 수 있다. gradient가 가리키는 방향으로 접근함으로써, 극소값 또는 극대값을 얻을 수 있다. (반드시 최소값 또는 최대값이 되는 것은 아니다) 위의 예를 시각화해 보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..

https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com 재귀 연습 문제이다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #i..

적률(Moment)란 Random Variable X의 n승의 expectation을 의미한다. 예를 들어 X의 1차 적률은 E(X), 2차 적률은 E(X^2) 이런 식이다. 이런 적률을 생성하는 함수로서, 다음과 같다. 이 적률생성함수를 n번 미분하여 t=0을 대입하면 X의 n차 적률을 구할 수 있다. 증명 e^(tx)는 테일러 전개에 의해 다음과 같이 표현될 수 있다. a=0을 대입하면 다음과 같다.(매클로린 급수) 양변의 expectation은 다음과 같다. 이 식의 양변을 n번 미분하고 t=0을 대입하면 적률을 구할 수 있다. 다음 예를 보자. 위와 같이 한 번 미분한 식에 t=0을 대입하면, 이를 일반화하면 다음과 같다. Continuous PDF의 경우 적분으로 expectation을 구할 수..

Taylor series는 함수를 한 점에서의 derivatives들의 무한 개의 항의 합으로 근사하는 방법이다. 일반적으로 이 점에서 두taylor function과 원래 함수는 어느 정도 근사한다. 유도 테일러 함수는 미적분의 기본 정리로부터 간단히 유도할 수 있다. 먼저 미적분의 기본정리 식을 f(x)에 대해 정리하고, f'(t)의 정적분항을 1과 f'(t)로 부분적분한다. 이때 적분상수는 C로 둔다. 적분상수를 -x로 대입하고, 뒤 정적분식을 다시 부분적분하면 다음과 같이 정리할 수 있다. 이러한 과정을 반복하면 다음과 같다. 이를 간단하게 쓰면 다음과 같다. 이를 테일러 급수(Taylor series)라고 한다. 또한 a=0인 특수한 경우에 식은 다음과 같이 표현되는데, 이러한 형태를 매클로린 ..