Brute force Study

[Algorithm/Divide&Conquer] 10. 거듭 제곱 계산법

거듭 제곱 계산법C^2을 계산하기 위해서는 다음과 같이 C 자신을 두 번 곱해야 한다C^2 = C X CC^n을 계산하려면 C 자신을 n번 곱해야 한다.이를 코드로 바꾸면 다음과 같다int Power( int Base, int Exponent ){ int i=0; int Result = 1; // C^0은 1이므로 for ( i=0; i 지수 크기만큼 곱셈을 수행하므로 O(n) 수행 시간을 소요한다는 사실을 알 수 있다.이보다 더 빠른 방법은 없을까?접근C^8은 C x C x C x C x C x C x C x C 로 정의되지만다음과 같이 표현할 수도 있다. C^2을 구한 뒤 제곱을 두 번 더 반복하여 결국 세 번의 곱셈만 수행함으로써 같은 결과를 얻을 수 있다.하지만 이 방법을 모든 제곱 연산에 적용할..

[Algorithm/Divide&Conquer] 09. 분할 정복을 적용하는데 있어서 주의할 점

분할 정복을 적용하는데 있어서 주의할 점분할 정복이 부적절한 경우입력이 분할될 때 마다 분할된 부분 문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 커지는 경우ex) 피보나치 수 구하기recursive하게 정의 : F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.예를 들어, n 번째의 피보나치 수를 구하는데 F(n) = F(n-1) + F(n-2)로 정의되므로 재귀 호출을 사용하는 것이 자연스러워 보이나, 이 경우의 입력은 1개이지만, 사실상 n의 값 자체가 입력 크기인 것이다따라서 n이라는 숫자로 인해 2개의 부분 문제인 F(n-1)과 F(n-2)가 만들어지고, 2개의 입력 크기의 합이 (n-1) + (n-2) = (2n-3)이 되어서, 분할 후 입력 크기..

[Algorithm/Divide&Conquer] 08. L-트로미노 타일링

트로미노 타일로 체스판 채우기구멍이 하나 있는 정사각형 체스판을 L 자 모양의 트로미노(tromino) 타일로 채울 수 있는가?체스판의 크기를 2^k ×2^k 라 가정  접근가장 작은 크기의 부문제인 “구멍이 하나 있는 2×2 체스판” 에 대해 어느 곳에 구멍이 있더라도 체스판을 채우는 것이 가능한가? -->  “구멍이 하나 있는 2k×2k 체스판”에서 “구멍이 하나 있는 21×21 체스판”으로 문제를 점차 줄여나갈 수만 있다면 분할정복 알고리즘을 사용하여 해결 가능하다. 아이디어정사각형의 체스판을 4개의 작은 체스판으로 나눈다하나의 2^k X 2^k 체스판 문제에서 4개의 2^(k-1) X 2^(k-1) 체스판 문제로 분할한다.그런데, 3개의 2^(k-1) X 2^(k-1) 체스판에는 구멍이 없다.원래..

최근접 점의 쌍 문제란?2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 가장 간단한 해결 방법모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운점의 쌍을 찾다.nC2 X O(1) = O(n^2)이것보다 효율적인 방법은 없을까?분할 정복을 이용한 해결 방법1. n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리 (d)를 가진 점의 쌍을 일단 찾는다. (recursive하게 반복하여 구함)2. [결합] 2개의 부분해를 취합할 때에는 반드시 두 부분 문제서 각각 한 점씩 포함되는 점의 쌍 중에서 그 거리가 d 보다 작은 쌍을 찾는다. (중간영역 고려!)만일 이러한 쌍이 있다면 그런 쌍 중에 ..

분할 정복 기법과 C++ 표준 라이브러리 함수앞선 게시글에서 알고리즘에 필요한 기능을 직접 구현해보았지만, C++ 표준 라이브러리는 미리 정의된 다수의 알고리즘 함수를 제공하고 있다.std::binary_search()std::binary_search() 함수는 정렬된 범위에서 특정 값을 찾기 위해 이진 검색 알고리즘을 사용합니다. 이 함수는 주어진 값이 정렬된 범위 내에 존재하는지를 확인하고, 존재 여부에 따라 true 또는 false를 반환합니다.헤더 파일:#include 사용법:bool binary_search(InputIt first, InputIt last, const T& value);bool binary_search(InputIt first, InputIt last, const T& valu..