에라토스테네스의 체

    [Java] 백준 1963 (소수 경로) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1963 (소수 경로) Gold 4

    Problem : https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net Approach 소수를 찾는 알고리즘과 BFS 개념으로 풀 수 있는 문제이다. 문제 풀이의 주요 로직은 다음과 같다. 먼저 간단하게 에라토스테네스의 체 개념을 이용하여 1 ~ 9999 사이의 숫자들 중 소수를 판별한다. 그리고 난 뒤 현재 숫자에서 숫자 하나만 변경하며 BFS를 수행한다. 숫자를 하나씩 바꾸는 부분을 구현하는게 꽤 까다로울 수 있다. String을 사용할까도 생각해봤지만,..

    [Java] 백준 1016 (제곱 ㄴㄴ 수) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1016 (제곱 ㄴㄴ 수) Gold 1

    Problem : https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net Approach 에라토스테네스의 체 라는 소수 판별 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다.(주관적 생각) 개인적으로 나는 에라토스테네스의 체라는 알고리즘을 사용한다는 것을 바로 생각했고, 구현하는 데에도 큰 어려움이 있지 않았지만 Gold 1이라는 난이도가 매겨져있었다. 조건을 좀 따져야 하긴 한다. 조건을 먼저 살펴보자. (자료형은 무조건 long ..

티스토리툴바