최대공약수(GCD)4 [Programmers] N개의 최소공배수 https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 일반적으로 프로그래밍을 통해 최소공배수(least common multiplier, LCM)를 구하기 위해 사용하는 알고리즘은 두 개의 숫자에 대한 최소공배수를 구하는 알고리즘이다. 2 개 이상의 숫자들에 대한 최소공배수는 아래와 같이 pairwise 연산을 통해서 구할 수 있음을 이용하고자 하였다. $$LCM(a, b, c) = LCM( LCM( a, b ), c )$$ 한.. 2023. 8. 27. [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. 이전 1 다음
