저는dfs/bfs를 많이 선호하다보니 아래와 같은 코드를 작성했는데 다른분 공부에 도움이 될까해서 코드 및 생각 적어봅니다 38:48 문제에 대해서 아래와 같이 최적값을 계속 업데이트 하는 방법으로 풀이가 가능한데 이경우 결국 최적값이 아닌 결과값또한 계산을 하는과정이 필요해 연산 낭비가 될 수 있어 풀이해주신 바텀업 방식이 효율적으로 보이네요 from collections import deque def ans(x): options = [ lambda x : x%5 == 0, lambda x : x%3 == 0, lambda x : x%2 == 0, lambda x : True ] actions = [ lambda x : x//5, lambda x : x//3, lambda x : x//2, lambda x : x-1 ] dic = dict() queue = deque([x]) dic[x] = 0 while queue: k = queue.popleft() for option, action in zip(options, actions): if option(k): nk = action(k) if nk < 1: continue if nk not in dic or dic[nk] > dic[k] + 1: dic[nk] = dic[k] + 1 queue.append(nk) return dic[1]
화폐나누기 문제는 바텀업으로 풀어봤는데 기록용으로 적어봅니다 def ans(N,M,array): mina = min(array) if M < mina: return -1 dic = dict() for i in array: dic[i] = 1 for i in range(mina, M+1): for j in array: if i not in dic: if i - j in dic: dic[i] = dic[i - j] + 1 else: if i - j in dic: dic[i] = min(dic[i], dic[i - j] + 1) return dic.get(i, -1)def ans(N,M,array): mina = min(array) if M < mina: return -1 dic = dict() for i in array: dic[i] = 1 for i in range(mina, M+1): for j in array: if i not in dic: if i - j in dic: dic[i] = dic[i - j] + 1 else: if i - j in dic: dic[i] = min(dic[i], dic[i - j] + 1) return dic.get(i, -1)
금광 문제부터 혼자 푸는데에 한계 느꼈습니다. 코드 구현은 커녕 아이디어 한참 고민하다가 절대 안 될 것 같아서 해설 보면 허탈하고 ㅋㅋㅋ 그래도 아이디어만 있으면 구현은 문제 없는 정도라 지금 단계에서는 정말 문제 유형을 많이 보는 게 도움이 될 것 같습니다. 예시 문제 많이 뽑아주셔서 감사합니다 ㅠㅠㅠㅠ
화폐 구성하기 문제를 이렇게 풀어봤는데 혹시 오류된 부분 있을까요? n,m = map(int,input().split()) k = [] for i in range(n): k.append(int(input())) a = [10001] * (m+1) for i in k: a[i] = 1 a[0] = 0 for i in range(len(a)): for j in k: a[i] = min(a[i],a[i-j] + 1) print("Ans: ", a[m])
57:16 금광 문제에서 i ==0 일 때 left_up = 0인 이유는 i의 좌표가 0 일 때는 left_up이 존재하지 않는다. 마찬가지로 금광의 행의 최대 값인 n (예제에선 3)에서 n-1은 dp 테이블의 가장 아래의 값에 위치할 때의 좌표이기 때문에 left_down이 존재하지 않는다. left의 값은 i의 어떤 값이든 존재한다.
라이브 방송보면서 생략된 부분 다시 들으면서 공부중인데 30001이 그냥 30000을 포함하기 위해 잡으신거네요. 저 코드에서 *30001대신 30002 30003..을해도 결과값은 똑같이 나오는걸 알 수 있습니다. 개인적으로 30000을 곱해도 똑같이 결과값이 나오는것으로 보아 30000을 그냥 해도 될거같긴한데 그냥 포함하는 느낌으로 +1이상 곱하는게 괜찮을거같습니다. 영상에서도 그렇게 했고요.
dp중 정수 삼각형의 경우 백준 사이트에도 똑같은 문제가 있습니다 하지만 이코테 코드로 제출시 문제가 틀렸다고 나옵니다(예제1은 맞다고 나옴) 다른 정답을 본결과 삼각형 2열에서 수가 2개만 존재하기 때문에 왼쪽,오른쪽 끝일때 0을 더하게 되어 값이 되물림 안된다고 생각을 했지만 그렇다면 예제 1이 맞을 수가 없어서 이해가 잘 안되서 댓글을 달아봅니다
만약 마지막 병사세우기 문제가 코딩테스트로 출제되었을 때 이렇게 1차원 적으로 접근하면 안되나요..? n = int(input()) array = list(map(int, input().split())) result = 0 for i in range(1, n-1): j = i-1 if array[i]>=array[j]: array.remove(array[i]) result += 1 print(result)
dynamic optimization을 수학적으로 푸는 방식을 dynamic programming 이라고 합니다. 마찬가지로 Linear optimization을 수학적 으로 푸는 방식을 Linear programming이라 하고 Stochastic optimization을 수학적 으로 푸는 방식을 Stochastic programming라고 합니다. 이외에도 nonlinear programming, quadratic programming, Stochastic programming 등등이 있고.. 그래서 동태적 최적화 문제를 수학적으로 푸는 방식을 dynamic programming 이라고 합니다. 핵심 아이디어는 벨만 최적성 원리이고 그 아이디어에 따라서 optimal substructure가 나오게 됐습니다. 간단하게 말하면 부분적으로 순간순간 매 time step step마다 최적의 결정을 내린다면 그 결정들의 set (policy)은 최적의 결정이 된다는 것이 벨만의 최적성 원리에 대한 아이디어입니다. 그래서 dp로 그래프 문제를 풀면 계속 구조를 잘잡으면서 푸니까 가중치때문에 꼬여서, 했던 계산을 또 하는 문제를 해결할 수 있습니다.
!["누가 5학년 담임을 맡을 건가" '용기 낸' 14년차 교사의 최후 [뉴스.zip/MBC뉴스]](/img/1.gif)
정말 거짓말안치고 이강의를 듣고 눈물을흘리며 기립박수를 쳤습니다.
너무 훌륭한 강의입니다 ㅜㅜㅜ
이런 양질의 강의가 무료라니.. 감사합니다
취준생인데 정말 감사히 보고있습니다ㅠㅠㅠ
2024년에 보고 계신 분..
와,, 이전까지는 문제를 풀 수 있었는데 이번 강의는 힘겹네요 잘 듣고 있습니다 좋은 강의 감사합니다:)
(개인적인 메모입니다)
36:34 문제2] 풀이 이해 안 됨.
38:48 그리디 방식과의 차이점 이해 안 됨. 그냥 관점이 다르다는 건가?
43:36 문제3] 효율적인 화폐 구성
코테 입문으로 정말 최고입니다
진짜 DP 때매 한참 잘 학습하다가 알고리즘 풀이 접었음 ㅜ ㅜ 구현문제보다도 훨씬 어려운데 문제를 많이 풀어봐야 하나봄..
DP, 분할정복, 퀵정렬 23:01
ㅡ 개미전사 26:49
ㅡ 1로 만들기 36:07
이해가 너무 잘가네요. 감사합니다
37:35 오늘 여기까지~! 강의 너무 좋습니다 ㅎㅎ
저는dfs/bfs를 많이 선호하다보니 아래와 같은 코드를 작성했는데 다른분 공부에 도움이 될까해서 코드 및 생각 적어봅니다
38:48 문제에 대해서 아래와 같이 최적값을 계속 업데이트 하는 방법으로 풀이가 가능한데
이경우 결국 최적값이 아닌 결과값또한 계산을 하는과정이 필요해 연산 낭비가 될 수 있어 풀이해주신 바텀업 방식이 효율적으로 보이네요
from collections import deque
def ans(x):
options = [
lambda x : x%5 == 0,
lambda x : x%3 == 0,
lambda x : x%2 == 0,
lambda x : True
]
actions = [
lambda x : x//5,
lambda x : x//3,
lambda x : x//2,
lambda x : x-1
]
dic = dict()
queue = deque([x])
dic[x] = 0
while queue:
k = queue.popleft()
for option, action in zip(options, actions):
if option(k):
nk = action(k)
if nk < 1:
continue
if nk not in dic or dic[nk] > dic[k] + 1:
dic[nk] = dic[k] + 1
queue.append(nk)
return dic[1]
화폐나누기 문제는 바텀업으로 풀어봤는데 기록용으로 적어봅니다
def ans(N,M,array):
mina = min(array)
if M < mina:
return -1
dic = dict()
for i in array:
dic[i] = 1
for i in range(mina, M+1):
for j in array:
if i not in dic:
if i - j in dic:
dic[i] = dic[i - j] + 1
else:
if i - j in dic:
dic[i] = min(dic[i], dic[i - j] + 1)
return dic.get(i, -1)def ans(N,M,array):
mina = min(array)
if M < mina:
return -1
dic = dict()
for i in array:
dic[i] = 1
for i in range(mina, M+1):
for j in array:
if i not in dic:
if i - j in dic:
dic[i] = dic[i - j] + 1
else:
if i - j in dic:
dic[i] = min(dic[i], dic[i - j] + 1)
return dic.get(i, -1)
병사배치 문제에서 array를 뒤집는 이유가 있나요? 뒤집지 않더라도 결과값은 잘 나오는 것 같습니다.
금광 문제부터 혼자 푸는데에 한계 느꼈습니다.
코드 구현은 커녕 아이디어 한참 고민하다가 절대 안 될 것 같아서 해설 보면 허탈하고 ㅋㅋㅋ
그래도 아이디어만 있으면 구현은 문제 없는 정도라 지금 단계에서는 정말 문제 유형을 많이 보는 게 도움이 될 것 같습니다.
예시 문제 많이 뽑아주셔서 감사합니다 ㅠㅠㅠㅠ
병사배치 설명 비명지르면서 봤습니다 엉엉엉엉 너무 이해하기 쉽게 알려주셔서 감사합니다
좋은 강의 감사합니다. 다이나믹 프로그래밍 학교에서 예전에 배우긴 했었는데 실제 문제에서 어떻게 쓰는지는 감이 잘 안잡혔는데 강의보고 알고리즘 문제들 풀어보니까 생각보다 범용적으로 적용할 수 있는 방법이었네요.
양질의 강의 잘 보고 있습니다. 꾸준히 볼께요. ^^ (1회 완강)
동빈선생님 덕분에 다이나믹프로그래밍 문제 푸는게 넘 재밌어졌습니다..감사합니다 ㅠㅠ
정말요? 부럽습니다...
화폐 구성하기 문제를 이렇게 풀어봤는데 혹시 오류된 부분 있을까요?
n,m = map(int,input().split())
k = []
for i in range(n):
k.append(int(input()))
a = [10001] * (m+1)
for i in k:
a[i] = 1
a[0] = 0
for i in range(len(a)):
for j in k:
a[i] = min(a[i],a[i-j] + 1)
print("Ans: ", a[m])
작은문제답을모아 큰문제해결할수잇을때, 중복되는 부분문제일때 dp 사용 > 하향식 :메모이제이션 캐싱, 피보나치 ex 계산한적잇는 dp테이블 재귀에종료조건 리턴, 아니면 점화식. 상향식은 반복문 점화식 o2n 지수에서 on됨
추석에 강의 찍고 편집하시고 계시군요 ~ 대단하십니다 ~
항상 잘 보고 있습니다
57:05 금광 문제는 완전탐색인건가요..?
병사 문제 조금 의문이 있는데 혹시 병사번호 3번 병사 7번 병사 열외시켜도 오름차순 으로 나머지 병사들 정렬되있고 5명이 남는데 무슨차이죠 ?..
bfs에서 visit array를 사용하여 중복되는 경우(visited)를 배제하는 것도 일종의 다이나믹 프로그래밍이라 볼 수 있지않을까요
채굴 문제에서 배열을 모든 방향으로 한개씩 더 추가해서 점화식을 별도로 설정하지 않아도 0만 더해지게 한다면 더 좋은 코드일까요, 아니면 메모리낭비의 코드일까요? 답변 부탁드립니다!
자세한 설명 정말 감사합니다
설명을 들으면 간단하게 처리되는 걸 알수 있다. 허나 설명을 안보고 직접 하려고 하면 넘 어렵다. 기초가 얼마나 되야 직접 풀 수 있을까?
식량 털기 문제에서 a (i-1)을 i-1창고를 털었을때 최대식량인가요 ? i-1창고를 털던 안털던 그냥 그까지 참고했을때 최대값인가요 ? 코드상, i-1번째 창고를 털던말던 상관없이 그냥 최대값인데 그럼 그냥 a (i-1)
감사합니다 잘봤습니다 그런데 어쩔때는 d[100] 이런식으로 활용하시고 어쩔때는 vector를 사용하시늗네 기준이 따로 있으신건가요?
효율적인 화폐 구성 문제에서요, 점화식을 보면 목표 금액마다 화폐 단위를 모두 확인하고 그 중 최소 값을 구하는데, 왜 실제 코드에서는 반복문 위치가 반대로 됐으며 답이 맞는 이유가 뭔가요? 그게 헷갈려서 이해가 안되네요ㅠㅠ
57:16 금광 문제에서
i ==0 일 때 left_up = 0인 이유는
i의 좌표가 0 일 때는 left_up이 존재하지 않는다.
마찬가지로 금광의 행의 최대 값인 n (예제에선 3)에서
n-1은 dp 테이블의 가장 아래의 값에 위치할 때의 좌표이기 때문에
left_down이 존재하지 않는다.
left의 값은 i의 어떤 값이든 존재한다.
감사합니다
그저갓..빛동빈...✨
1로 만들기 진짜 놀랍습니다. 실제로 이런 문제가 나오면 제 머리로 이걸 구상할 수 있을지가 의문이네요...
동빈님도 처음엔 이러한게이해가 잘 안되셨나요? 처음이라 그런지 이해가 잘 안되네요
백준에 있는 문제인가요? 문제 번호 아시는 분?
1로 만들기 문제가 그리디 알고리즘으로 해결 가능하다고 해도 다이나믹으로 해결하는게 더 헷갈리지 않게 되는건가요?
동영상에서 2와 3으로 나누는 것을 적절히 섞는다면 최적의 해를 구할 수 있다고 하네요
효율적인 화폐 구성에 점화식에 대한 설명이 거의 없으셔서 이해가 잘 안가네요ㅠㅠ
31:00 에서 그림 아래부분을
(i-2) 여기를 털면 >> (i-1) 여기를 안털면
으로 수정하는게 조금 더 정확한 설명이 아닐까요??
41:25 에서 dp테이블 범위가 왜 30000이 아니라 30001이 되나용??
d[0]은 최적의 값을 찾을 필요가 없는 값이니 0으로 두고 1부터 세서 30000개(d[1] ~ d[30000])를 생성하려는 목적이에요
라이브 방송보면서 생략된 부분 다시 들으면서 공부중인데 30001이 그냥 30000을 포함하기 위해 잡으신거네요. 저 코드에서 *30001대신 30002 30003..을해도 결과값은 똑같이 나오는걸 알 수 있습니다. 개인적으로 30000을 곱해도 똑같이 결과값이 나오는것으로 보아 30000을 그냥 해도 될거같긴한데 그냥 포함하는 느낌으로 +1이상 곱하는게 괜찮을거같습니다. 영상에서도 그렇게 했고요.
이거 이해못하면 어떤걸 공부해야하나요 점화식세우는거 부터가 너무 어려워요 ㅠㅠㅠ
DP는 원래 학부생 수준에서 배우는 알고리즘 중에 가장 어려운편에 속합니다 원래 어려워요
다양한 종류의 DP유형을 최대한 많이 접하는 수 밖에 없습니다. DP버리면 코테 안정권은 포기해야 됩니다
@@아무나-v4c 감사합니다 천천히 다시 공부해야겟네요 ㅠㅠ
dp중 정수 삼각형의 경우 백준 사이트에도 똑같은 문제가 있습니다 하지만 이코테 코드로 제출시 문제가 틀렸다고 나옵니다(예제1은 맞다고 나옴) 다른 정답을 본결과 삼각형 2열에서 수가 2개만 존재하기 때문에 왼쪽,오른쪽 끝일때 0을 더하게 되어 값이 되물림 안된다고 생각을 했지만 그렇다면 예제 1이 맞을 수가 없어서 이해가 잘 안되서 댓글을 달아봅니다
감사합니다. 코테 준비중인데 큰 도움이 되고있네요. ㅎㅎ
감사합니다!!
1로 만들기 코드 이해가 안갑니다..ㅜ
두 번 들으니 이해되네요..
강의 잘 보고 있습니다. 질문같은거는 댓글로 남겨도 안남겨주시는데 다른데다가 해야하나요?
요즘은 graphql이랑 리액트 하느라 자주 못 들어왔네요
책갈피 : 26:47
강의 잘 보고 있습니다.!
강의 잘 보고 있습니다. 감사합니다
블로그에 정리 해두고 싶은데, 출처 남기고 내용 퍼가도 될까요?
금광 문제부터 52:30
감사합니다
컴공에게 dp는 이것이다
만약 마지막 병사세우기 문제가 코딩테스트로 출제되었을 때 이렇게 1차원 적으로 접근하면 안되나요..?
n = int(input())
array = list(map(int, input().split()))
result = 0
for i in range(1, n-1):
j = i-1
if array[i]>=array[j]:
array.remove(array[i])
result += 1
print(result)
2 4 3 1이 반례가 될것같습니다. 해당 알고리즘으로 풀이한다면 2 4 3 1-> 2 3 1-> 2 1이 되어버리는것을 확인하실 수 있을겁니다
문제 그래프나 이해는 되는데
문제 풀이 코드로는 이해가 안간다
강의 퀄리티는 쵝오인데 머리가 이해 못해 밉다
이책 모든 목차가 강의로 만들어져 있는 건가용 ..?
박노아 넵. 정확히 말하자면 전에 라이브하신걸 사용하신걸거에요
14:00
45:00
2:00 dynamic이 별 의미 없이 사용된 단어라니요 @ㅅ@ Bellman이 슬퍼하겠어요
dynamic optimization을 수학적으로 푸는 방식을 dynamic programming 이라고 합니다.
마찬가지로 Linear optimization을 수학적 으로 푸는 방식을 Linear programming이라 하고
Stochastic optimization을 수학적 으로 푸는 방식을 Stochastic programming라고 합니다.
이외에도 nonlinear programming, quadratic programming, Stochastic programming 등등이 있고..
그래서 동태적 최적화 문제를 수학적으로 푸는 방식을 dynamic programming 이라고 합니다.
핵심 아이디어는 벨만 최적성 원리이고 그 아이디어에 따라서 optimal substructure가 나오게 됐습니다.
간단하게 말하면 부분적으로 순간순간 매 time step step마다 최적의 결정을 내린다면 그 결정들의 set (policy)은 최적의 결정이 된다는 것이 벨만의 최적성 원리에 대한 아이디어입니다.
그래서 dp로 그래프 문제를 풀면 계속 구조를 잘잡으면서 푸니까 가중치때문에 꼬여서, 했던 계산을 또 하는 문제를 해결할 수 있습니다.
43:51
개같은 세상.. 피 맺히는 음악..ㅋ
감사합니다!!
43:29
42:38
43:23
43:03
24:37
43:52
52:30
38:41