반응형 알고리즘 썸네일형 리스트형 [BOJ 2399] 거리의 차이 2399번 (거리의 차이) 이 문제는 단순히 이중 반복문을 이용하여 (x[0] ,x[0]~x[n]) , (x[1], x[0]~x[n]), ... (x[n], x[0]~x[n]) 이렇게 총 n^2개의 모든 쌍을 구하는 방식으로 구할 수 있다. 하지만 이 방식은 시간복잡도가 O(n^2)이기 때문에 n이 커지면 시간이 오래 걸리게 되고, 또 이 문제의 분류가 "정렬" 이기 때문에 정렬을 이용하여 문제를 풀어보았다. 정렬을 이용한 풀이에는 아주 유용한 "수학적인 아이디어"가 이용된다. 1. 우선 정렬을 통해서 n개의 점을 좌표가 오름차순이 되도록 정렬을 한다. 2. 특정한 x[i]를 생각해보면, 모든 n^2개의 쌍 중에서, x[i]는 총 2n번 등장하게 된다. (x[1] ~ x[n] , x[i]) : n개 / .. [BOJ 11051] 이항 계수 2 11051번 (이항 계수 2) Try 1) 단순히 이항 계수의 식인 nCk = n! / k!(n-k)! 을 이용하여 해결하기 (idea) N과 K를 입력받았을 때, 1부터 N까지 곱하고, 그 후 1 ~ K까지 나누고, 1 ~ N-K까지 나눈다. 하지만 이 경우, 가장 큰 범위의 정수형 타입인 long long 타입이라고 하더라도, N이 큰 수면 오버플로우(Overflow)가 발생해서 정확한 수가 저장 되지 않는다. 따라서, 이 방법은 올바른 답을 도출해낼 수 없다. Try 2) 이항 계수 공식 nCk = n-1Ck-1 + n-1Ck 을 이용하고, Try 1)의 문제점을 해결하기 위해 (a+b)%mod = a%mod + b%mod 성질 이용하기. (idea) 이항 계수 공식인 nCk = n-1Ck-1 + .. 메모이제이션 (Memoization) 메모이제이션 (Memoization) 이 알고리즘에 대해서는 백준 알고리즘 11051번 (이항 계수 2) 문제를 통해서 학습하게 되었다. 메모이제이션은 동적 계획법 (Dynamic programming)의 핵심 기술이다. (동적 계획법에 대한 설명은 따로 정리를 할 예정이므로 이 게시물에서 개념에 대한 설명은 간단하게 한다.) 우선 해당 문제에 대해서 한번 살펴보자. 다음과 같이 문제가 주어져 있다. 즉, 예를 들어 입력으로 5 2를 입력하게 되면, 10이 출력되어야 한다. 이 알고리즘에 대해 알지 못하거나 익숙하지 않은 사람들은 필자를 포함하여 대부분 위의 식을 이용해서 풀었을 것이다. 즉, 만약 "10 5" 가 입력되었다면, (N = 10, K = 5) 1부터 10까지 곱한 후, 다시 1부터 5까지 .. 이전 1 ··· 4 5 6 7 다음
