728x90
반응형

CS(Computer Science)/알고리즘 2

삼성SDS 2023 동계(상반기) 대학생 알고리즘 특강 후기

삼성SDS에서는 매 방학 시즌에 대학생들을 대상으로 알고리즘 특강을 무료로 진행한다. 요즘에는 컴퓨터공학 전공뿐 아니라 전자, 기계분야도 코딩테스트가 거의 필수가 된 시대이다. 코딩테스트 하나만으로 그 사람의 사고에 대해 많은 것이 설명 가능하고, 또한 채용에 많은 돈을 들이는 기업의 입장에서 본다면 일종의 미달 기준선이 되기에 매우 좋은 시험이기 때문에 필수가 됐다고 생각한다. 이 알고리즘 특강은 알고리즘을 제대로 배워본 적이 없는 대학생이나 기존에 알고리즘을 공부했지만 플레티넘 수준의 문제는 접근하지 못해 봐서 더 깊게 알고리즘을 배우고 싶은 취준생 입장에서 매우 좋은 기회라고 생각한다. 나는 삼성SDS처럼 업계에서 좋은 입지를 가지고 있는 회사에서 이런 좋은 기회를 주는데 마다할 이유가 없다고 생각..

밀러 - 라빈 소수 판별법 (Miller - Rabin primality test)

컴퓨터 공학에 입문한 뒤 대부분 처음으로 배우는 소수 판별 알고리즘은 에라토스테네스의 체 알고리즘이다. 에라토스테네스의 체는 소수를 판별하고 싶은 범위 안의 소수인 수의 모든 배수를 차례로 제거해서 원하는 수의 범위에서 어떤 수가 소수인지 판별 할 수 있는 알고리즘이다. 이는 꽤나 직관적인 알고리즘으로, 알고리즘이 작동하는 방식을 보면 소수라는 체로 소수가 아닌 수를 거르는 것처럼 보인다. 따라서 알고리즘의 고안자인 에라토스테네스의 이름과 체를 붙여서 에라토스테네스의 체 라는 이름을 가지고 있다. 에라토스테네스의 체는 O(N^2) 시간복잡도를 가진 알고리즘이다. 그런데 놀랍게도 에라토스테네스의 체를 가르쳐 준 후, 컴퓨터 공학 학부를 졸업할 때까지 일반적인 학부 과정상에서 소수 판별에 대한 더 효율적인 ..

728x90
반응형