알고리즘3 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다. n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다. -> 예를들어 12는 2*6 혹은 3*4 등으로 나타.. 2022. 2. 12. PS 입문 추천 (알고리즘 입문 추천) PS 입문 추천 PS; Problem Solving 해외 사이트들도 많지만, 국내에서 유명한 사이트로 그냥 입문하기 좋아보이는 개인 추천 루트 백준(boj) : 국내 사이트 중 가장 많은 문제수를 가지고 있지만, 기존엔 난이도에 따른 분류가 되어있지 않아서 문제를 잘 찾아 풀어야 했음. 현재는 solved.ac 라는 애드온을 유저중 한명이 만들면서 백준 사이트에도 정식적으로 채택되어 집단지성에 의한 난이도 분류가 되고있는 중이라 단점이 사라지고 있는 중. 사실상 국내 사이트 중 PS만 보면 최고라 생각합니다. 프로그래머스 : 요즘 많은 회사에서 코딩테스트 시 프로그래머스를 사용하는곳이 많아요. 사실상 문제 풀어보는 사이트보다는 코딩테스트 플랫폼이라고 볼 수 있음. 문제 자체는 매우 빈약한편이지만, 코테 .. 2021. 9. 22. PS 란? (알고리즘) Problem Solving 이란? 용어 사용, 용어 해석에 있어 작성자의 개인적인 생각이 포함되어 있습니다. The Feynman Algorithm Write down the problem Think hard Write down the solution Problem Solving(이하 PS)은 '문제 해결'이라는 단어 그대로 주어진 문제를 적절하게 해결 할 수 있는 방법을 찾아 해결하는 것을 뜻합니다. ! 프로그래밍으로 본다면 '원하는 결과를 적정한 시간과 메모리 이내에 처리하는 프로그램을 만드는 것'을 뜻합니다. 여기서 '적정한 시간'은 사람이 문제를 해결하는데 걸리는 시간이 아니라, 해당 프로그램이 입력을 받은 후 결과를 내놓기 전까지 걸린 시간을 의미합니다. 예시 정수 A와 B를 입력받아 A+B를.. 2021. 9. 22. 이전 1 다음
