DP 정복 - 1.1 재귀 접근 방법이란?

이번 책은 설명에 매우 많은 지라,

책 내용을 다 옮겨 적기보다는(저작권 문제도 있으니)

책을 읽고 내가 이해한 내용만 좀 짤막하게 남기려고 한다.

 

DP는 항상 정복(?) 하고 싶지만 못하는 '산'같은 존재라

이번 기회에, 이 책을 통해 정복할 수 있었으면 좋겠다.

 

일단 첫 장은 그래도 익숙한 재귀 접근 방법에 대한 설명이다.

 

재귀의 특징

1. 종료 조건(Terminating Condition) 

2. 전체 작업의 일부만 수행하고 나머지는 재귀 호출에 위임

 

전체 문제를 한 번에 풀지 않아도 되므로 상대적으로 쉽(???)이다고 저자는 말함.

 

재귀 함수 내에서 두 개의 코드 부분

1. 더 큰 범위의 풀이법을 더 작은 범위의 인수를 가진 풀이법을 사용해 정의하여 구체화

2. 종료 조건 지정

 

코딩 테스트나 실무에 사용되는 코드 작성 시 웬만하면 일기 쉬운 코드로 작성하는 걸 추천.

 

함수 작성 시 유의사항

1. 목적지향적이어야 함. 의도된 대로 동작해야 함. 모호한 결과 반환하면 안 됨.

2. 수행 시간이 짧을수록, 메모리를 적게 쓸수록, 이해하기 쉬울수록 좋음

3. 중복 코드는 웬만하면 작성을 피할 것

 

재귀의 분류

1. 선행 재귀 : 함수가 작업을 수행하기 전에 재귀 호출

2. 후행 재귀 : 함수가 작업을 수행한 뒤에 재귀 호출

물론 선행/후행 재귀에 포함되지 않는 재귀 형태도 존재.

 

마지막으로 저자는 재귀를 잘 다뤄야 좋은 프로그래머라고 이야기한다.