[2023-02-21]

Start

이전 포스팅인 [2023-02-15] 마지막에 이런 말을 하면서 사라졌는데

코딜리티 안에서는..어차피 도망쳐봤자 지옥밖에 없어서 해당 문제를 부수고 넘어갈 예정이다.

 

 

CommonPrimeDivisors 문제

정답 코드

 

1. 유클리드 호제법을 이용해서 A와 B의 최대공약수를 구한다.

 

2. A와 1에서 구한 최대공약수의 최대공약수를 구한다.

 

3. 2에서 구한 최대공약수가 존재한다면 A를 2의 최대공약수로 나눠 몫을 구한다.

 

4. 몫이 1에 도달한 경우 최대공약수에 나타난 소수 외 다른 prime divisor는 존재하지 않는다는 의미이다.

 

5. 최대공약수가 1인 경우 최대공약수가 없다는 의미이다. -> 추가 소수가 존재한다는 의미이다.

 

2~5 과정을 반복한다.

 

A와 B 모두 몫이 1이 되면 1에서의 최대공약수 외에는 없는 것이다.

 

A = 75, B = 15

A = 30, B = 10

똑바로 이해를 못했던 것 같다.

 

A나 B를 나누는 최대공약수는 아래와 같이 최대공약수로 나눈 몫으로 최대공약수를 구한 후 몫을 구하도록 변경해야한다.

아래는 위의 로직으로 풀었지만 계속 틀리던 코드였는데, 최대공약수로 나눈 몫으로 구한 최대공약수로 나누는 것이 아닌 최초의 A와 B 최대공약수여서 틀렸다.

시간복잡도는 아래와 같이 나왔다.

 

---

FibFrog 문제

다 맞았을 거란 생각을 하는건 아니지만..뭔가..런타임 에러와 타임아웃으로 뒤범벅 되어있는 것으로 보아..시간복잡도를 더 줄여야겠다는 생각이 든다..

 

현재 점프 중인데 이미 점프 완료 횟수보다 점프 수가 많을 경우 연산을 마치도록 조건 추가했더니 위와 같이 50%로 바뀌었다.

 

현재 결국 2중 for문으로 돌아가고 있어서 시간복잡도가 너무 큰 것 같다..

for문의 시작을 뒤부터 했더니 아래와 같이 정확도는 모두 맞았다. 결국 아까부터 로직 자체는 옳았지만 너무 오래 걸리는 로직이었던 것이다.