Java 코테 핵심이론 (그리디, 정수론)

06 그리디 알고리즘

6-1 그리디 알고리즘

그리디 알고리즘은 현재 상태에서 보는 선택지 중 best 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 즉, 부분의 best가 전체의 best이다. 하지만 항상 최적의 해를 보장하지는 않는다.

따라서 그리디 알고리즘을 적용할 수 있는 문제인지 아닌지를 파악하는 것이 중요하다.

 

<핵심 이론>

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적정설 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

---

07 정수론

7-1 소수 구하기

소수는 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다.

코딩 테스트에서 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제가 된다. 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체가 있다.

 

<에라토스테네스의 체>

1. 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성한다.
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다. (이 숫자는 소수)
3. 배열의 끝까지 2를 반복한 후 배열에서 남아 있는 모든 수를 출력합니다.

시간 복잡도는 일반적으로 O(Nlog(logN)) 이다. (생각보다 빠름)