[백준 파이썬 2617번 구슬 찾기] 재귀함수와 동적계획법 DP

모든 재귀함수 문제는 DP로 해결할 수 있다 -> X

2617번: 구슬 찾기

---

재귀함수의 장점

1. 변수를 여럿 만들지 않기 때문에 헷갈리지 않는다
2. 반복문에 비해 코드가 간결하다

재귀함수의 한계

→ 연산 복잡성, 같은 연산을 반복해야한다

-> 시간복잡도가 커진다

 

또한 메모리 문제도 있다.

재귀함수를 사용하면 함수를 호출할 때 메모리에 적재되는 일련의 과정을 거쳐야 하기 때문에 *오버헤드(ovehead)가 발생할 수 있다!

→ 문맥 교환에 비용이 발생한다!

함수를 종료하지 않고 기다리면서 생기는 콜스택의 부하로 인한 메모리낭비가 생긴다

지역변수, 매개변수, 반환값이 process stack에 저장된다.

 

여기서 하나! 꼬리재귀

이러한 메모리낭비 문제를 해결하기 위해 꼬리 재귀(tail call recursion)를 사용할 수 있다. return에서 재귀함수를 호출함으로써 나는 종료하고 재귀함수로 넘어가는 테크닉이 가능하다.

---

[알고리즘] 다이나믹 프로그래밍(DP)에 대해 알아보자! (+Python 구현)

[알고리즘] 다이나믹 프로그래밍(DP)에 대해 알아보자! (+Python 구현)

다이나믹 프로그래밍의 장점

재귀함수에서 반복해서 구해야 했던 연산을 메모리제이션함으로써 중복된 연산을 줄임

이 문제도 나보다 큰 수보다 큰 수의 개수 반복적으로 구해야한다고 생각해서 DP로 사고함

 

하지만 다이나믹 프로그래밍의 진가는 탑다운이 아닌 바텀업에서 나온다

탑다운보다는 바텀업의 성능이 더 뛰어나기 때문에 이번 경우에는 적절하지 않았던 것 같다. (랭커들이 dp로 안풀더라...)

또한 dp의 경우 개수만 기억하기 때문에 만약 같은 부모를 가진 다른 자식들에 연결되어 있을 경우 똑같이 1 + 1로 계산할 뿐 부모가 같을 경우를 고려할 수 없었다.

5 4
1 2
1 3
2 4
3 4

# 이런 경우 처럼 2, 3의 부모가 똑같이 1이기 때문에 4보다 큰 수는
# 1,2,3 이지만 2+1+1로 계산하기 때문에 DP로 풀 수 없다.

>> 맥스 디피 [0, 0, 1, 1, 2, 0]
>> 맥스 디피 [0, 0, 1, 1, 4, 0]

 

→ 앞으로 DP를 생각할 때는 바텀업의 경우만 고려하자

 

DP를 고려해야하는 경우

1. 부분 정복 문제일 경우
   큰 문제를 작은 문제로 나누어 해결해야 할 때
2. 참조적 투명성이 보장되는 경우
   결과값이 입력 값만으로 결정되는 경우를 참조적 투명성
3. 최적부분구조 문제일 경우
   전체 문제의 최적해가 각 부분 문제들의 최적해로 이루어진 경우

기억 안나면 링크 확인하기!

동적 계획법(Dynamic Programming)

---

DP로 풀어보려 했던 시도...

import sys
sys.setrecursionlimit(int(1e9))
input = sys.stdin.readline


def maxDfs(now):
    if max_visited[now]:
        return max_dp[now]

    max_visited[now] = True
    for nxt in max_ls[now]:
        max_dp[now] += maxDfs(nxt)

    return max_dp[now]


def minDfs(now):
    if min_visited[now]:
        return min_dp[now]

    min_visited[now] = True
    for nxt in min_ls[now]:
        min_dp[now] += minDfs(nxt)

    return min_dp[now]


N, M = map(int, input().split())
max_ls = [[] for _ in range(N+1)]
min_ls = [[] for _ in range(N+1)]
max_dp = [0 for _ in range(N+1)]
min_dp = [0 for _ in range(N+1)]
max_visited = [False for _ in range(N+1)]
min_visited = [False for _ in range(N+1)]

graph_set = set()
for _ in range(M):
    u, v = map(int, input().split())
    graph_set.add((u, v))

for u, v in graph_set:
    max_ls[v].append(u)
    max_dp[v] += 1
    min_ls[u].append(v)
    min_dp[u] += 1

for i in range(1, N+1):
    if not max_visited[i]:
        maxDfs(i)
    if not min_visited[i]:
        minDfs(i)

ans = 0
for i in range(1, N+1):
    if max_dp[i] >= (N+1)/2 or min_dp[i] >= (N+1)/2:
        ans += 1

print(ans)