재귀, 다이나믹 프로그래밍

알고리즘을 공부하면서
컴퓨터를 이용하려하면 내 머리로하는 일도 만만치 않다는 느낌을 받는다.
공부를 시작한지 약 한달동안 체감은 되지 않지만 발전 했으리라 믿고
나같이 개념이 부족한 사람들에게 도움이 되고자 블로그를 작성했다.

재귀메소드

class 메소드에서 메소드를 반환 하면 종료조건이 없는 경우 무한으로 반복되는 재귀 메소드가 만들어진다.
종료조건을 설정하여 메소드를 실행시키면 계속하여 메소드에서 메소드를 반환하며 반복 실행할 것이고, 이말은 원하는 값을 위해 엄청나게 공을 들인다는 뜻이다
메모리도 많이 사용하면서 속도도 느리기 때문에
가독성이 좋다는 장점 외엔 재귀의 장점은 없다고 생각하면 된다.

[재귀를 사용해야할 때는 물론 있을 것이다. 그러므로
"재귀를 절대 사용하면 안된다" 는 틀렸다.
재귀를 사용할 수 있다고 아무때나 사용하는것은 지양 해야 한다 -]

당연한 이야기겠지만 강조하는 부분은 꼭 명심해야 한다.
재귀메소드에 관한 간략한 설명은 마무리하고
수학에서 조합문제를 풀기위하여 3가지 프로그래밍을 해볼 것이다.

1. 반복문을 통한 계산
2. 재귀메소드를 이용한 방법
3. 다이나믹프로그래밍을 이용한 방법

<참가자 n명중 (4 <= n <= 10) 추첨하여 4명에게 상품지급을 한다.>

private int nCr (int totalPerson) {
        
        int win = 4;
        int denominator = 1; //분모가 될 변수
        int numerator = 1; //분자가 될 변수
        
        for (int i = 0; i < win; i++) {
            numerator *= (totalPerson - i);
            denominator *= (i + 1);
        }
        return numerator / denominator;
    }

nCr 계산을 위해 반복문을 통하여 분모 분자를 계산해주고
경우의 수를 반환해주는 메서드 이다.

하지만 nCr의 모양은 사실 정해져있다.
몇개의 물건 중에서 순서없이 몇가지를 선택할 수 있는 경우의수를 파스칼삼각형으로 나타낼 수 있다.

이것이 파스칼삼각형의 모양이고

이것은 각 nCr의 값들이다.

이두가지로 알게 된 사실이 중요하다.

1. r 이 0 일때나 r 이 n과 같을 때는 모두 1이다.
2. nCr의 값은 n-1Cr-1 과 n-1Cr의 합과 같다.

이 두가지로 로직을 짜 재귀함수를 만들 수 있다.
다음은 재귀함수의 모양이다.

private int nCr (int n, int r) {

        if (r == 1 || r == n){
            return 1;
        } else {
            return nCr(n-1, r-1) + nCr(n-1, r);
        }
    }

이렇게 파스칼삼각형의 재귀적으로 구현하였다.
하지만 이메서드로 코딩테스트를 본다면 통과하지 못할 가능성이 높다.
가독성은 좋지만 사실 풀이하는 방식은 노가다에 가깝다.
따라서 메모리초과로 실패할 가능성이 농후하다.

하지만 이값들을 저장해놓는다면?
nCr의 n을 입력받을 때
n까지의 파스칼삼각형의 데이터를 저장해 놓는다면
별도로 메모리를 사용할 일 없이 꺼내 올 수 있다.

바로 다이나믹 프로그래밍이다.

private int nCr (int totalPerson) {

        int win = 4;
        int[][] nCr = new int[totalPerson+1][totalPerson+1];
        for (int i = 0; i <= totalPerson; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == i || j == 0){
                    nCr[i][j] = 1;
                } else {
                    nCr[i][j] = nCr[i-1][j-1] + nCr[i-1][j];
                }
            }
        }
        return nCr[totalPerson][win];
    }

재귀와 다른점은
필요한 만큼만의 파스칼삼각형을 구할수 있었고
구하려는 값을 구할때도 미리 계산해놓은 값을 재활용하여 뽑아냈다.
재귀는 틀렸어도, 다이나믹프로그래밍으로는 맞출수 있었다.

공부를 시작한지 1달 쯤
java 기초를 둘러봤고,
잘 익히지 못한 java기초는 앞으로 계속 공부를 진행하며
깨우치고, 배우고하며 체득할테니 너무 앓으며 외우려 하지 않기로 했다.
진행해야 할 공부가 산더미 이기 때문에
java의 정석 책, 유튜브 등을 보며 필요한 개념들을 죽죽 찾아보려고 한다.