목록알고리즘 (3)
Graphics Programming
문제 출처 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 ..