Graphics Programming

포함-배제의 원리는 합집합의 크기 ($ n(A_1 \cup A_2 \; \cup \; ... \; \cup \; A_k) $) 를 세는 데 활용할 수 있는 기법이다. 다음은 수학 정규교육에서 집합을 배울 때 나오는 간단한 공식이다. $$ n(A \cup B) = n(A) + n(B) - n(A \cap B) $$ 위키피디아를 보면 위 공식을 k개 집합에 대해 일반화한 공식이 나온다. 출처: 위키피디아 하지만 위 공식을 코드로 구현하라면 가능할지 모르겠다. 대신 재귀적인 형태를 살펴보자. ($ A = A_1 $) , ($ B = A_2 \; ... \; A_k $) 를 대입하면 $$ n(A_1 \cup A_2 \; \cup \; ... \; \cup \; A_k) = n(A_1) + n(A_2 \cup \..

세그먼트 트리는 부분합 또는 RMQ(Range Minimum Query)에 적합한 자료구조다. 부분합 구하기는 펜윅 트리를 써도 되기 때문에 RMQ만 알아보겠다. RMQ를 위한 세그먼트 트리는 원소 ($ A[1..n] $) 들에 대해 다음 두 연산을 ($ O(log \, n) $) 으로 효율적으로 처리한다. 1. query(l, r): ($ A[l..r] $) 내에서 최솟값을 반환한다.2. update(i, x): ($ A[i] = x $) 로 갱신한다. 세그먼트 트리에는 이 외에도 구간 갱신(range update) & 단일 원소 질의(single element query), 지연 전파(lazy propagation) 등의 개념이 있다. 세그먼트 트리의 기본과 이러한 고급 개념들은 다음 글들에 자세히 ..

펜윅 트리는 정수 ($ a[1], a[2], ..., a[n] $)에 대해 다음 연산을 수행할 수 있는 자료구조다.1. query(p): ($ a[1] + a[2] + ... + a[p] $) 을 ($ O(log n) $)으로 계산한다. 2. update(i, x): ($ a[i] += x $) 를 ($ O(log n) $)으로 수행한다.부분합 ($ a[l] + a[l+1] + ... + a[r] $)을 구하려면 ($ sum(r) - sum(l-1) $)을 계산한다. (단 ($ a[0] = 0 $)으로 정의)다음과 같은 단순 부분합의 경우 1번 연산에는 ($ O(1) $)이 걸리지만 2번 연산에는 ($ O(n) $)의 시간이 걸린다. 1번 쿼리가 m번, 2번 쿼리가 k번 있을 때, 이 방법은 ($ O(m..

문제: https://www.hackerrank.com/challenges/game-of-stones-1 다이나믹 프로그래밍을 시도해보자. dp[i]를 다음과 같이 정의한다. dp[i] = 돌이 i개 남았고 플레이어 1의 차례다. 플레이어 1이 이길 수 있는가? dp[n] == true이면 플레이어 1이 이기고, 아니면 플레이어 2가 이긴다. 하지만 이 정의는 플레이어 2를 고려하지 않는다. 식을 하나 더 만들어보자. dp2[i] = 돌이 i개 남았고 플레이어 2의 차례다. 플레이어 2이 이길 수 있는가? 한 번에 돌을 2개, 3개, 또는 5개 가져갈 수 있으므로 돌이 1~5개 남은 상황에 대해 생각한다. dp[1] = false (플레이어 1이 선택 불가)dp[2] = true (2개를 가져가면 0개가..

문제: https://www.acmicpc.net/problem/9520 다이나믹 프로그래밍을 코딩하는 방식은 크게 재귀와 루프로 나뉜다. 재귀 방식은 일종의 지연 평가(lazy evaluation)를 구현한다. (i,j) 항을 참조했는데 평가되지 않았다면 평가하여 반환하고, 이미 평가되었다면 그대로 값을 반환한다. 루프 방식은 for/while로 루프를 돌며 DP 테이블을 채운다. 문제에 따라 무엇을 써도 상관 없는 경우가 있고 재귀나 루프 중 하나가 훨씬 편한 경우도 있다. 나는 루프를 선호한다. 이 문제의 경우 방문 순서를 그리면 1~(n-1)번 도시들은 무조건 n번 도시의 왼쪽이나 오른쪽에 통째로 있어야 한다. 따라서 점화식을 다음과 같이 세울 수 있다. dp[i][j] = 도시 1~i를 방문하는..

문제 출처 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 ..