1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 해당 문제는 주어진 숫자가 소수인지 판별하는 문제입니다. 낮은 난이도이기에 어떠한 방식으로 풀어도 통과가 됩니다. 대표적인 3가지 방법으로 풀어보겠습니다. 1. 일반적인 방법 가장 일반적인 방법으론 2부터 1씩 늘려가며 해당 숫자가 나누어 떨어지는지 보는 방법입니다. // Java static boolean isPrime(int number) { if (number
15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된 www.acmicpc.net 해당 문제는 제곱수를 구하는 문제입니다. 이 사실을 알면 굉장히 쉽게 풀 수 있습니다. 다만, 저는 몰랐구요 ㅎ... 정답을 찾아놓고 최적화 하는 것을 좋아해서 맨 처음에 그냥 완전탐색으로 for문 두 번 돌렸습니다. 작은 숫자들은 무난하게 되더군요. 다만 제출했더니 바로 메모리가 터집니다 ㅎㅎ.. 사실 예상했던 부분인지라 좀 더 살펴보았습니다. 보다보니 규칙이 보이더군요. 3, 5, 7, 9, 11 ~ 이런 식으로 숫자가 2씩 증가하면서 백기의 숫자가..
1090번: 체커 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 www.acmicpc.net 이번 문제는 체커입니다. 여러 개의 체커들의 좌표가 주어지고, 해당 체커들이 모일 수 있는 가장 적은 비용을 구하는 문제입니다. 다만, 여러 개의 체커들이 모두 모인 경우만 구하는 것이 아니라 1개 모였을 때, 2개 모였을 때, 3개 ~, 4개 ~ 이런 식으로 구해야 합니다. 해당 문제는 완전탐색으로 해결할 수 있습니다. // 슈도 코드 // 1. 각 체커들이 모일 좌표를 선정한다. // 2. 선정한 좌표와 각 체커들의 거리를 계산하여 저장한다. (i..
2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 이번 문제는 숫자 야구입니다. 주어진 힌트를 통해 가능한 숫자들의 개수를 출력하는 문제입니다. 해당 문제도 완전탐색을 이용하여 풀어보도록 하겠습니다. // 슈도 코드 (Java 기준) // 1. 주어진 입력을 받는다 int[][] hint; // hint에 각 회차별 힌트들을 저장한다. int count = 0; // 가능한 숫자의 횟수를 받을 변수 // 2. 1 ~ 999 중 각 자릿수가 서로 다른 경우 hint와 비교한다. // 3. 모든 hint가 통과될 ..
19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 해당 문제는 이원연립방정식의 해를 구하는 문제입니다. 해당 문제도 완전탐색 알고리즘을 활용하면 손쉽게 풀 수 있습니다. 물론, 직접 방정식을 푸는 식을 사용한다면 더욱 최적화를 할 수 있습니다. 두 가지 방법 모두 사용해 보겠습니다. # Python : 일반적인 완전탐색을 활용한 방법입니다 def solution(a: int, b: int, c: int, d:..
14568번: 2017 연세대학교 프로그래밍 경시대회 규칙에 맞게 사탕을 분배하는 경우의 수를 출력한다. 택희, 영훈이, 남규가 받은 사탕의 수를 각각 A, B, C개라고 할 때, 서로 다른 (A, B, C) 순서쌍의 수를 세면 된다. 만일 규칙에 맞게 사탕을 분 www.acmicpc.net 해당 문제는 규칙에 맞게 사탕을 나눌 수 있는 경우의 수를 계산하는 문제입니다. 문제 조건을 보면 시간과 메모리가 충분하므로 완전탐색으로 구현하면 손쉽게 풀 수 있습니다. # Python N = int(input()) count = 0 for A in range(2, N - 1, 2): for B in range(1, N - A): C = N - A - B if C - B >= 2: count += 1 print(c..
1816번: 암호 키 현대 사회에서 통용되고 있는 많은 종류의 암호 시스템에서는, 매우 큰 소수의 곱으로 만들어진 수를 암호 키로 이용하는 경우가 많다. 현실적으로 매우 큰 수를 빠른 시간 내에 소인수분해하는 www.acmicpc.net 백준 - 1816번 문제입니다. 해당 문제는 숫자가 주어지고 해당 숫자가 1,000,000 보다 큰 소인수로 이루어져 있다면 "YES"를 출력하고 아니면 "NO"를 출력하는 문제입니다. 다양한 방법으로 최적화가 가능하지만, 해당 문제의도에 맞게 가능한 모든 경우의 수를 넣는 방식인 완전탐색으로 풀어보겠습니다. 시간과 메모리가 충분하다면, 그 어떤 문제도 해결할 수 있는 아주 강력한 방법입니다. # Python for _ in range(int(input())): num ..
