코딩스토리

확장 유클리드 호제법 기말 기간이라 밀렸던 문제 해결 기법 강의를 듣고 있는데 확장 유클리드 호제법이 나왔다. 유클리드 호제법을 알고 있었고 가끔씩은 백준 푸는 데 사용했었기 때문에 어렵지 않게 이해하고 넘어가야지 했는데 뭐지? 이해가 안가네? 옛날 같았으면 그냥 에라이 모르겠다 하고 넘어갔을 텐데 뭔가 시험에 나올 것 같다는 강렬한 촉이 와서 정리해봤다. (개인적인 이해를 바탕으로 작성했기 때문에 완벽하진 않아요!) 확장 유클리드 호제법을 이해하려면 먼저 유클리드 호제법을 이해해야 한다. 일명 GCD 알고리즘이라고도 불리며 "수학"이란 카테고리에서는 가장 처음 접하는 알고리즘 다운 알고리즘이다. 자세하게 설명하는 건 생략하고 요약하자면 결국 유클리드 호제법을 간단히 말하면 "log 시간안에 최대공약수를..