패스트캠퍼스 챌린지 10일차

재귀 용법 (Recursive call, 재귀 호출)

 • 함수 안에서 동일한 함수를 호출하는 형태

 

팩토리얼 예제

public class Factorial{
  public int factorialFunc(int n){
    if(n > 1){
      return n * this.factorialFunc
    }else{
      return 1;
    }
  }
}

시간/공간 복잡도 O(N)

 

 

동적 계획법과 분할 정복

 • 동적 계획법 (Dynamic Programming, DP)

  - 입력 크기가 작은 부분 문제들을 해결한 뒤, 해당 부분의 해(풀이)를 활용해서 보다 큰 부분 문제를 해결, 최종적으로

    전체 문제를 해결하는 알고리즘

  - 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용하여 쉬운 문제를 해결하는 방식

  - Memoization 기법 사용 : 프로그램 실행 시 이전에 사용했던 값을 기억하여 재사용,

    다시 계산하지 않아 실행속도 증가

 

• 분할 정복 (Divide and Conquer)

 - 문제를 나눌 수 없을 때 까지 나누어서 각각 풀면서 합병하여 문제의 답을 찾는 알고리즘

 - 상위의 해답을 얻기 위해, 아래로 내려가며 하위의 해답을 구하는 방식

 

공통점

 - 문제를 잘게 쪼게서 가장 작은 단위로 분할

 

차이점

  - 동적 계획법에서는 부분 문제는 중복되어, 상위 문제 해결 시 사용됨 => Memoization 기법

  - 분할 정복에서는 부분 문제는 중복되지 않는다.

 

 

동적 계획법 피보나치 수열 알고리즘 풀이 방법

동적 계획법을 통한 피보나치 수열 알고리즘 풀이

• 동적 계획법을 사용하여 배열을 통한 데이터를 저장한 후 문제를 해결해나아가며 배열의 마지막 값으로 알고리즘

  풀이의 값을 도출한다.

 

 

10일차 인증

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]