백준 알고리즘 4150번 피보나치 수 문제

JAVA/알고리즘|2018. 8. 1. 22:16


저번에 공부한 BigInteger를 응용하여 알고리즘 문제를 풀어보자.

이번문제는 피포나치 수열을 해결하는 문제이다. 저번에 포스팅 했었던 피보나치 수열을 구하는 방법은 재귀와 DP 그리고 반복문이 있다.

이번 문제는 반복문을 사용하여 구해보자. 위에 문제를 보면 데이터의 결과 크기가 Long의 범위를 벗어난다. 그렇기 때문에 데이터를 담기위해서 BigInteger를 사용하였다.

생각보다 문제는 간단하나 여러가지 경우를 정리 할 수 있었서 좋았다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package test;
 
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Fibanachi {
    
    
    public static void main(String args[]) {
        
        List<BigInteger> data = new ArrayList<>();
 
        data.add(BigInteger.ZERO);
        data.add(BigInteger.ONE);
 
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
 
        if (0 == num) {
            System.out.println(data.get(0));
            in.close();
            return;
        }
 
        if (1 == num) {
            System.out.println(data.get(1));
            in.close();
            return;
        }
 
        for (int i = 2; i <= num; i++) {
            data.add(i, data.get(i - 1).add(data.get(i - 2)));
        }
 
        System.out.println(data.get(num));
        in.close();
    }
 
}
cs


자세한 코드는 아래 URL을 통해서 확인가능하다.
https://github.com/weduls/algorithm/tree/master/%EC%88%98%ED%95%99/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98

댓글()

Java의 거대 정수를 담을 수 있는 BigInteger

JAVA|2018. 7. 31. 23:36

대학교 학창시절에 BigInteger만들기를 자료구조 시간에 C로 만들어 본적이 있다.

그리고 실질적으로 실무에서는 Long값을 벗어난 데이터를 담아서 사용해본적이 없어 자바의 BigInteger라는 객체가 존재하는지 몰랐다.

매주 진행하는 알고리즘 스터디에서 문제를 풀다가 Long값 이상의 데이터가 필요해서 찾다가 사용하게 되었다.

몇 가지 정리해보자.

BigInteger 객체 생성 방법
팩토리 메서드와 기존 constant 객체로써 제공하는 방법으로 BigInteger객체를 만들 수 있다.

1
2
3
4
5
6
7
8
9
10
// Constant
BigInteger zero = BigInteger.ZERO;
BigInteger one = BigInteger.ONE;
BigInteger ten = BigInteger.TEN;
        
// 생성자로 생성
BigInteger ten2 = new BigInteger("10");
        
// 팩터리 메스드로 생성
BigInteger ten3 = BigInteger.valueOf(10);
cs


그럼 생성자와 Constant 그리고 팩터리 메서드로 만드는 경우의 차이는 무엇인가? 
Constant와 팩터리 메스드의경우 같은 계속 같은 객체가 나오게 될 것이고, 생성자의 경우 매번 다른 객체가 나온다.

1
2
3
4
5
6
7
8
9
// 비교
System.out.println(ten == ten2);
System.out.println(ten3 == ten2);
System.out.println(ten3 == ten);
 
// 결과
false
false
true
cs


Immutable
그리고 BigInteger의 경우 Immutable 속성으로 인해 연산을 통해 나온 결과는 기존의 BigInteger 객체가 변경되는 것이 아니라 새로운 객체가 만들어진다.

사칙연산
우선 BigInteger는 사칙연산을 바로 사용할 수 없다.
사칙연산을 사용하기 위해서는 다음과 같은 메서드등을 사용할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
// 덧셈
System.out.println(ten2.add(ten3));
        
// 뺄셈
System.out.println(ten2.subtract(ten3));
        
// 곱셈
System.out.println(ten2.multiply(BigInteger.ONE));
 
// 나누기
System.out.println(ten.divide(BigInteger.ONE));
cs


다음번에는 이 BigInteger를 이용해서 피보나치 수열을 한번 풀어보자.

'JAVA' 카테고리의 다른 글

Java의 거대 정수를 담을 수 있는 BigInteger  (0) 2018.07.31

댓글()