DFS(재귀)
[2023.04.22 ~ 2023.04.27] 동안 공부한 DFS 내용이다.
해당 포스트는 누구나 자료구조와 알고리즘 개정 2판을 참고하여 작성되었다.
루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다. 재귀를 쓸 수 있다고 하여 무조건 재귀를 써야하는 것은 아니다. 재귀는 명쾌한 코드를 작성해 줄 수 있는 하나의 도구이다.
재귀를 써야하는 이유
재귀는 **하위 문제**의 계산 결과에 기반에 계산할 수 있을 때 쓰인다. 어떠한 문제를 다룰때 문제를 더 작은 범위로 쪼갠 결과에 기반해서 풀릴 수 있다면 재귀를 쓰는게 효율적이다.
[하위문제] 는 입력을 더 작게한 똑같은 문제이다
즉, 더 큰 문제를 해결하는데 더 작은 문제에서 문제의 해결점을 찾아야 하는 것이다.
하향식과 상향식
상향식과 하향식 둘다 재귀로 풀어나갈 수 있다. 하지만 상향식은 루프나 재귀나 별반 차이가 없다. 하지만 하향식에서는 재귀를 써야한다. 하향식에서는 재귀가 더 효율적이다.
하향식 재귀
하향식 재귀는 기존과는 완전히 다른 방식이다.
- 누군가 이미 작성중인 함수를 완벽하게 짜 놓았다.
- 이 문제의 하위 문제를 생각해보자.
- 하위문제에 함수를 호출했을 때, 어떻게 되는지 살펴본 후 거기서부터 생각해보자
불필요한 재귀 호출을 줄이자
재귀를 제대로 사용하지 않으면 어떠한 문제를 해결할 수는 있어도 가장 느린 빅오(O^2n) 를 만들 수 있는 주된 원인이다.
[빅오] 는 데이터 원소가 N개 일때 얼마나 많은 단계수가 필요한가라는 핵심 질문에 대한 답
메모이제이션을 통한 동적 프로그래밍
하위문제가 중첩될때, 메모이제이션을 통해 문제를 해결한다. 먼저 계산한 하위문제의 결과를 기억해 재귀 함수 호출 중복을 방지한다.
메모이제이션
메모이제이션 == 메모리제이션(기억)
함수를 호출할때, 호출 결과를 해시 테이블에 저장한다. 재귀 함수를 중복호출하여 값을 활용하는 것이 아니라 해쉬 테이블에 담긴 결과를 활용하여 재귀를 사용한다.
동적프로그래밍
[동적프로그래밍] 은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차
하지만 메모이제이션을 쓰더라도 재귀가 루프보다 오버헤드가 더 든다는 사실을 잊어서는 안된다. 즉, 재귀를 어떻게 사용하든 컴퓨터는 호출 스택에 모든 호출을 기록해야하므로 메모리를 소모한다…
재귀를 공부하며…
코딩테스트 문제와 책을 병행하면서 공부한 결과, 재귀와 관련하여 공부해야되는 내용에 대해 정리해보았다. 추후 공부해나갈 예정이다.
- 이진트리
- 퀵정렬
