높은 정확도의 자료 처리를 위해 float, double과 같은 부동소수점 자료형과 decimal 자료형을 사용할 수 있다. 그런데 소수점 아래의 정확도가 아닌 큰 수의 정확한 처리는 어떨까. 자주 사용하는 정수형 int보다 더 큰 값은 long, 더 큰 값은 ulong, 그보다 더 큰 값은 어떻게 처리할까. 한 때는 오버플로우 되는 값을 미리 처리하기 위해 최대값의 절반 범위에서 넘어간 값을 다른 변수에 옮겨담아 자리올림 같은 개념으로 구현한 적이 있다.
A0 = 1,073,741,823 ( int.Maxvalue / 2 )일 때 A0 값이 1 증가하면 A1 = 1, A0 = 0 이 되는 식
이렇게 하면 물론 간단한 덧셈 뺄셈은 쉽게 구현 가능하지만 곱셈은? 나눗셈은? 답이 안나온다. 심지어 저런 식으로 하면 출력조차 어렵다. 출력할 때 어차피 큰 수의 원형을 뽑아내야하게 되는데 그게 또 답없다. 아무튼 큰 수의 곱셈을 하기 위한 카라추바 알고리즘이 있다. 그걸 이용하면 어떻게 연산까지는 하겠다. 근데 큰 수의 나눗셈은? 진짜 이제는 머리가 어질어질해진다.
하지만 C#은 큰 정수의 처리를 위한 BigInteger 구조체를 제공하고 있다. 다른 자료형처럼 사용 가능하며 연산 시간도 빠르다. BigInteger 자료형은 System.Numerics 를 참조한다. 혹시 네임스페이스를 못찾겠다는 에러가 발생하면 어셈블리>프레임워크에서 System.Numerics를 찾아 참조를 추가해주자.
using System;
using System.Numerics;
class Program
{
static void Main()
{
BigInteger big = new BigInteger();
big = 1;
Console.WriteLine(big);
big = ulong.MaxValue;
Console.WriteLine(big);
// big = ulong.MaxValue + 1;
// ulong 최대값을 넘어간 값은 컴파일타임에 에러가 생긴다.
// 이런 값은 문자열 형태로 Parse 메소드를 쓰거나
// 연산을 통해 입력시켜줘야한다.
big++;
Console.WriteLine(big);
}
}
// 결과
// 1
// 18,446,744,073,709,551,615
// 18,446,744,073,709,551,616이걸 활용할 수 있는 문제를 풀어보자. 백준 10826번 피보나치 수 4 문제다.
10826번: 피보나치 수 4
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
최대 10000번째 피보나치 수를 구해야하는 문제다. 10000이라는 수치가 별거 없어보이지만 피보나치 수는 94번째에 ulong범위를 넘어가버리고 1000번째 피보나치 수는 200자리를 넘는다. 나머지를 구하는 문제도 아닌 수 자체를 구하는 이 문제는 여러 테크닉을 요구하는 것 같지만 BigInteger를 쓰면 아주 간단한 문제가 되어버린다.
using System;
using System.Numerics;
class Program
{
static int n;
static BigInteger[] f = new BigInteger[10001];
static void Main()
{
n = int.Parse(Console.ReadLine());
f[0] = 0; f[1] = 1;
for(int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
Console.WriteLine(f[n]);
}
}
0번부터 10000번 피보나치 수를 저장할 BigInteger 형식 배열만 만들어주면 된다. 메모리를 조금 많이 먹긴 하지만 연산 시간은 압도적으로 빠르다. 그리고 Math 클래스를 사용하지 않고도 거듭제곱, 대소비교 등 다양한 메소드를 바로 사용할 수 있어서 편하다. 당연히 Math 클래스를 거치지 않으니 Parse를 해줄 필요도 없다. 이런거 생각해보면 Math 클래스의 메소드를 많이 사용하는 코드에서는 작은 수를 다루더라도 BigInteger를 쓰는게 나을지도 모르겠다.
높은 정확도의 자료 처리를 위해 float, double과 같은 부동소수점 자료형과 decimal 자료형을 사용할 수 있다. 그런데 소수점 아래의 정확도가 아닌 큰 수의 정확한 처리는 어떨까. 자주 사용하는 정수형 int보다 더 큰 값은 long, 더 큰 값은 ulong, 그보다 더 큰 값은 어떻게 처리할까. 한 때는 오버플로우 되는 값을 미리 처리하기 위해 최대값의 절반 범위에서 넘어간 값을 다른 변수에 옮겨담아 자리올림 같은 개념으로 구현한 적이 있다.
A0 = 1,073,741,823 ( int.Maxvalue / 2 )일 때 A0 값이 1 증가하면 A1 = 1, A0 = 0 이 되는 식
이렇게 하면 물론 간단한 덧셈 뺄셈은 쉽게 구현 가능하지만 곱셈은? 나눗셈은? 답이 안나온다. 심지어 저런 식으로 하면 출력조차 어렵다. 출력할 때 어차피 큰 수의 원형을 뽑아내야하게 되는데 그게 또 답없다. 아무튼 큰 수의 곱셈을 하기 위한 카라추바 알고리즘이 있다. 그걸 이용하면 어떻게 연산까지는 하겠다. 근데 큰 수의 나눗셈은? 진짜 이제는 머리가 어질어질해진다.
하지만 C#은 큰 정수의 처리를 위한 BigInteger 구조체를 제공하고 있다. 다른 자료형처럼 사용 가능하며 연산 시간도 빠르다. BigInteger 자료형은 System.Numerics 를 참조한다. 혹시 네임스페이스를 못찾겠다는 에러가 발생하면 어셈블리>프레임워크에서 System.Numerics를 찾아 참조를 추가해주자.
using System;
using System.Numerics;
class Program
{
static void Main()
{
BigInteger big = new BigInteger();
big = 1;
Console.WriteLine(big);
big = ulong.MaxValue;
Console.WriteLine(big);
// big = ulong.MaxValue + 1;
// ulong 최대값을 넘어간 값은 컴파일타임에 에러가 생긴다.
// 이런 값은 문자열 형태로 Parse 메소드를 쓰거나
// 연산을 통해 입력시켜줘야한다.
big++;
Console.WriteLine(big);
}
}
// 결과
// 1
// 18,446,744,073,709,551,615
// 18,446,744,073,709,551,616이걸 활용할 수 있는 문제를 풀어보자. 백준 10826번 피보나치 수 4 문제다.
10826번: 피보나치 수 4
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
최대 10000번째 피보나치 수를 구해야하는 문제다. 10000이라는 수치가 별거 없어보이지만 피보나치 수는 94번째에 ulong범위를 넘어가버리고 1000번째 피보나치 수는 200자리를 넘는다. 나머지를 구하는 문제도 아닌 수 자체를 구하는 이 문제는 여러 테크닉을 요구하는 것 같지만 BigInteger를 쓰면 아주 간단한 문제가 되어버린다.
using System;
using System.Numerics;
class Program
{
static int n;
static BigInteger[] f = new BigInteger[10001];
static void Main()
{
n = int.Parse(Console.ReadLine());
f[0] = 0; f[1] = 1;
for(int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
Console.WriteLine(f[n]);
}
}
0번부터 10000번 피보나치 수를 저장할 BigInteger 형식 배열만 만들어주면 된다. 메모리를 조금 많이 먹긴 하지만 연산 시간은 압도적으로 빠르다. 그리고 Math 클래스를 사용하지 않고도 거듭제곱, 대소비교 등 다양한 메소드를 바로 사용할 수 있어서 편하다. 당연히 Math 클래스를 거치지 않으니 Parse를 해줄 필요도 없다. 이런거 생각해보면 Math 클래스의 메소드를 많이 사용하는 코드에서는 작은 수를 다루더라도 BigInteger를 쓰는게 나을지도 모르겠다.
