2022-08-24 일자 계발 일지

저번 글은 짧아도 너무 짧은데… 이번걸 길게 쓰면 해결되는 문제겠지? 9월 3일날에 보는 필기시험을 내가 합격할 수 있을지는 모르겠다. 우선 운영체제, 메모리 관리, 프로세스 관리같이 외우는 거 우선 보고 있다. 알고리즘 / 프로그래밍 파트는 굳이 안 봐도 될 것 같다. 있는 자료를 죄다 습득한 다음에 다른 자료들도 있으면 찾아볼 것이다. 지금 따도 바로 산업기사를 얻을 수는 없지만, 산업기사 책은 있으니까 그걸로 보강하듯이 공부하면 앵간하면 필기는 합격할 것이다. 외출증 끊게 빨리 수험표 출력하고 갖다가 내야겠다.

어제는 좀 보람찬 하루였다. “제곱 ㄴㄴ수” 라는 1016(예는 백준이 생기자 마자 있던 문제일 듯 싶다.)번 문제를 완전히 내힘으로 풀었기 때문이다. 내가 이전에 문제를 풀면서 알게된 알고리즘을 가공해서 풀었는데, 1번에 AC를 받으니까 진짜 짜릿했다. 응용했던 문제는 “약수의 합”문제이다. 문제의 알고리즘을 검색을 통해 알게 되었지만 베껴서 넣는다고 해봤자 딱히 내 성장에 도움이 될 것 같지는 않아서 알고리즘 구조만 유심히 봐둔 것이 오히려 도움이 되었다.

제곱 ㄴㄴ 수를 풀기 위해서는
1. ceil(sqrt(max))이전의 모든 소수를 구한다. 에라토스테네스의 체를 이용하면 되고, 시간복잡도는 자세히 모르지만(아직도 어떻게 계산할지 잘 모르겠다!) 충분히 작으므로 이용할 수 있다.
2. 모든 소수를 vector에 우겨 넣고 전부 제곱을 한다. O(N)
3. 모든 소수의 제곱수에 대해서 min 부터 max까지의 수가 앞에서 말한 제곱수의 배수인지 확인한다. 확인한 사실을 배열에 넣어서 기록한다. max - min <= 1000000이므로 해당 bool 배열을 만들 수 있고, index = ceil(min / (제곱수)) 를 이용해 [index * (제곱수) - min] 번째 배열의 요소를 ture로 만드는 것을 모든 제곱수에 대해서 반복한다. (해당 알고리즘은 vector의 모든 요소 P에 대해서 O(P^2)인 것 처럼 보이지만 제곱수인데다 + max를 초과하는 배수부터는 연산을 하지 않는다는 것 때문에 그렇게 오래걸리지는 않는다고 한다. 이전에 원본 알고리즘을 소개했던 블로그에서는 PlogP라나…)
4. 앞의 배열에서 false인 모든 요소의 개수를 구해 출력한다. O(N)
N < 1000000 이고 당연히 P < 1000000 이기때문에 시간내에 구할 수 있다.

대강 이렇게 하면 된다. PS에 대한 것도 어쩌다보니 주저리주저리 이야기 했다. 이렇게 PS활동을 하다보니 느낀거지만 너무 스트릭에 신경쓰는 건 좋지 않은 것 같다. 이전에는 무조건 하루마다 문제를 푸는 것에 집중했는데, replit에 넣고 커밋을 매일 하자는 것에 집중하니까 사람이 여유로워진다. 못 풀어도 좋으니까 더 좋은 문제를 볼 수 있고, 만만한 문제를 다시 보는데 시간낭비하지는 않게 되는 듯 싶다. 오늘도 플5문제에 도전하러 가는데 이건 정 못풀면 다른 문제를 볼 수도 있을 듯 싶다. 재미있는 문제가 많았으면…