C++ 코딩 문제 풀이/백준113 [Baekjoon] 1934번: 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 관련 개념을 고등학교 1학년 과정에서 아마 배웠던 것으로 기억하는데, 요새 수학 교육과정은 어떻게 되는지 잘 모르겠다. 본인은 이 개념을 처음 배웠을 때 도대체 왜 이렇게 최대공약수를 구해야하는가에 대한 의문이 풀리지 않았었는데 대학교를 입학해서 수치해석 과목 시간에 이를 revisiting 하면서 이 알고리즘이 왜 필요한지를 깨달았던 기억이 있다. 나는 여태 살아오면서 수학을.. 2023. 5. 6. [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. 이전 1 ··· 15 16 17 18 19 다음
