유클리드호제법

[c++] 백준 14476 (최대공약수 하나빼기, 누적합, 최대공약수, 유클리드 호제법)

최대공약수를 구하는 함수는 수는 유클리드 호제법을 이용하여 정의할 수 있다. gcd(36, 8) => gcd(8, 36%8) ....gcd(36,8) => gcd(8,4) => gcd(4,0) => 최대공약수는 4가 된다. int gcd(int a, int b){ while(b != 0){ int r = a % b; a = b; b = r; } return b; } 이를 활용하여 누적합을 적용해 본다. number 8 12 24 36 48 L to R 8 4 4 4 4 R to L 4 12 12 12 48 각 L to R과 R to L을 구한 이유는 k수를 제외하고 최대공약수를 구할때 O(n) 시간복잡도로 구하기 위해서이다. 즉, k=8 , 최대공약수 = RL[1] k=12, 최대공약수 = gcd(LR[..

백준 2981 풀이 (검문, 유클리드 호제법, 약수 구하기)

이 문제는 정말 나의 탁월한 운빨로 풀게된 문제이다. 문제를 읽게 되면 그렇게 어려워 보이지 않는다. 읽고나서 바로 생각나는 것은 2부터 나누기 시작해서 다 나누어 떨어지면 되는거 아닌가? 하는 생각이 든다. 나도 당연히 그렇게 풀어볼까 하다가 조금이라도 연산을 줄이고자 나머지를 기준으로 값을 나누어 보기 시작했다. 물론 잘못된 방법이었다. 바로 풀릴리가 없지ㅋㅋㅋㅋ 그래서 고민하다가 도달한 결론은 노가다로 푸는게 아니고 무언가 규칙이 있을것이란 생각이었다. 테스트 케이스로는 6,34,38을 준다. 그래서 이걸로 값을 바꿔보기도 하다가 1씩 증가시켜보았다. 7, 35, 39 신기한것은 이렇게 1이 증가하여 전부 홀수가 되었음에도 같은 나머지를 만들기 위해서 2, 4가 필요한 것이었다. 그래서 각 값들의 ..

백준 1934 풀이 (최소공배수, 유클리드 호제법)

저번 2609문제에서 최대공약수와 최소공배수를 구했다. 이번에는 최소 공배수만 구하는 문제이기 때문에 저번에 사용했던 코드를 재활용해주면 아주 쉽게 구할 수 있다. 최소 공배수를 노가다로 구하게 되면 불필요한 연산이 너무 많아진다. 따라서 최대 공약수를 유클리드 호제법으로 구하고 이후에 최소 공배수를 구하는 방식이 효율적이다. 따라서 저번에 활용한 코드를 재활용하는 것이다. 그냥 함수로 묶어 주기만 하면 된다. n = int(input()) def find(tmp): if tmp[0] < tmp[1]: t = tmp[0] tmp[0] = tmp[1] tmp[1] = t a = tmp[0] b = tmp[1] # get 공약수 yak = 0 while 1: c = tmp[0] % tmp[1] tmp[0] ..

백준 2609 풀이 (최대공약수와 최소공배수, 유클리드 호제법)

쉬운문제였다. 물론 한번 틀려서 유클리드 호제법 공부하고 왔다. 처음에는 a와 b중에 작은 수에서 1씩 빼면서 둘다 나누어 떨어지는지 확인하는 방식을 통해 최대 공약수를 구하려고 했다. 물론 그 방법이 틀렸다고는 할 수 없지만, 문제는 시간도 오래걸리고 좋은 방법 같지 않았다. 그래서 찾아보니 유클리드 호제법이라는 엄청난 방법이 있었다. (a,b)가 존재할때 a%b를 하여 나머지를 계속해서 나누어주는 방법이다. (24, 18) => 24 % 18 = 6 (18, 6) => 18 % 6 = 0 (6, 0) => 최대 공약수는 6 이러한 방식으로 몇개의 연산으로 최대 공약수를 찾을 수 있는 것이다. 기존보다 연산의 횟수가 획기적으로 줄어들게 된다. 요 방식으로 최대 공약수를 찾으면 최소 공배수는 쉬워진다. ..