아리곤듀의 개발 성장 일기

다이나믹 프로그래밍: 하나의 문제를 단 한번만 풀도록 하는 알고리즘

ex) 피보나치 수열

어떨 때 사용? 

1. 큰 문제를 작은 문제로 나눌 수 있을 때 - 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤 처리

     -> 이 과정에서 메모이제이션(memoization) 사용해야함: 이미 계산한 결과를 배열에 저장

2. 작은 문제로부터 구한 결괏값을 큰 문제에서도 활용 가능

2가지 문제 풀이 방식

1. 상향식(바텀 업) 방식: 가장 작은 문제의 답부터 찾아가는 방식, 반복문 사용

2. 하향식(탑 다운) 방식: 가장 큰 문제부터 시작하여 작은 문제 순으로 답을 찾아가는 방식, 재귀 함수 활용

1. 상향식(바텀 업) 방식

# 계산된 결과를 memoization 하기 위해 리스트 초기화
d = [0] * 100

d[0] = 1 # a_1 = 1
d[1] = 1 # a_2 = 1

# 바텀 업 방식: 반복문 활용
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

n = 99
print("fibo({}): {}".format(n, fibo(n)))

2. 하향식(탑 다운) 방식

# 계산된 결과를 memoization 하기 위해 리스트 초기화
d = [0] * 100

# 탑 다운 다이나믹 프로그래밍 기법과 재귀 함수를 활용한 피보나치 수열 구현
def fibo (x):
    # 종료 조건 (전달인자가 1 또는 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    
    # 계산된 결괏값이 존재할 경우 해당 결과값 반환
    if d[x] != 0:
        return d[x]
        
    # 계산된 결괏값이 존재하지 않을 경우 피보나치 수열의 결과를 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

n = 99
print("fibo({}): {}".format(n, fibo(n)))

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

- 유형: 그래프 문제 -> DFS(깊이 우선 탐색)/BFS(너비 우선 탐색)

   - DFS: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동/ BFS 보다 느림

   - BFS: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

* DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

​

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.

둘 중 편한 것을 사용하시면 됩니다.

​

2) 경로의 특징을 저장해둬야 하는 문제

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

3) 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도 

- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

2022.10.12 수요일

이코테 p.178-181

yo = int(input())

_list = []
for i in range(yo):
    _list.append(int(input()))

_list = sorted(_list, reverse=True)
for a in _list:
    print(a, end=' ')

std = int(input())

std_inf = []
for i in range(std):
    std_inf.append(input().split(' '))

# std_inf = [['ㅎ', 95],['ㅇ','77']]
for i in range(len(std_inf)):
    std_inf[i][1] = int(std_inf[i][1])
    
sort = sorted(std_inf)

for i in range(len(sort)):
    print(sort[i][0], end=' ')

❤️문제

책 이것이 코딩테스트다 p.110

구현문제.

❤️내코드

n = int(input())
move = map(str, input().split(" "))
# n = 5
# move = ["R", "R", "R", "U", "D", "D"]

ga, se = 1, 1 

for i in move:
    if i == "R":
        if ga == n:
            pass
        else:
            ga += 1
    elif i == "U":
        if se == 1:
            pass
        else:
            se -= 1
    elif i == "L":
        if ga == 1:
            pass
        else:
            ga -= 1
    elif i == "D":
        if se == n:
            pass
        else:
            se += 1
            
print("%s %s" %(se, ga))

❤️ 문제

이것이 코딩테스트다 p.99 

그리드 문제. 

❤️ 코드

아....또 map 함수 까먹었었다. ㅠㅠㅠ 당 장 기 억 해 라 

map(인자값 형식, 인자값)!!!

n, k = map(int, input().split(" "))

count = 0

while n > 1:
    if n%k==0:
        n = n//k
        count += 1
    else:
        n = n - 1
        count += 1

print(count)

❤️ 문제

이것이 코딩테스트다 p.92

그리드 문제.

❤️풀이

처음 내 풀이,, map함수를 모르고 썼을때다

values = list(str(input()).split(" "))
lst = [2,4,5,4,6]
# lst = [3, 4, 3, 4, 3]


n = int(values[0])
m = int(values[1])
k = int(values[2])

ans, cnt = 0, 0

lst.sort()
first = lst[-1]
second = lst[-2]

while cnt < m:
    if first == second:
        ans +=first*m
        cnt += m
    else:
        ans += first * k
        cnt += k 
        ans = ans + second
        cnt += 1
print(ans)

이제 map 함수 기억하자~!! 아래는 적용 후

n, m, k = map(int, input().split())
lst = list(map(int, input().split()))

ans, cnt = 0, 0

lst.sort()
first = lst[-1]
second = lst[-2]

while cnt < m:
    if first == second:
        ans +=first*m
        cnt += m
    else:
        ans += first * k
        cnt += k 
        ans = ans + second
        cnt += 1
print(ans)