728x90 소수 썸네일형 리스트형 [백준알고리즘] 1016번: 제곱 ㄴㄴ 수 -C++ [백준알고리즘] 1016번: 제곱 ㄴㄴ 수 -C++ 1016번: 제곱 ㄴㄴ 수 (acmicpc.net) 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 시간 복잡도 때문에 문제 푸는데 좀 골머리를 앓았다 ㅎㅎ; 문제를 푸는 데 있어서 시간 복잡도를 생각할 부분이 두 개 있었다고 생각한다. 실제 제출해서 통과한 시간은 다른 분들이 10ms 안팎인 것에 비해 144ms라는 결과가 나왔지만, 푸는 과정은 거의 비슷했지만, 다른 분들은 다 배열을 썼기 때문에 이것은 STL을 사용했기 때문에 발생한 추.. 더보기 [백준알고리즘] 4948번: 베르트랑 공준 -C++ [백준알고리즘] 4948번: 베르트랑 공준 -C++ 4948번: 베르트랑 공준 (acmicpc.net) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 소수 문제들은 다 비슷비슷한 것 같기도 하다. 에라토스테네스의 체를 사용해서 가능한 범위의 모든 수들의 소수 여부를 판단해주었다. 이후 입력되는 수에 대해서 에라토스테네스의 체를 이용해 소수 판정을 한다. 주의할 점은 입력으로 들어오는 \(n\)이 \(1\) 이상 \(123456\) 이하라는 것이고, 문제에서는 \(n\)보다 크고 \(2n\)보다 작거나.. 더보기 [백준알고리즘] 2023번: 신기한 소수 -Python [백준알고리즘] 2023번: 신기한 소수 -Python https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다. 수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 www.acmicpc.net 처음에는 에라토스테네스의 체를 이용해서 10**8만큼의 리스트를 만들었었다. 만.. 더보기 [백준알고리즘] 1644번: 소수의 연속합 -Python [백준알고리즘] 1644번: 소수의 연속합 -Python https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 연속합 형태의 문제와 똑같이 풀어주나 소수를 구하는 과정이 추가된다. 다른 .. 더보기 [백준알고리즘] 1963번: 소수 경로 -Python [백준알고리즘] 1963번: 소수 경로 -Python https://www.acmicpc.net/problem/1963 더보기 이전 1 다음