[프로젝트 오일러] 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합

두번째 프로젝트 오일러 포스팅입니다.

문제는 재미있게 7번까지 풀었는데 올리기는 벌써부터 왜이렇게 귀찮은 것인지 ㅠㅠ 

그렇지만 칼을 뽑았으면 무라도 베어야겠지요.

문제는 아래와 같습니다.

피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?

코드를 작성함에 있어서 가장 기본적인 원칙은 아래와 같습니다. (몇 가지가 추가되었습니다.)

1. clean code를 최대한 준수하도록 합니다. 
• 코드의 라인 수가 짧을 수록 좋겠지만 그것보다는 깨끗한 코드를 만드는데에 더 초점을 두었습니다.
• SRP(단일 책임 원칙), OCP(개방-폐쇄 원칙), 한 메소드 내에 동일한 추상화를 최대한 유지하도록 하였습니다.
• 하드코딩으로 특정 문제만 풀 수 있는 것이 아닌 모든
2. 1의 가독성이 유지되는 선에서 가능한한 코드를 짧게 합니다.
3. 언어는 Java를 사용합니다.
4. 테스트 주도 개발 기법(TDD, Test - Driven - Development)을 이용합니다.
5. 가능한한 혼자 힘으로 해결합니다.
• 막히는 부분이 있을때, 비효율적인 코드가 나올지라도 찾아보지 않고 혼자 힘으로 해결합니다. (이는 저의 프로그래밍 실력을 향상시키기 위한 프로젝트이기도 합니다.)
• 해당 수학적인 라이브러리가 구현되어 있다고 하더라도 기본적인 API 이외에는 스스로 구현합니다. 

※ 테스트 주도 개발 기법에 대하여 보다 자세히 알고 싶으시면 구글에 검색, 또는 제가 1년 전에 작성한 http://jhleed.tistory.com/13 을 참조하세요 :)

완성된 코드는 아래와 같습니다. (getSumOfTermsBelow)

지금 보니 setFibonacciNumbers는 더 깔끔하게 리팩토링 할 수 있을 것 같기도 하군요 ^^

import java.util.ArrayList;
import java.util.List;
 
public class FibonacciNumber {
    public int getSumOfTermsBelow(int restrictNumber) { 
        List<Integer> fibonacciNumbers = setFibonacciNumbers(restrictNumber);
        return sumOfEvenFibonacciNumber(fibonacciNumbers);
    }
 
    private int sumOfEvenFibonacciNumber(List<Integer> fibonacciNumbers) {
        int result = 0;
        for(int fibonacciNumber : fibonacciNumbers){
            if(isEvenNumber(fibonacciNumber)){
                result += fibonacciNumber;
            }
        }
        return result;
    }
 
    private List<Integer> setFibonacciNumbers(int restrictNumber) {
        List<Integer> fibonacciNumbers = new ArrayList<Integer>();
        int firstNumber = 0;
        int secondNumber = 1;
        int currentNumber = firstNumber + secondNumber;
 
        while(currentNumber <= restrictNumber){
            fibonacciNumbers.add(currentNumber);
            firstNumber = secondNumber;
            secondNumber = currentNumber;
            currentNumber = firstNumber + secondNumber;
        }
 
        return fibonacciNumbers;
    }
 
    private boolean isEvenNumber(int fibonacciNumber) {
        return fibonacciNumber % 2 == 0;
    }
}
 
 

그럼 리뷰를 하기 전에 한가지 고백드리자면..

문제는 400만 이하의 짝수의 합인데, 문제를 잘못 읽어서 처음에는 홀수의 합을 푸는 솔루션으로 코딩을 하고 있었어요 ㅠㅠㅠ

중간에 짝수를 계산하는 솔루션으로 바뀝니다. 유념하고 봐주시길 바랄게요!

역시 테스트 코드를 먼저 만듭니다. (Test - First)

그리고 가장 간단하게 통과하는 코드를 작성합니다.

1 이하의 홀수 피보나치 수의 합은 1이죠.

계속해서 두번째, 세번째 테스트 코드를 작성합니다.

2 이하의 홀수 피보나치 수열의 합 : 1

3이하의 홀수 피보나치 수열의 합 : 4 (1 + 3)

역시 가장 간단하게 통과시킵니다.

아직은 로직을 생각하는 단계가 아닙니다.

5 이하의 홀수 피보나치 수열 (1, 3, 5)의 합은  9입니다.

여기서부터는 조금씩 눈에 보이지 않는 규칙을 찾아냅니다. 

9는 피보나치 수열 1, 3, 5의 합

4는 1, 3의 합

이는 아래와 같은 형태로 표현할 수도 있습니다.

아, 여기에도 보이지 않는 규칙이 숨어있습니다.

1 + 3 + 5 .. 

1~5까지 반복되는 값 중, 홀수인 값만 들어왔네요.

아래와 같이 조건문을 추가해줍니다.

조금씩 중복되는 규칙들이 보이기 시작합니다.

1, 2, 3, 5, 8은 피보나치 수열의 값들이므로 fibonacci의 List를 만들고 하드코딩으로 집어넣어 줍니다. 

그리고 아래의 if문은 거의 완벽한 중복이 되었네요. 

드디어 fibonacciNumbers.get(숫자)가 1씩 증가하는 규칙이 보입니다.

피보나치 수열에 13이라는 값이 있다고 가정해봅시다.

문제에는 n 이하이면서 홀수(또는 짝수)라는 조건이 붙으므로 입력된 값인 restrictNumber보다 피보나치 수열이 크다면

해당 피보나치의 항은 더하면 안되겠지요.

따라서 if(fibonacciNumbers.get(n) > restrictNumber) return 조건을 붙입니다.

이 조건은 모든 if문에 공통적으로 적용되는 것입니다.

또 중복이 생겼네요!

자 이제 규칙들이 보이므로 loop를 돌려서 일반화를 합니다!

이제 슬슬 하드코딩 - 중복된 규칙 생성 - 일반화의 패턴이 보이시나요?

TDD는 항상 베이비 스텝을 원칙으로 하고 있습니다.

이것이 필요한 이유는..

프로그래밍을 하다보면 보통 한번에 너무 많은 생각을 머릿속으로 하게 되어 엄청나게 추상적인 코드 (빅 스텝)가 나오곤 합니다.

이럴 경우, 꼬이게 된다면 코드를 다 날리고 다시 처음부터 짜게 되지만 베이비스텝으로 진행을 하게 된다면 여러번의 베이비 스텝으로 프로그래밍을 진행했기 때문에 적당하게 필요한 부분까지 돌아갈 수 있습니다.

또한 한번에 동시다발적인 생각을 하는게 아닌 문제를 작게 쪼개서 단계적으로 정복 할 수 있습니다. (분할 정복)

이것 외에도 장점이 참 많은데.. 일단은 계속 진행하도록 할게요~

위의 그림에서 입력값 8에 대한 일반화된 솔루션이 도출되었습니다.

이 솔루션은 5, 3, 2, 1의 입력값에 대해서도 동작할 수 있을까요?

잘 동작합니다! (이것은 미리 작성한 테스트 코드를 동작시켜 보면 알 수 있습니다.)

자 이제 모든 입력값에 대하여 잘 동작을 하니 중복을 제거합니다!

입력된 피보나치 수열에서 홀수 항의 합을 도출하는 솔루션은 완성되었다고 볼 수 있습니다. 

다음 단계는 위에서 fibonacciNumbers를 하드코딩으로 만들어주는 과정입니다.

이 역시 일반화된 솔루션으로 만들어 줘야 합니다. (400만이하까지 일일히 피보나치 넘버를 하드코딩으로 만들 수는 없겠죠?)

규칙을 찾아봅시다!

일단 저 기능은 setFibonacciNumbers라는 메소드로 분리합니다 (SRP원칙, 하나의 메소드는 하나의 기능만을 수행)

피보나치 수열의 규칙은

앞앞 항의 값과

앞 항의 값을 더한 값이

현재 항의 값이 되는 것입니다.

그리고 여기에서는 첫째 항과 둘째 항은 1, 2로 시작한다는 조건이 있습니다.

현재 항(세번째)은 첫번째 값과 두번째 값의 합입니다. 

이렇게 하나의 피보나치 항을 계산하고 나면

1번째 값 -> 2번째 값

2번째 값 -> 3번째(바로 이전에 만들어진 값) 으로 값이 전이됩니다. 

예시 : 피보나치 1, 2, 3 , 5 , 8

1번째 값 : 1

2번째 값 : 2

3번째에 계산된 값 : 1 + 2 = 3

그 다음에 들어가는 값은 5가 나와야 하므로 2 + 3을 더해야 합니다. 

따라서 1번째 값 : 2

2번째 값 : 3이 되어야 합니다.

이러한 패턴이 모든 구간에 반복됩니다.

또 중복이 생기는 것을 볼 수 있군요.

이러한 피보나치 수열을 구하는 반복속에도 중지 조건이 있습니다.

현재 피보나치수열의 값이 입력 값( 400만 이하 )가 넘게 된다면 추가를 그만 해야 합니다.

따라서 아래와 같은 조건문이 붙습니다.

모든 구간에 적용되는 조건입니다.

자 이제 중복을 제거합니다. 

코드가 줄어들었어요!

아래에서 입력값 (400만)을 검사해주는 방어코드가 있으므로 위에서 검사해주는 if문은 제거해줍니다. (리팩토링)

아래와 같은 코드에 가드 클로즈를 적용해줍니다. (리팩토링)

가드 클로즈 : 방어코드를 맨 위에 두어서 조건이 걸리면 그 이하는 건 뛰도록 하는 것.

동일한 결과를  내지만 저는 가드 클로즈를 선호하는 편입니다. 

if(fibonaccinumber % 2 == 0)의 역활은 짝수를 걸러내는 것이므로 가독성을 위하여

isEvenNumber()라는 메소드로 추출합니다. (리팩토링) (이때까지만 해도 홀수인 항의 합을 구하는 것으로 알고 있었죠..)

※ 테스트 코드에 의하여 솔루션의 결과가 보장받는 한 계속해서 리팩토링을 해야합니다.

(리팩토링)

for loop를 돌아서 홀수인 피보나치의 합을 구하는 부분을 하나의 메소드(sumOfOddFibonacciNumber)로 추출하였습니다. 

(SRP 원칙 및 동일한 레벨의 추상화 원칙)

가독성이 조금 더 나아졌나요? 

아....이제서야 홀수의 합이 아닌 짝수의 합인 것을 깨닫고 코드를 바꿉니다. 

가드 클로즈를 했던 부분을 버리고 짝수(isEvenNumber)일때 값을 누적시키도록 합니다.

또한, 줄일 수 있는 라인은 줄이도록 합니다 (17라인, 43~45라인)

완성된 값은 아래와 같습니다.

피보나치 수열에서 4백만 이하이면서 짝수인 항의 합은 

4613732!

 
public class FibonacciNumbersTest {
 
    private FibonacciNumber fibonacciNumber;
 
    @Before
    public void setUp() throws Exception {
        fibonacciNumber = new FibonacciNumber();
    }
 
    @Test
    public void test_sumOfTermsBelow1(){
        FibonacciNumber fibonacciNumber = new FibonacciNumber();
        assertEquals(0,fibonacciNumber.getSumOfTermsBelow(1));
    }
 
    @Test
    public void test_sumOfTermsBelow2(){
        assertEquals(2, fibonacciNumber.getSumOfTermsBelow(2));
    }
 
    @Test
    public void test_sumOfTermsBelow3(){
        assertEquals(2, fibonacciNumber.getSumOfTermsBelow(3));
    }
 
    @Test
    public void test_sumOfTermsBelow5(){
        assertEquals(2, fibonacciNumber.getSumOfTermsBelow(5));
    }
 
    @Test
    public void test_sumOfTermsBelow6(){
        assertEquals(10, fibonacciNumber.getSumOfTermsBelow(8));
    }
 
    @Test
    public void test_sumOfTermsBelow90(){
        assertEquals(44, fibonacciNumber.getSumOfTermsBelow(90));
    }
 
    @Test
    public void test_sumOfTermsBelow4000000(){
        assertEquals(4613732, fibonacciNumber.getSumOfTermsBelow(4000000));
    }
}

읽으시느라 수고 많으셨습니다 

도움이 되셨길 : )