잡소리
일을 때려치고 독학을 시작한지 어느덧 4개월이 되었다.
이것 저것 여러가지를 공부하다보니 머릿속이 중구난방이 되어버린 상황이다.
고등학생때 C만 해봤는데 자바도 해야되고 DB도 해야되고 STS도 해야되고 열심히 책 보면서
실습을 조져봤지만 항상 조져지는건 나였다고한다. ▶◀R.I.P.......
잠시 머리를 식힐 겸 이번주는 몇달동안 미뤄뒀던 백준 골드달기 프로젝트를 진행해보기러 했다.
시작 일시 : 2022/4/11
시작 당시 티어 : S1 , 660점 (G5까지 -140점)
- 대뜸 이틀전 얘기를 들고와서 글을 쓰고 있는 것은 신나게 코딩을 하다가 막혔다는 이야기다.
유클리드씨와의 만남
어떤 분야를 풀며 머리를 식혀나갈까 고민하던 중, '#유클리드 호제법' 알고리즘 태그를 만났다.
유클리드 대센빠이 오랜만에 봽는다.
잠시 유클리드 센빠이의 용안을 뵙고 가도록하자.
꺼무위키 피셜 인류 최초의 알고리즘.
우리는 이 알고리즘의 시초부터 시작해야했던 것이다.
유클리드 호제법은 이렇게 적혀있다.
int a,b(a > b > 0)에 대해서 a = b * q + r일 경우, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이를 좀 더 깐지나고 있어보이게 쓰면 GCD(a,b) == GCD(b,r) 이라고 보면 된다.
위의 식에서 r == 0이면 a와 b의 최대 공약수는 b가 되버린다! 굉장히 엄청나는 상황이다!
그래서 그걸 어따 쓰게 **아
아 이거를 C에서 코드로 작성하면 더욱 더 굉장히 몬가가 몬가 엄청난 상황이 탄생해 버린다.
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}이 4줄짜리 코드로 5문제 뚝딱 해먹었다. 국밥이 따로 없잖아.....
이 함수의 리턴값은 두 수의 최대공약수가 나와버린다....
잠시 수치플이지만 3달 전, 42서울에 들어가기 전 혼자 풀 때 백준 2609번 (최대공약수, 최소공배수)을
풀었던 흔적이 남아 있어서 코드를 긁어와본다.
#include<stdio.h>
int main()
{
int a, b;
int i;
int k=0;
int mx = 1;
scanf("%d %d", &a, &b);
if (a >= b)
k = a / 2;
if (b >= a)
k = b / 2;
for (i = 1;i <= k;i++)
if (a % i == 0 && b % i == 0)
mx = i;
if (a == b)
printf("%d\n%d", a, b);
else
printf("%d\n%d", mx,(a*b)/mx);
return 0;
}당시 풀이 방법을 찾아보니 나름 머리를 쓴 것이 a,b중 큰 값의 절반 지점까지 반복문을 돌리며
두 수의 최대 공약수를 찾고, 뭐 암튼 자기딴엔 무지성으로 머리를 좀 굴린 것 같다.
뭐 아무튼 돌아는가서 정답을 맞췄으니 된거 아니냐!
(대가리를 돌리랬더니 정말 대가리를 돌려서 해결해버린 케이스.다.)
방금 글을 작성하며 다시 작성한 코드는 이러하다.
#include<stdio.h>
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n%d", gcd(a, b), a * b / gcd(a, b));
return 0;
}코이츠wwwwwwww 3달 전의 나란 녀석의 코드보다 메인 함수를 1/3으로 줄여버린wwwwwwwww
3달 전의 나 녀석 반성하라구wwwwwwwwwwwwwww
아무튼 그렇다.... 그렇게 유클리드 호제법으로 실버 언저리 문제들을 풀어봐서 행복한 나머지 이렇게 글을 써봤습니다.
마....마지막으로......
유클리드 센세..... 호제는 필요 없고, 호재는 언제 오나요....
