자바 코딩 인터뷰 완벽 가이드 ch8. 재귀 및 동적 프로그래밍

8.1 재귀의 개요

재귀 메서드 : 직접 또는 간접적으로 스스로를 호출하는 메서드

 

8.1.1 재귀 문제로 인식하기

재귀 문제는 하위 문제로 구성될 수 있다.

> 메서드가 반환한 값을 해당 메서드가 반환한 다른 값으로 표현할 수 있다.

> 피보나치 수, 숫자 목록 합계, 최대공약수, 팩토리얼, 재귀이진 검색, 문자열 반전 등

 

 

 

8.2 동적 프로그래밍의 개요

재귀 문제는 평범한 재귀 알고리즘을 사용하거나 프로그래밍을 사용하여 해결할 수 있다.

 

8.2.1 메모이제이션

메모이제이션(하향식 동적 프로그래밍) :

메서드에서 중복 작업할 때 사용하는 기법. 동일한 입력에 관한 메서드를 한 번만 호출하도록 보장한다. 이미 계산된 입력을 계산하고자 메서드를 호출해야 할 때 메모이제이션이 저장된 결과를 반환하여 메서드 호출을 하지 않는다.

 

시간 복잡도 개선 : O(2^n) 에서 O(n)으로 줄어들었다

공간 복잡도 : 여전히 O(n)

 

하향식 접근법 > "나는 책을 썼다. 어떻게? 책의 장을 썼다. 어떻게? 각 장의 절을 썼다."

 

8.2.2 태뷸레이션

테뷸레이션 : 상향식 접근법(상향식 동적 프로그래밍)은 재귀 알고리즘의 단점을 방지하고 공간 복잡도를 줄인다.

 

상향식 접근법 > "나는 각 절의 문단을 썼다. 그리고? 모든 장을 썼다. 그리고? 책을 썼다."

상향식 접근 방법은 호출 스택을 쌓을 때 재귀에 의해 부과되는 메모리 비용을 줄여주므로 재귀 알고리즘의 단점인 스택 오버플로 에러가 발생할 수 있는 취약점을 제거한다. 스택 오버플로 에러는 호출 스택이 지나치게 커져서 공간이 부족할 때 발생한다. 

 

시간 복잡도 : 여전히 O(n)

공간 복잡도 : O(n) 에서 O(1)로 줄어들었다.

 

평범한 재귀 : 알고리즘은 실행 시간이 O(2^n)이며 공간 복잡도는 O(n)
메모제이션 재귀 : 알고리즘은 실행 시간이 O(n) 공간 복잡도는 O(n)
태뷸레이션 재귀 : 알고리즘은 실행 시간이 O(n) 공간 복잡도는 O(1)

 

 

 

8.3 코딩 테스트

 

8.3.1 코딩테스트 1: 로봇 격자 지도

https://www.youtube.com/watch?v=WdqJqZqEJuw 

 

8.3.3 코딩테스트 3: 요세푸스

https://www.acmicpc.net/problem/1158

https://www.youtube.com/watch?v=rxgBHPy-GAk&list=PLHqxB9kMLLaNIvuYT6NgXsIt782lS3xiD&index=3 

#1. Queue 이용 (책에 있는 풀이법, 시간 제일 오래 걸림)

def findTheWinner(self, n: int, k: int) -> int:
    q = [i for i in range(1, n+1)]
    while len(q) > 1:
        for j in range(1, k+1):
            friend = q.pop(0)
            if j != k:
                q.append(friend)
    return q[0]

#2. Circular Linked List 이용

def findTheWinner(self, n: int, k: int) -> int:
    q = [i for i in range(1, n+1)]
    j = 0
    while len(q) > 1:
        j = (j + k -1) % len(q)
        q.pop(j)
    return q[0]

#3.1. 점화식 이용

'''
f(1,k) = 1
f(n,k) = (f(n-1,k) + k -1)%n + 1

'''
def findTheWinner(self, n: int, k: int) -> int:
    if n == 1:
        return 1
    return ((self.findTheWinner(n-1, k) + k -1)%n) + 1

#3.2. 점화식 > 반복문 : 동적 프로그래밍

def findTheWinner(self, n: int, k: int) -> int:
    s = 1
    for n in range(1, n+1):
        s = ((s+k-1)%n)+1
    return s

 

8.3.5 코딩테스트 5: 동전 거스름돈

https://www.youtube.com/watch?v=N7m44HWa39o 

그리디(최소 동전 개수) > 동적 방법(모든 경우의 수)

def solution(n, money):
	dp = [1] + [0]*n
    
    for coin in money:
    	for price in range(coin, n+1):
        	if price >= coin:
            	dp[price] += dp[price - coin]
    return dp[n] % 1000000007

 

*참고 모듈러? https://velog.io/@yoopark/1000000007

 

8.3.7 코딩테스트 7: 마법의 인덱스

 

8.3.9 코딩테스트 9: 상자 쌓기

 

8.3.11 코딩테스트 11: 기사의 여행

https://www.youtube.com/watch?v=l6Q55ag8AVQ 

> 해밀턴 경로, 백트래킹

 

8.3.13 코딩테스트 13: 계단

https://www.youtube.com/watch?v=lhZTYwHgrDM&list=PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v&index=3 

 

8.3.15 코딩테스트 15: 줄바꿈

트라이 자료구조 > https://www.youtube.com/watch?v=TohdsR58i3Q > 특별히 문자열에서 검색을 빠르게 도와줌

 

 

https://www.youtube.com/watch?v=WooOuXIiRjE 

 

https://velog.io/@gojaegaebal/210126-%EA%B0%9C%EB%B0%9C%EC%9D%BC%EC%A7%8050%EC%9D%BC%EC%B0%A8-%ED%8A%B8%EB%9D%BC%EC%9D%B4Trie-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%B0%8F-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0feat.-Class