modern cpp challenge 책의 문제들을 푸는 과정을 작성해놓으려 한다.
1. 문제
2. 풀이(1)
2.1. I/O
2.2. 연산
2.3. 코드
3. gcd 구현 방법
3.1. I/O 타입
3.2. 연산 방법
3.2.1. 반복문으로 구현한 유클리드 호제법
3.2.2. Binary GCD
4. 후기
1. 문제
최대공약수 프로그램 구현하기
양의 정수 두 개가 주어졌을 때, 두 수의 최대공약수를 계산하고 출력하는 프로그램을 작성하라.
2. 풀이(1)
필요한 코드 구조는 아래와 같다.
양의 정수 2개 입력값 받는 부분 + 최대공약수 연산하는 부분 + 최대공약수 출력하는 부분
전 문제와 마찬가지로 main함수에서 I/O를 해결하고 최대공약수 연산 부분은 따로 함수로 처리하기로 했다.
2.1. I/O
사용자가 입력한 양의 정수 상한을 가장 크게 설정하기 위해 입력값, 출력값을 unsigned long long으로 정했다.
2.2. 연산
numeric 라이브러리의 gcd 함수를 사용하기로 하였다. gcd 함수는 템플릿이어서 모든 정수 타입으로 사용 가능하고, 최신 컴파일러 환경이면 추가적인 타입 캐스팅이 필요없기 때문이다.
2.3. 코드
처음에 작성한 코드는 아래와 같다.
#include<iostream>
#include<numeric>
using namespace std;
unsigned long long GetGcd(unsigned long long n1, unsigned long long n2)
{
return gcd(n1, n2);
}
int main()
{
unsigned long long n1, n2;
cin >> n1 >> n2;
cout << GetGcd(n1, n2);
return 0;
}시간복잡도는 O(log n)이고, 저번 문제와 다르게 cpp 표준 라이브러리 함수가 인식할 수 있도록 공식 표준 타입으로 선언했다.
3. gcd 구현 방법
코드 작성 후 2.2. 단계에서 고민이 생겼다.
보통 cpp로 gcd 구현할 때 std::gcd를 쓰는데 다른 방법 중에 좋은 방법은 없나?
3.1. I/O
연산 타입은 양의 정수 상한이 가장 큰 unsigned long long을 그대로 사용한다.
3.2. 연산 방법
보통 cpp17 이상의 std::gcd를 주로 사용하는데, 해당 함수 외에 다른 방법으로 간단하게 gcd를 구현해보기로 했다.
3.2.1. 반복문으로 구현한 유클리드 호제법
unsigned long long gcd(unsigned long long n1, unsigned long long n2) {
while(n2 != 0) {
unsigned long long r = n1 % n2;
n1 = n2;
n2 = r;
}
return n1;
}
재귀보다 스택 부담이 적어서 반복문으로 구현했다.
시간복잡도는 O(log min(n1, n2)이다.
나눗셈 연산 횟수가 많을수록 코스트가 증가한다.
3.2.2. Binary GCD
unsigned long long binary_gcd(unsigned long long n1, unsigned long long n2) {
if(n1 == 0) return n2;
if(n2 == 0) return n1;
int shift = __builtin_ctzll(n1 | n2);
n1 >>= __builtin_ctzll(n2);
while(n1) {
n2 >>= __builtin_ctzll(n2);
if(n1 > n2) swap(n1, n2);
n2 -= n1;
}
return n1 << shift;
}
GCC, Clang에서는 __ builtin_ctzll이 있어서 2로 나누는 횟수 세기와 비트 쉬프트 반복을 더 용이하게 할 수 있다.
나눗셈 대신 비트 연산을 이용했고, 두 수가 짝수인지 여부에 따라 처리 방식이 달라진다.
(두 수 모두 짝수 : 2로 나누기, 하나만 짝수 : 짝수만 2로 나누기, 둘 다 홀수 : 큰 수-작은 수 이후 다시 진행)
시간복잡도는 O(log min(n1, n2)이지만, 비트 연산과 뺄셈 위주여서 나눗셈이 느린 구형 CPU에서 효과적이다.
(나눗셈 대신 비트 연산과 덧셈/뺄셈 위주여서 나눗셈 기반 연산보다 더 빠르다.)
(++ 현재 최신 CPU는 일반 나눗셈도 빨라서 차이가 아주 크지 않다.)
3.2.3. numeric의 std::gcd
#include <numeric>
unsigned long long n1, n2;
int answer = std::gcd(n1, n2);유클리드/바이너리 중 상황에 따라 가장 효율적인 방식을 사용하도록 구현되었다.
템플릿 함수여서 타입 의존적이다.
시간복잡도는 O(log min(n1, n2))으로 최적화된 low-level 연산이 사용되어 있다.
(++ 최적화된 low-level 연산?
= 내부에 유클리드 호제법으로 구현되어 있음.
= 일부 구현은 binary gcd를 사용해 나눗셈 연산을 줄이고 속도를 높이게 처리. (컴파일러, 라이브러리 차원 최적화)
= 모든 컴파일러와 라이브러리에서 일관된 성능과 동작 보장. (일관성 및 유지보수성 높음)
= 템플릿 함수로 작성되어있어 다양한 데이터 타입에 최적화되고, 타입별 오버플로우와 예외 문제 자동으로 처리 가능. (타입 독립성과 안전성)
3.3. 결론
최대한 빠른 gcd값 구하기라면 std::gcd가 가장 효율적이다. 표준 라이브러리 함수로 안정성이 보장되어 있고 내부 구현이 최적화되어 있으며, 다양한 타입에 바로 적용이 가능하며 코드 가독성 및 유지보수가 용이하기 때문이다.
각 방법의 차이는 사실상 미세하며, 직접 구현이 필요한 경우는 공간 효율성을 위해 반복문 구현을 주로 사용한다.
4. 후기
단순하게 std::gcd 위주로 사용했는데 모두가 사용하는 건 이유가 있다는 생각도 들었고, gcd에 대해 다시 한 번 더 생각해보게 되었다.