C++ 코딩 문제 풀이151 [Baekjoon] 2485번: 가로수 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 최대공약수의 개념을 활용하는 문제인데, 단순히 최대공약수를 구하라고 한다면 모두 빠르게 프로그래밍으로 구현할 수 있지만 이렇게 서술형 문제로 나오면 왠지 모르게 어떤 방법으로 풀어야할 지 헷갈리는 것 같다. 문제 해결 과정 착안 가로수의 간격이 등간격이 되도록 새로운 가로수를 심는 과정은 주어진 간격을 등분하는 것과 같으므로, 각 간격들 사이의 공약수(common divisor)만큼 등분하.. 2023. 5. 6. [Baekjoon] 1735번: 분수 합 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 문제 해결 과정 착안 분모가 다른 두 분수 \(A, B\)의 계산을 위해 두 수를 통분(reduction to common denominator, 영어로는 별도로 통분을 나타내는 하나의 용어가 존재하지 않는다)하여 계산하고, 기약분수(irreducible fraction)로 나타내기 위해 최종 계산된 분자와 분모 사이의 최대공약수(greatest common divisor, GCD)를 구해 분자와 분모를 약분(reduction of a fractio.. 2023. 5. 6. [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. 이전 1 ··· 21 22 23 24 25 26 다음
