@markdownACM-ICPC 2016년 대한민국 인터넷 예선에 출제되었던 문제입니다. Q-Index라는 개념을 이용해 문제를 푸는 것이었는데요. 번역문보다 원문을 보는게 이해가 빠른 문제라 푸는데 조금 시간이 걸렸던 문제입니다. 문제를 해설해보면 "Q 인덱스가 k이다" 라는 말은 " n개중에 k개의 논문이 k번 이상 인용되었고 n-k의 논문이 k번 미만 인용되었다." 라는 의미입니다. 논문의 개수와 인용회수의 범위를 살펴보면,논문의 개수 n은 1 이상 1000이하,논문의 인용 회수(편의상 m)은 0이상 10000이하 라고 되어있습니다. 제가 생각하는 간단한 문제 풀이 방법은, 논문의 인용 횟수를 통해, 존재하는 논문을 전부 탐색해서, q-index의 최대값을 구하는 방법입니다. Psuedo Code를..
이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,000,000,000,000)인 걸 보아 절대 동적 계획법으로는 풀 수 없는 문제입니다. 이럴 땐, 점화식을 자세히 살펴보고, 분해해보아야 합니다. 수열의 n번째 항과, n-1번째 항을 위 아래로 나열해보면 과 같이 나타낼 수 있습니다. 그럼? 이것을 행렬로 나타내보면? 입니다. 오! 개쩔죠? 그럼? 이 점화식을 계속해서 나열해본다면! 이 될 것이고 이렇게 되니까, 피보나치 수열의 일반 행렬을 얻을 수 있습니다. n by n의 행렬을 곱하는 데엔 보통 O(n^3)의 시간 복잡도가 필요합니다.그리고 같은 행렬을 M번 곱하는 데는 O(Mn^3)의 시간이..
교환학생 온 3월부터 계속 느끼는 거지만, 여기 학식은 좀 비싼 것 같다. 거의 한 끼 먹을때마다 450-500엔 돈을 내야 한다. 아침을 먹지 않는다고 해도, 점심과 저녁을 먹으면 무려 1000엔 이상의 돈이 든다. 저녁을 5-6시 사이에 먹기 때문에, 10시쯤 출출해지는데 야식까지 먹으면 더 들 수 있다. 물론 저녁을 든든하게 먹으면 되지 않는가? 하는 의문도 있을 수 있지만 솔직히 500엔으로 일본에서 저녁을 배부르게, 든든하게 먹는다는 건 조금 어려운 것 같다. 그래서 요새는 점심 도시락을 싸볼까 생각중인데, 도시락을 싸오는 친구들을 보니 소풍날 애니에서 여주가 남주에게 거하게 한상 차려오는 것처럼 그렇게 거창하게 싸오는 것 갓진 않다. 요리를 내가 아얘 못하는 것도 아니고, 도시락을 싸서 다니면..
작성중
오사카대학교 기초공학부 정보과학과로 교환학생 온지 벌써 반 년이 지나갔다. 3월 28일에 일본 도착해서 지금이 10월 13일이니까 반 년쯤 된거라고 할 수 있다. 가을~겨울 학기(2학기를 이렇게 부른다)에는 내 대학생활의 마지막 금공강을 만들어 보기 위해 시간표를 잘 짜봤는데. 아직 목요일 4교시인 통계학 C-II가 확정이 되지 않아 걱정하고 있다. 프로그래밍 D는 Java 수업이고, 데이터구조와 알고리즘은 말 그대로고, 소프트웨어 구성론은 소프트웨어 공학이다. 그 밑의 정보해석 A는 점화식이나 정수론 같은 간단한 수학을 배우는 과목이다. 계산기언어는 PL이고 정보처리는 C언어(양심 어디?) 통계학은 말 그대로 통계이다. 무난한 시간표에, 절대평가이고 저번 학기의 시험 난이도를 봤을때 어렵게 나오지 않는..