Algorithm2 [알고리즘] 소수 구하기 (Java) 소수 구하는 문제는 코테 풀 때 종종 나오는 데 풀 때마다 까먹어서 정리해보려고 한다! 소수 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 자세히 뜯어서 살펴보면 조건이 2가지 이다. 조건1) 1보다 큰 자연수라는 것 조건2) 1과 자기 자신만을 약수로 가진다는 것 1보다 큰 자연수라는 것은 2부터 시작하는 자연수를 의미한다. 그래서 즉 0과 1은 제외하게 된다. 2, 3, 11, 17 과 같은 숫자들이 소수이고, 8, 12와 같이 1과 자기자신 외의 약수가 있는 숫자들은 소수가 아닌 합성수이다. 소수 판별 알고리즘 N보다 작은 자연수들로 나눠보기 가장 간단한 방법이다! 소수는 1과 자기 자신만을 약수로 가지는 수이기 때문에 자기 자신보다 작은 자연수들(1은 제외)로 나눠보고 나.. 2023. 9. 22. 그리디 & 구현 💬 해당 포스팅은 나동빈님의 (이코테 2021 강의 몰아보기) 2. 그리디 & 구현 강의를 듣고 요약한 글입니다. ✔ 그리디 알고리즘(Greedy) 이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 그리디 알고리즘으로 풀 때는 중요한 점이 있는데, 해당 방법의 정당성을 분석하는 것이다. 단순히 가장 좋아 보이는 것만을 반복적으로 선택해도 최적의 해를 구할 수 있는 지 검토해야 한다는 것이다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많지만, 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다. ▼ 예) 거스름 돈 문제 더보기 동전으로 거스름 돈을 주려고 하는데 500원, 100원, 50.. 2023. 5. 26. 이전 1 다음
