유클리드 호제법 (Euclidean Algorithm) 이란? 두 개의 자연수의 최대공약수(GCD) 를 빠르게 찾는 알고리즘이다. 유클리드 호제법이 유명한 또 다른 이유는, 이 방법이 인류 최초의 알고리즘이라고 소개되고 있기 때문이다. 최대공약수를 찾는 알고리즘은 여러가지가 있겠지만, 시간복잡도 면에서 가장 훌륭한 알고리즘이기 때문에 PS 과정에서 필요하다면 적극 활용하는 것을 추천한다. 계산 과정 유클리드 호제법은 매우 단순하다. 자연수 A, B가 있다고 가정하고, 다음과 같은 과정을 반복하기만 하면 된다. (1) A를 B로 모듈러 연산한다. (A % B) (2) 만약 나머지가 0이라면, B가 최대 공약수이다. (3) 만약 나머지가 0이 아니라면, A를 B로 바꾸고, B를 나머지로 바꾼다. 만약 A =..

코딩테스트 문제 중, 가끔 수학적인 기초를 묻는 문제에 약수, 배수 등의 문제가 출제된다. 이러한 유형의 문제를 접해본 경험이 없는 사람들은 최악의 시간복잡도를 갖는, 모든 경우를 찾는 순차적인 알고리즘으로 문제를 풀게 된다. 그러므로 PS를 준비하는 사람이라면 '모든 약수를 찾는 효율적인 알고리즘' 정도는 익혀두는 것이 좋다. 가장 단순하게 약수를 찾는 알고리즘 가장 단순한, 누구나 쉽게 생각할 수 있는 방법을 고안해보자. 만약 10의 약수를 찾는다고 했을 때, 1~10까지의 수 중에서, 10을 0으로 나누어 떨어지게 하는 수를 찾는 알고리즘을 생각할 수 있을 것이다. 10 % 1 = 0 10 % 2 = 0 10 % 3 = 1 10 % 4 = 2 10 % 5 = 0 10 % 6 = 4 10 % 7 = ..

1. 문제 2. 접근 방법 '어떤 수가 가지고 있는 약수를 빠르게 찾는 알고리즘' 을 모르면 해결이 쉽지 않은 문제이다. 나도 이 알고리즘을 몰랐기 때문에, 처음에는 시간 초과를 겪어 당황스러울 수밖에 없었다. 이 문제를 접근하는 방법은 다음과 같다. (1) N개의 숫자를 대상으로, N - 1 만큼 숫자 간의 차이들을 구한다. (2) 이 N - 1개의 '차이'들 중, 가장 작은 값을 찾는다. (3) 위에서 구한 가장 작은 값을 대상으로, 1을 제외한 모든 약수를 구한다. (4) 위에서 구한 모든 약수 중, 전체 숫자를 나눠봤을 때 0으로 나누어 떨어지는 약수들만 출력한다. 예시를 들어보자. 다음과 같이 9, 23, 58 의 3개의 숫자가 있다고 가정해보겠다. 그렇다면 위와 같이, 3개의 숫자들의 차이는 ..

1. 문제 2. 접근 방법 https://kbw1101.tistory.com/27 [백준/10816] 숫자 카드 2 (이분 탐색) 1. 문제 2. 접근 방법 이분 탐색 알고리즘으로 접근하되, 찾고자 하는 숫자가 시작하는 지점, 끝나는 지점을 찾아야 한다. 즉, 변형된 이분 탐색 알고리즘이라고 생각하면 된다. 찾고자 하는 숫자 kbw1101.tistory.com 위의 문제와 비슷하게, 이분 탐색을 응용한 알고리즘인 Lower Bound를 이용하여 푸는 문제이다. 여기에서 Lower Bound 의 의미는 다음과 같다. "찾고자 하는 수 이상의 값이 처음으로 등장하는 위치" 그렇다면 문제를 푸는 소개하겠다. 우선 LIS을 담을 배열을 만들고, 가장 첫 번째 원소의 값은 입력 배열의 첫 번째 원소와 동일하게 설..

1. 문제 2. 접근 방법 이분 탐색으로 해결할 수 있는 적당한 난이도의 문제... 라고는 하나 접근 방법이 잘 떠오르지 않아 애를 먹었던 문제이다. 이 문제는 브루트 포스적인 방법으로 접근하면, O(N * log N) 이라 시간 초과로 풀 수 없다. 그러므로 효율적인 계산 방법을 생각해야 하는데, 아래와 같이 구할 수 있음을 알게 되었다. 우선, N =5 일 때, 즉 5 X 5 배열을 통해서 계산을 생각해보자. 그리고 여기에서 k = 11 일 때, 즉 B[11] 을 찾는 경우를 생각해보자. 우리가 찾는 11번째의 숫자를 S 이라고 한다면, 다음과 같이 접근해야 한다. "전체 숫자 중에서, S보다 작거나 같은 숫자의 개수가 11개보다 작으면 안된다!" → 만약 그렇다면, 찾는 숫자의 범위를 큰 쪽으로 옮..

1. 문제 2. 접근 방법 이분 탐색의 종류인 Parametric Search 를 이용한 문제이다. 이 문제는 다음과 같은 과정으로 접근해야 한다. (1) 공유기 사이의 최소 거리가 될 수 있는 값은, 1 이다. (2) 공유기 사이의 최대 거리가 될 수 있는 값은, (마지막 공유기의 위치 - 첫 번째 공유기의 위치) 이다. (3) 중간값은 (1)과 (2)에서 구한 값의 중간값이다. (4) 중간값이 가능한 값인지 검사한다. (5) 만약, 중간값이 가능한 값이라면 → 범위를 큰 쪽으로 줄인다. (6) 만약, 중간값이 불가능한 값이라면 → 범위를 작은 쪽으로 줄인다. 여기에서 중간값이 가능한 값인지는 다음과 같이 구할 수 있다. 전체 공유기를 대상으로, 자신의 공유기의 위치에서 이전에 놓았던 공유기의 위치를 ..