[Do it!_Algorithm with Python] 4.정수론

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python'

 

4장은 정수론이다

이 부분은 손으로 직접 써보고 풀어보는 것이 더 효과적인 것 같아서 필기로 대체한다.

글씨체를 좀 예쁘게 쓰고 싶은데 어렵다하핫

 

 

1) 소수 구하기

우리가 잘 아는 '소수'를 구하는 알고리즘이다.

'소수'란, 약수를 1과 자기자신 만 갖는 수를 말한다.

이를 판별하는 방법으로 가장 대표적인 것이 '에라토스테네스의 체' 이다.

구하고자 하는 범위만큼 배열을 생성한 후, 각 숫자의 배수를 지워가다보면 남은 수는 소수들 뿐이다.

이 지우는 과정때문에 시간 복잡도는  O(Nlog(logN))을 갖는다.

 

 

2) 오일러 피

오일러피 함수는 1~N까지 수에서 N과 서로소인 자연수의 개수를 말한다.

P[6] = 2의 뜻은, 6과 서로소인 개수가 1부터 6에서 2개라는 뜻이다 (1과 5)

이 알고리즘은 앞의 '소수구하기'와 비슷한데, '소수 구하기'에서는 자신의 배수를 지워갔다면

오일러피에서는 대신 P[i] = P[i] - P[i]/2 를 계산한 값으로 업데이트 해준다.

 

 

 

3) 유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘이다.

우리가 고등과정에서 배웠던 최대공약수 구하는 법은 소수들의 곱으로 표현한 뒤, 겹치는 부분을 찾는 것이다.

이와 달리 알고리즘으로 구하는 방법에서 핵심은 MOD 연산이다.

MOD 연산은 코딩에서 % 기호 연산과 동일하며, 두 수를 나눴을 때의 나머지 값을 말한다.

 

이 연산은 동일한 연산을 반복하는 특징을 가지므로 코드로 구현할 때는 '재귀함수'를 사용하게 된다.