말 그대로 수를 정렬하는 문제입니다. 문제의 조건을 잘 읽어보면, N이 10,000,000이라 O(NlgN)의 정렬 방법을 사용하면 시간 안에 풀 수 있을거라는 추측을 할 수 있습니다. 하지만, 문제의 메모리 사용 조건이 8MB이기에, 1000만개의 수를 모두 배열 안에 저장할 수는 없습니다. 그럼 어떤 방법을 생각할 수 있을까요? 문제에서 제시하는 수의 범위를 유심히 살펴봐야 합니다. 입력이 1000만개가 주어지는데, 입력으로 주어지는 수는 1부터 1만까지밖에 없습니다. 1만개를 초과하는 수가 입력으로 주어지면, 비둘기 집의 원리(서랍원리?)에 의해 반드시 중복이 존재할 수 밖에 없습니다. 따라서, 모든 수를 배열에 저장하는게 아닌수의 개수를 길이가 10000인 배열에 저장하면 됩니다. 입력이 종료된 ..
이 문제는, N개의 지형 높이가 주어졌을 때,오르막길의 최대 높이 차이를 찾는 문제입니다. 해결 방법은 간단합니다. 저는 2가지 변수를 처음과 끝을 가리키는 화살표처럼 사용해 문제를 해결했습니다. 처음에 first와 last는 동일하게 arr[0]입니다. 예제를 통해 진행을 알아볼까요 8 12 20 1 3 4 4 11 1입력이 다음과 같이 주어집니다.for문을 통해 다음 원소가, 현재 last가 가리키고 있는 원소보다 크지 않을때까지 진행합니다.```1) first = 12, last = 12 - 12 < 20? TRUE2) first = 12, last = 20 - 20 < 1? FALSE 2-1) answer = max(answer, last-first);3) first = 1, last = 1.....
2016년 ACM-ICPC 한국 인터넷 예선 D번 문제였던 Message Passing 입니다. 규칙을 찾고, 길이가 몇차든, 항이 M개인 선형 점화식의 N번째 항을 O(M^3 logN)에 구하는 방법을 알고 있다면 풀 수 있는 문제였습니다. 문제에 쓰여 있는규칙을 n=2, n=3일때 몇 번 나열해본다면, 위의 규칙은 모두 피보나치 수열과 유사한 형태의 규칙을 띈다고 생각하시면 됩니다. 위의 규칙을 깨달았다면?문제의 70%는 해결 되었습니다. 이 문제를 설명하기 위해선 여러가지 문제를 거쳐야 합니다.먼저 BOJ 2749번 피보나치 수 3문제입니다. 이 문제는 A(n) = A(n-1) + A(n-2)의 선형 점화식의 항을 빠르게 구하는 것을 목표로 합니다. 게다가 n의 범위가 10^18(1,000,000,..