TIL 그리디, 에라토스테네스의 체

그리디

내가 생각한 그리디를 풀 때 주의해야 할 점은, 한 번의 반복 상황에서 각 그리디 조건 (ex: 5면 좋고 그 다음은 3이면 좋고)이 위에서 아래로 내려올 때, 한 번의 반복에서 차근차근 내려와야 한다는 점이었다. 흔히 우리는 가장 좋은 그리디 조건을 반복 없이 한 번에 처리하려고 실수 하지만 매 반복 내에서 가장 좋은 조건을 매번 추구해야 하는 지점을 명심하자.

에라토스테네스의 체

소수 판별 ==> 에라토스테네스의 체를 기억하자. a b = y라면 b a = y 다. 때문에 소수를 판별할 때 해당 수의 제곱근(좌와 우의 가장 가운데 값)을 기준으로 절반만 소수 판별을 한다면 전체를 판별한 것과 같다. 기억하자 소수, 제곱근, 에라토스테네스