재귀,DP, 백트래킹 뿌수기...

[ 재귀 ]

-> 귀납적 사고가 가능한가?

* 절차적 사고를 버리고 귀납적으로 접근하는 것이 중요*

 

01. 함수정의

- 함수가 어떤 역할을 수행해야하는지/어떤 인자를 받아야하는지

 

02. base condition

- 종료조건

 

03. 재귀식

- 말로 풀어쓰고, n에 대한 식으로 작성

---

[다이나믹 프로그래밍 DP]

---

-> 이거 완전탐색인데? 근데 경우의 수가 너무 크다!

-> 메모이제이션 가능한가? 겹치는 부분 문제를 해결할 수 있는가?

-> 매 순간 최선의 선택을 해야하는가?

 

* 상태값을 정하는 것이 핵심*

 

[ 연습문제 ]

(1) 피보나치 수열

 

[조건 충족]

1. 귀납적으로 사고가능?

1,2,3,4,5...N => N일때 fibo(N)=fibo(N-1)+fibo(N-2)

2. 겹치는 부분 문제? => yes

3. 이거 완탐인데? 하지만 경우의 수 너무 큰데? 메모이제이션 가능? =>yes

 

[접근]

01> 함수 정의

fibo(N)

02> base condition

n이 memo에 있으면 return

03> 재귀식

(1) n번째 fibo=fibo(n-1)+fibo(n-2)

(2) memo에 n번째 fibo 저장

(3) return n번째 fibo

 

[코드]

memo={
    1:1,
    2:1
}

def fibo(n):
    if n in memo:
        return memo[n]

    nth=fibo(n-1)+fibo(n-2)
    memo[n]=nth
    return nth

print(fibo(99))

---

(2) 계단 오르기

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

 

[ 조건 충족 ]

[접근]

바텀업 DP이므로 순차적으로 데이터 채워나감 => 재귀필요 X

 

[코드]

n=int(input())
List=[]
dp=[]
for _ in range(n):
    List.append(int(input()))

if len(List)>=3:
    dp.append(List[0])
    dp.append(max(List[0]+List[1],List[1]))
    dp.append(max(List[0]+List[2],List[1]+List[2]))

    for i in range(3,n):
        dp.append(max(List[i]+List[i-1]+dp[i-3],List[i]+dp[i-2]))

    print(dp[-1])
else:
    if len(List)==1:
        print(List[0])
    elif len(List)==2:
        print(List[0]+List[1])
    elif len(List)==3:
        print(max(List[0]+List[2],List[2]+List[1]))

(3) 1로 만들기

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

 

[ 조건 충족 ]

1. 겹치는 부분문제?

 N=2 → 2//2 or 2-1

 N=4 → 4//2 -> 2//2 or 2-1

... yes!

 

2. 메모이제이션 가능?

Yes !

 

3. 완탐의 냄새 하지만 범위는 10^6으로 경우의 수가 너무 많다!

 

[ 문제 접근 ]

1. dp[i] = dp[i-1] +1 로 정의 (1을 뺀 기본값 + 1번의 연산횟수)

2. X가 2로 나누어 떨어진다면, min( dp[i], dp[i//2]+1 ) 

3. X가 3으로 나누어 떨어진다면, min( dp[i], dp[i//3]+1 ) 

 

[ 코드 ]

n=int(input())
dp=[0]*(n+1)

for i in range(2,n+1):
    dp[i]=dp[i-1]+1
    
    if i%3==0:
        dp[i]=min(dp[i],dp[i//3]+1)
    if i%2==0:
        dp[i]=min(dp[i],dp[i//2]+1)

print(dp[n])

---

(4) 자두나무

: 상태값이 3개 이상인 경우

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

 

---

[ 백트랙킹 ]

- 백준 N과 M 시리즈 (1) ~ (4)

- n-queens 문제

- 백준 #1182 부분수열의 합