sh1mj1_log

확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것입니다. 제대로 이것을 이해하려면 수학적인 증명이 필요하지만 우리는 관련 알고리즘 구현만 알아봅시다. 확장 유클리드 호제법의 원리 해를 구하고자 하는 방정식은 ax + by = c 입니다. (a, b, c, x, y 는 정수) 위 방정식은 c % gcd(a,b) = 0 인 경우에만 정수해를 가집니다. 즉, c 가 a 와 b 의 최대 공약수의 배수인 경우에만 정수해를 가집니다. ax + by = c 가 정수해를 갖게 하는 c 의 최소값이 gcd(a,b) 라는 것을 의미합니다. 5x + 9y = 2 일 때 이 식을 만족하는 정수 x, y 을 구하는 과정을 봅시다. 1. ..

이전 글 https://sh1mj1-log.tistory.com/136 에서 계속됩니다. 백준 1033 칵테일 https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 1. 문제 분석 문제에서는 N-1 개의 비율로 N 개의 재료와 관련된 전체 비율을 알아낼 수 있다고 합니다. 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있습니다. 그래서 임의의 노드에서 DFS 혹은 BFS 를 진행하면서 정답을 찾으면 됩니다. DFS 과정에서 유클리드 ..

유클리드 호제법 유클리드 호제법(Euclidean-algorithm) 은 두 수의 최대 공약수를 구하는 알고리즘입니다. 일반적으로 최대공약수를 구할 때는 소인수분해를 이용하지만 유클리드 호제법을 사용하면 더 간단하게 가능합니다. 유클리드 호제법 원리 먼저 최대 공약수를 구하는 데 사용하는 핵심 연산인 MOD 을 알아야 합니다. 연산 기능 예 MOD 두 값을 나눈 나머지를 구하는 연산 10 MOD 4 = 2 // 10 % 4 = 2 1. 큰 수를 작은 수로 나누는 MOD 연산 수행. 2. 앞 단계에서의 작은 수와 MOD 연산 결과 (나머지값)으로 MOD 연산 수행. 3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택. 270 과 192 의 최대공약수를 유클리드 호제법으로 구하는 그림을 통해 구체..