재곱 ㄴㄴ수 (1) 썸네일형 리스트형 [백준] 1016번 : 제곱 ㄴㄴ수 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 해당 문제는 모든 경우의 수를 set 자료구조로 만들어서 전체에서 빼는 로직을 세웠으나, 메모리 복잡도에서 에러 판정을 받았다. 문제를 오랫동안 생각해보았지만 생각나지 않아서 정답을 찾아 보았다. 에라토스테네스의 체의 성질을 이용하여 문제를 해결하였다. visited 리스트를 0혹은1 상태로 저장하여 메모리 최적화를 하였습니다. min = 1, max = 1000 일때, 예를들어 .. 이전 1 다음