코딩테스트 입문 - 소인수분해 ( while )

 

오늘은 어린이날!!!!

공휴일이지요

딱 월요일도 징검다리처럼 휴일 해줬으면..

왕 박수 짞짞인데

아쉽습니다.

 

원래 어린이날이 5월 5일이 아니라는 거 알고 계신가요?

원래는 언제게요~~!~!~

5월 1일이었다고 합니다!

 

하지만 5월 1일이 노동절이랑 겹치면서!

5월 5일로 바뀐 거라고 해요!

 

제가 초등학교 때,

독서퀴즈대회를 나갔었는데

 

저랑 나머지 한 명만 남았었는데

둘 다 계속 답을 맞혀서

1등 결정전 문제로 이 문제가 나왔는데

저는 몰랐어서 2등 했거든요.

 

그게 너무 아쉬워서..

제가 오래오래 기억하고 있답니다.ㅎ

 

몇 년 후에

같은 독서퀴즈대회에서

제 동생과 그 친구만 남았었는데

 1등 결정전에서 제 동생이 이기며

저의 복수를 해줬다는

비하인드 스토리까지 ㅎ 있답니다.

 

제 기억 한구석입니다.

 

오늘은 소인수분해 풀어볼게요!

---

 

최대공약수 gcd만 알고 있던 나

 

사실 음..

이문제를 어떻게 접근해야 할지 잘 몰라서 걱정했다.

2랑 곱해주고 맞으면 3, 다음 5, 다음 7..

 

이 규칙성 없는 애들을 어떻게 해주지?

하며

고민했다.

 

인지 씨에게 물어보니

그냥

모든 수를 나눠주면 된다고 했다.

언제까지?

 

매개변수로 주어지는 n이 1이 될 때까지

 

12의 경우 2 2 3 이기 때문에

while문을 써야 한다는 사실은 캐치했다.

 

나는 while문의 조건을 n>1로 잡고

if(n % i == 0) 이면

answer.push_back(i);

n /= i;

 

해주고..

아니면 i++ 해주는 방식으로 했다.

 

인지 씨는 그거도 괜찮고 더 간결하게 쓰는 법을 알려주었다.

 

while( n % i  == 0 )

이것이다.

 

즉 while의 조건문과 if문을 구별하지 말고

하나로 합치라는 것이다.

그럼 else도 안 써도 된다는 것!

 

 

하지만 여기서 가장 중요한 것은

이렇게 해주면,

2가 두 번 들어간다. 하지만 답에서는 중복이 허용 안된다.

 

그래서!! 우리는

내가 풀었던 방식과 인지 씨의 방법을 합쳐야 한다.

 

if ( n % i == 0 ) 이면

push(i) 해주고 이 if문 안에다가

while ( n % i == 0 )를 선언하고

그 안에서는 그냥 n /= i만 해주는 것이다.

 

그럼 답이 나온다!!

 

더 빠르게 푸는 방법은

첫번째 for문에서 i*i <=n으로 조건을 두는 것이다.

 

이러면 장점이 매우 매우 스피드하게 계산하지만

소수의 하나가 남게 된다.

 

쉽게 14라고 하면

2 로나누면 7인데

그다음 i가 3이 되는데 7%3은 나머지가 나오니까 while문에 들어가지 못해서

push가 안된다.

 

그뜻은 n이 1까지 나눠지지 않은거고

그것은 매우 큰 소수가 껴있다는 뜻

그래서!

 

만약 for문이 다 끝났는데도

if(n>1) 1보다 크다면 그것은 소수니까

push_back 해줘야한다!

 

 

i*i로 안해줬다면

if ( n > 1) 도 안해도 된다!

---

 

생각의 발상이 중요하다.

알고리즘만 중요한 게 아니다.

잊지 말자!!!

 

 

어려웠다...

키키

그리고

나도 아직 취준생이니까!!

으른 아니니까!!

 

엄마한테 선물사 달라고 해야겠다.

히히