분류 전체보기166 [Baekjoon] 1010번: 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 수학적인 배경 지식을 어느정도 요구하는 문제였던 것 같다. 고등학생 때 경우의 수를 구하는 문제를 정말 극도로 싫어했었는데 문제를 해결하다보니 그 때의 생각이 물씬 났다. ㅎㅎ;; 이번 문제를 해결하는 것 자체는 사실 수리논리적으로 그렇게 어려운 일은 아니지만(반박 시, 당신의 말이 옳습니다) 초보 프로그래머로서는 프로그래밍적으로는 생각해 볼 여지가 꽤 많은, 좋은 문제라고 생각한다. 문제 해결 .. 2023. 5. 6. [Baekjoon] 2581번: 소수 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 문제 해결 과정 착안 어떤 하나의 수 \(n\)이 소수(prime number)인지 아닌지를 판별하기 위해서는 \(1, 2, ..., k (k ≤ \sqrt{n}\)을 만족하는 최대의 자연수\()\)로 모두 나누어서 확인할 수 있지만, 1 이상 \(n\) 이하의 자연수 중에서 소수인 것을 모두 찾는 과정에서 위와 같이 구하는 것은 계산적으로 유리하지 않다. 따라서, 에라토스테네스의 체(Sieve of Era.. 2023. 5. 6. [Baekjoon] 9506번: 약수들의 합 https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 문제 해결 과정 착안 주어진 수 \(n\)의 약수를 구하기 위해서는 \(i = 1\)부터 최대 \(i = \sqrt{n}\) 까지의 자연수로 나누어보면 모든 약수를 구할 수 있다(\(a\)가 \(n\)의 약수이면, 반드시 \(n/a\)도 \(n\)의 약수이기 때문이다). 이를 이용해 약수를 구하는 과정의 시간 복잡도를 \(O(\sqrt{n})\)으로 단축시킨다. 구현 위와 같이 문제를 해결.. 2023. 5. 6. [Baekjoon] 5086번: 배수와 약수 https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 문제 해결 과정 착안 두 수를 서로 나눈 나머지가 0인지 확인한다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; int main() { vector A, B; unsigned short a = 1, b = 1; while (a != 0 || b != 0) { cin >> a >> b; A.push_back(a); B.push_back(b.. 2023. 5. 6. [Baekjoon] 1193번: 분수찾기 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 직전의 포스트와 마찬가지로, 이번 문제도 규칙성을 찾으면 쉽게 해결 가능한 문제이다. 본인은 처음 이 문제를 풀 때 너무 단순하게 생각해서 실제로 지그재그로 움직여서 구하는 코드를 짰었는데, 실행 시간이 생각보다 길게 나와서 다른 사람의 코드를 분석해보다가 깨달음을 얻고 눈물을 흘려버리고 말았다. 문제 해결 과정 착안 실제로 지그재그로 움직여서 구한다(분자 또는 분모가 1이 될 때 방향을 전환하는 원리). 아래와 같이 분수들을 그룹화 하고, 각 그룹의 규칙성을 찾아 해결한다(아래 그림 참고). 그림과 같이 분수들을 묶으면, \(.. 2023. 5. 6. [Baekjoon] 2292번: 벌집 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 이번 문제를 보고서는 규칙을 금방 찾아낸 사람에게는 아주 쉬운 문제이지만 규칙을 잘 발견하지 못한 사람에게는 엄청나게 어려운 문제가 될 수도 있을 것 같다는 생각이 들었다(물론 전혀 아닐 수도 있다 ㅎㅎ 반박 시에는 항상 제가 죄송합니다). 문제 해결 과정 착안 아래의 그림과 같이 구획을 나누어 규칙성에 따라 문제를 해결한다. 벌집의 중앙 1에서 \(N\)번 방까지 최소 개수의 방을 지나서 갈 때 지나는 .. 2023. 5. 6. 이전 1 ··· 24 25 26 27 28 다음
