Graphics Programming

평소처럼 블로그에다 번역하려고 했는데 아무래도 책 한 권을 통째로 번역하는 거다 보니... 위키독스라는 좋은 서비스가 있어서 여기에 작성하고 있다. 주소: https://wikidocs.net/book/204

문제 출처 http://koistudy.net/?mid=prob_page&NO=390 금방 풀 것 같았는데 의외로 테스트를 통과하지 못하고 질질 끌었다. 먼저 [1 1]에서 시작해서 X 버튼이나 Y 버튼을 누르는 경우를 5~6단계까지 전부 그려보며 패턴을 찾아내기는 개뿔 하나도 못 찾았다. 방향을 바꿔서 [n 1] [n 2] [n 3] ... [n n-1]에서 [1 1]을 만드는 방법은 어떨까? 예를 들어 [n 1] length = 0; return q; } void push(Queue q, Pair p) { Pair tail; if(q->length == 0){ q->first = p; }else{ tail = q->first; while(tail->next) tail = tail->next; tail..

문제 출처 http://koistudy.net/?mid=prob_page&NO=600 이진수를 십진수로 변환해서 %(나머지) 연산자를 쓰면 될 것 같지만 자릿수가 최대 10만이다. 정수 변수는 보통 32비트고 많아봤자 128비트까지이므로 불가능하다. 처음에는 3의 배수들을 이진수로 바꿔 나열하고 패턴을 찾아보려 했지만 3 x 2^n 꼴인 수들이 오른쪽에 0이 하나씩 늘어나는 것 빼고는 딱히 패턴을 찾을 수 없었다. 3 -> 11₂ 6 -> 110₂ 9 -> 1001₂ 12 -> 1100₂ 15 -> 1111₂ ... 다음으로 입력받는 수를 쪼개서 처리해보려 했다. 예를 들어 a = b + c인데 b와 c가 3의 배수이면 a도 3의 배수다. 가령 입력이 110011₂이라면 11₂= 3으로 3의 배수이므로 ..

문제 출처 http://koistudy.net/?mid=prob_page&NO=144 위키피디아(http://en.wikipedia.org/wiki/Maximum_subarray_problem)를 보니 정식 이름은 Maximum subarray problem인 것 같다. 문제 소개는 출처에 있다. 가장 먼저 모든 경우를 검사하는 Θ(nn) 알고리즘이 떠올랐다. 원소가 n개일 때 부분합의 총 개수는 양 끝을 선택하는 방법의 개수로서 C(n,2) = n(n+1)/2 개다. 모든 부분합을 구하여 그 중 최댓값을 선택한다. 예를 들어 입력이 [1, -2, 5, -3, 6, 2] 이라면 i ~ j번째 원소의 합을 다음과 같이 표로 나타낼 수 있다. (i, j) 0 1 2 3 4 5 0 1 -1 4 1 7 9 1 ..

원문: GPU Gems 2: Chapter 8. Per-Pixel Displacement Mapping with Distance Functions 주소: https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter08.html 용어 번역 distance function: 거리 함수 displacement mapping: 변위 매핑 ray tracing: 광선 추적 surface: 표면 implicit function: 음함수 mapping: 매핑(사상) fragment shader: 조각 셰이더 William Donnelly University of Waterloo 이번 장에서는 물체에 소규모 변위 매핑을 적용하기 위한, 거리 매핑이라는 픽셀 셰이더 기..

주소 http://jsfiddle.net/codeonwort/v4LEc/ 카오스(http://www.yes24.com/24/goods/8949034)를 읽고 jsfiddle에서 만들었다. 누른 곳 기준으로 확대하게 만들었는데 실수 변수 정밀도 때문에 얼마 안 가서 뭉개진다. 뭉개지지 않고 계속 확대되는 동영상(http://www.youtube.com/watch?v=0jGaio87u3A)을 봤는데 이렇게 하려면 Big Number를 구현하거나 꼼수를 찾아봐야 할 것 같다. 올ㅋ 이거 끼워넣기도 됨?

서로 다른 k+1 개 점 ($ (x_0, y_0) $) ~ ($ (x_n, y_n) $)을 보간하는 k차 라그랑주 다항식은 다음과 같은 꼴이다. 주어진 점들은 반드시 지나야 하기 때문에 ($L(x_i) = y_i$) 를 만족하며, ($L_k (x)$) 는 ($x_0$) ~ ($x_n$) 에 대해 다음 성질을 만족하는 k차 다항식이다. 예를 들어 ($ L_0(x_0) = 1 $) 이고 ($ L_0(x_1) = L_0(x_2) = ... = L_0(x_n) = 0 $) 이다. ($ L_0(x) $) 를 구하는 방법은 여러 가지가 있겠지만 선형대수학에 맛들려 에서 역행렬을 구해 곱하겠다면 무운을 빈다. ($ L_0(x_1) = L_0(x_2) = ... = L_0(x_n) = 0 $) 이므로 n개의 x값 ($..

중간값 정리 - 위키피디아http://ko.wikipedia.org/wiki/%EC%A4%91%EA%B0%84%EA%B0%92_%EC%A0%95%EB%A6%AC 뉴턴법으로 어떻게 구해보려고 쇼를 하다가 미적분학 강의 때 중간값 정리 보고 '아.. -_-' 하며 구현했다. 함수 f:R->R 이 해를 구하려는 구간 내에서 연속이다고 가정한다. 그러면 f(a)와 f(b)의 부호가 다를 경우 그 사이에 f(c) = 0인 지점이 반드시 있는데 c가 바로 방정식 f(x) = 0의 해다. 그러니 정의역에서 해를 구할 구간을 적당히 잡고 적당한 간격으로 함숫값을 추출해서 바로 전에 추출한 함숫값과 부호가 다르면 그 구간에서 이진 분할을 하든 열 조각으로 쪼개든 하여 범위를 점점 좁혀나가면 해의 근사값을 얻을 수 있다...