# Foundation/기초수학
최대 공약수 알고리즘
이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ 두 수의 최대 공약수 구하기이번에는 두 숫자의 최대 공약수를 구하는 방법에 대해서 알아보자. 약수를 빠르게 찾는 방법은 이전 게시글을 참고하도록 하자. 먼저 쉽게 가보자. 지금보다 큰 공약수가 나올때마다 갱신하면 된다. 물론 성능은 보장할 수 없다. a = 1,000,000,000 이고 b = 876,543,210 일 때, 평균 2711 ms가 걸렸다. 반복문이 min(a, b)번 만큼 순회하므로, 시간 복잡도는 O( min(a, b) ) 이고, 큰 입력값이나 횟수나 들어온다면 더더욱 성능을 보장할 수 없다. 여기서 잔머리를 한번 굴려보자, 뒤에서 첫 공약수가 최대 공약수임을 눈치챘다면 공약수..
2018. 10. 22. 14:01
# 미사용
[백준 1011] Fly me to the Alpha Centauri 통찰노트
이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다. https://github.com/AeroCodeX/ Fly me to the Alpha Centauri문제를 대충 요약하면, 다음 조건을 갖는 최적화 문제와 같다. 워프거리는 위의 점화식을 만족해야 하고, 출발할때는 1로 출발해야 하며, 도착할때도 1로 도착해야 한다. 다만, 최소횟수로 워프해야 한다. 조건 (1, 2, 4)에 의해 속력은 출발점에서 우쪽으로 선형 증가하며, 조건 (1, 3, 4)에 의해 속력은 도착점에서 좌측으로 선형 증가하고, 조건 (1)에 의해 그래프는 연속이어야 한다. 즉, 위의 조건을 모두 만족하는 그래프는 다음과 같은 형태일 것 이다. 아래는 짝수 횟수로 최대 워프할 때의 그래프. 아래는 홀수 횟수로 최대 워프할 때의..
2018. 10. 22. 03:45
