컴공댕이 공부일지

유클리드 호제법이란? 두 양의 정수의 최대공약수를 구하는 알고리즘 중 하나로, 두 수가 반복적으로 서로 나누어지면서, 나머지를 구하며 최대공약수를 얻게 된다. 유클리드 호제법의 기본 원리 📝 A,B의 최대공약수 = A-B, B의 최대공약수 * GCD : 최대 공약수( Greatest Common Divisor ) 아하 ! 그러면 A, B의 최대공약수를 구하는 대신, A-B, B를 이용하면 빠르겠군 ! 그런데 A와 B의 차가 크다면 ...? 가령, 1024와 2라고 해보자. GCD (1024, 2) GCD (1022, 2) GCD (1020, 2) GCD (1018, 2) . . . GCD (2, 2) 이걸 어느 세월에....ㅜ 그래서 나온 또 다른 증명 ! 📝 A,B의 최대공약수 = A%B, B의 최대공..

백준 문제를 풀다가 정렬을 할 떄 내가 아는 버블 정렬이나, 삽입 정렬을 하게되면 시간 초과가 떠서 정렬 알고리즘에 대해 한 번 공부해보았다. [1] 퀵 정렬 피벗값을 임의로 정해, 이보다 작은 수들은 왼쪽, 큰 수는 오른쪽으로 나눈 후, 나눠진 파트 안에서 또 피벗을 정하고, 작은 수 큰 수 모음으로 나누기. 각각 낱개로 하나씩으로 나눠질때까지 이를 반복. ★참고영상 [자료구조 알고리즘] 퀵정렬(Quicksort)에 대해 알아보고 자바로 구현하기 https://www.youtube.com/watch?v=7BDzle2n47c 퀵 정렬 Java로 구현하기 public class Sort { public static void QS(int a[], int l, int r) { int pl=l; int pr=r..