Coding Diary

문제 및 코드 1. 생각 // 생각 // 1과 2를 배치한 합이 n을 만들 수 있는 모든 경우의 수를 구해야 함 // 조합의 느낌 // 구현 // 규칙이 피보나치 수열... // 피보나치 수열의 값을 재귀로 구해도 되고 dp로 구해도 된다 2. 회고 여러 경우를 살펴보니 조합과 순열의 기운이 느껴졌다. 그런데 조합과 순열 코드 작성이 잘 안 돼서 다른 코드를 참고했다. 그런데 n에 따른 결과가 피보나치 수열이라고 dp로 풀더라... 그래서 나도 dp로 풀었다 dp로 풀 생각을 맨 첨에 어떻게 하지..? 3. 기억 피보나치 수열을 dp로 풀 때 들어올 값이 1인 경우를 잘 고려해야 한다. 4. 체크 풀이 횟수 시간 정답 여부 참고 여부 1 25분 O

1. 개념 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 2. 특징 큰 문제를 작은 문제로 나눌 수 있어야 한다 작은 문제들이 반복되고, 작은 문제들의 결과값은 항상 같아야 한다. 작은 문제들은 한 번만 계산해 DP 테이블에 저장한다. 이후에 재사용할 때는 DP 테이블에 있는 것을 사용한다. 이는 메모이제이션 기법이다. 톱 다운 방식과 바텀 업 방식으로 구현 가능하다 3. 원리 피보나치 수열을 통해 원리를 알아보자. 피보나치 수열 공식: D[N] = D[N-1] + D[N-2] 1) 동적 계획법으로 풀 수 있는지 확인하기 피보나치 수열의 3번째 값은 1번째 값과 2번째 값의 합이다. 그리고 이는 수열이 진행되면서 반복된다. 즉 큰 ..