동적 계획법: 역방향 라벨링과 비용 계산

공적교육법이 기본적인 아이디어가 문제를 시작해서부터 푸는 겁니다. 마지막 단계에서부터. 영말자 문제를 보면 이 과정을 어떻게 시작했는가 하니. 마지막 단계, 직전 단계부터 시작했어요.

스테이지 파일과 상태 제 2개 상태 에이에서 그 제 2까지 가는 가장 취급 최소 비용 최단 경로를 찾는데 a 부터 시작을 하는 게 아니라 이 알고리즘이 동쪽 계획법 알고리즘이 어디서 시작하는 거니 4단계에 있는 h 하고 아이 부터 시작되어 있지

거기에서 어디로 가야 되느냐 하는 결정과 그 다음에 최종 목적지까지 거리가 비용이 어떻게 되느냐를 레이블로 저렇게 하이라이트에서 박스를 하고 저 위에다 푸시하단 말이야. HV에다가는 표시하고 IR에다가도 표시하고 저 레이블만 결정을 했으면 그 다음 한 단지 앞으로 가서

3단계에서 EFG에 있을 때 어떤 결정을 해야 되는가를 또 결정할 수 있습니다. 그래서 그 성냥개비 예제를 들었던 게 동적계획법이 이 역마차 문제는 앞에서 시작해도 내 뒤에서 시작해도 상관없어요. 어떤 문제들은 방향성과 관계없이 풀 수 있는 문제들도 있어. 그런데

또 다른 어떤 문제들은 반드시 끝에서부터 거꾸로 풀어야지만 답을 쉽게 구할 수 있고 앞에서부터 복잡하게 시작하면 계산이 엄청 복잡해지는 그런 문제들이 있다 이거야 오케이? Subtraction 게임, 성령게비 놓고 하는 게임이 그런 겁니다. 마지막 상태를

타겟을 정해놓고 그 전에 어떻게 해야 되는지 그럼 그 전전 단계에서는 어떻게 되는지 이걸 거꾸로 역추적 백트래킹해서 아 그럼 맨 처음 시작할 때 어떻게 해야 되겠구나를 거꾸로 결정 역방향으로 결정한 예를 들은 겁니다 오케이? 이 문제는 역방향이든 포워드든 백워드든 either way 풀 수 있지만

기본적으로 역방향으로 품다 이거지 어떤 문제들은 역방향으로 역방한 이 거꾸로 풀어야지만 쉽게 풀려 문제 되기 때문에 기본적으로 나이를 프로그램 하면 거꾸로 이렇게 한다 이거예요 아 이걸 설명하는 게 또 하나 설명할 수 있는 게 성령 깨비 문제 말고 또 하나

어 하노이 타오라는 게 있어요. 하노이. 베트남에서 올라서 하노이에 타오가 있어 진짜?

This is the first one. The first one is that you can only move one disc at a time. And the second is that a bigger disc can never sit on a smaller one. So start by moving the smallest disc to the right. Then make the only legal move that isn't the smallest disc. And move the smallest disc to the right again. So now place disc three in the middle and whenever the smallest reaches the end, move it back to the first end.

This allows you to move disc 2 to the middle since it's smaller than disc 3. Then move the smallest to the right on top of the middle stack, and make the next legal move by placing disc 4 on the last peg. Now repeat those two steps, moving the smallest disc, then the bigger one, and moving the smallest back to peg 1. And keep going until the whole tower is rebuilt on the other side. This kid is playing a- You have to move all four disks to a

뭐 하는지 알겠어요? 네 비슷한 얘기입니다 어쨌든 간에 알고리즘은 기본적으로 레이블링을 하는 거다 마지막 단계부터 거꾸로, 마지막 단계는 5단계인데 5단계는 결정할 필요가 없죠 4단계에서 어떤 결정을 해야 되느냐 그러면 4단계 결정을 기초로 3단계에서 어떻게 해야 되느냐

그런 식으로 이렇게 한 단계 한 단계 어 시작하는 제 상태로까지 이제 거꾸로 오는 겁니다 4단계에서도 사실 뭐 할 것은 없어서 선택은 없어요 무조건 어 hg 수지의 와야 되는 거 아예 수질을 반으로 가는 겁니다 근데 이제 한 단계 이제 상단계 앞으로 이제 한 단계 앞으로 오면 선택을 해야 되는데 2에서 이 집안을 안 맞게 하고 또 어떻게 생각하는 거 아니 바로 h 하고 아예 이 입을 가지고서 결정한 데가 이 치아 아예 입을 플러스

2에서 이 치가 2에서 아이까지 가는 거리 거에서 ok 여기 이 치유의 숫자가 제1항 3 이란게 나타내는 게 뭐냐 그 똑같은 형식으로 3단계에 있는 이 fg 에다가도 내일링을 똑같이 할 건데 일단 h 위에 제2가 나타나는 게

바로 h 에서 바로 그 다음에 가야 될 목적지를 나타내요 그걸 알아야지 그 다음에 3 이라는 숫자는 h 에서 최종 목적지 그 뒤로 뭐 몇 단계가 있든지 관계없어요 일단 h 에서 그 다음 단계 제의로 가고 제의도 우리는 내 조건 아니까 다음에는 제의 하나밖에 없지만은 여러개가 있어서 상관없어 h 에서 일단 다음 단계는 제의라는 상태로 간단한 것과

H에서 J로 가게 되면 최종 목적지가 우린 J라는 걸 알지만 J가 아니라 뭐가 몇 단계 뒤에 있다 하더라도 최종 목적지까지 최소 비용이 3이다라는 겁니다. 그게 저 레이블이 나타내는 거예요. 그거를 EFG에다가 똑같은 형식으로 라벨을 붙여줄 거야.

그 2개에 붙어있는 라벨은 뭐냐? H하고 4인데 H는 2에서 다음 단계는 H라는 상태로 갈아입어야 뭐 여러 상태로 몇 개가 이든지 방금 없이 H로 갈아입어야 그런데 몇 개가 해서 H랑 I 둘 중에 H로 갈아입어야 하지 말고 그러면 H,4는 뭐냐?

H로 가면 E에서부터 최종 목적지까지 최소 비용이 4다라는 거예요. understood? 네. 됐습니까? 네. 자 그러면 E에서 저 레이블 H,4라는 걸 어떻게 결정하느냐? 다른 정보 다 필요 없어요.

h 위에 있는 제이 콤마 뜰 이란 아이 밑에 있는지 콤마 사랑은 저의 입을 그리고 2에서 h로 갈 때 거리가 1로 되어있고 아예 갈 때 4라인 5 숫자만 알면은 2의 이그를 h 콤마 사랑을 결정할 수 있다 어떻게 그 앞에 있는 곳도 녹 노란 저 녹색 홍광색

1 더하기 3 4 더하기 4 했더니 작은 게 뭐냐? 1 더하기 3 4다. 그래서 H로 가고 최종 목적지까지 총 비용이 4다라는 거야. H까지 가는 게 4다네. H까지 가는 게 1밖에 안 들이죠. 비용이. H까지 가는 데 1이 들고 2에서 H까지. 그 다음에 거기서 최종 목적지.

원의 1이 것까지 3이 된다 이거예요 자 그 다음에 f도 똑같이 할 수 있어 h나 i로 둘 중에 한군데 선택해야 되는데 어디에 어디로 가는게 좋냐 f에서 h가 6이고 f에서 i가 되는 3이에요 자 거기에다 h로 갔을 때 그 다음에 추가되는게 3이라 이거예요 이거랑 이거랑

이거 더 와서 작은 걸 골라 주는 거죠. 이게 9, 이게 7이니까 7이고 이거가 이게 뭐예요? 이게 I로 가는 거란 거지. 여기는 이거 더하면 4하고 이거 더하면 8인데 어디로 갔나? 이 앞에가 H고 뒤에가 I예요.

아는 주에서는 이가 출구 7인 2개의 2시 아예 아예 아예 아예 아예 아예 칠하는 거죠 이렇게 말 그래서 내 입을 저렇게 h 콤라 5 아예 마스에 볼 때 이침 마스스 저렇게 내부니 되면 그 다음에는 4단계 h 아예 그거는 더 이상 필요 없고

에프지에 레이블만 있으면 그 앞 단계에 있는 결정을 또 할 수 있다 그런식으로 반복하는 겁니다 어디까지 a 까지 갈 때까지

질문이 있어요? 질문 없죠? B에서는 어디로 간다? E, F, G로 갈 수 있는 세 개 비교해 보니까 어떻게 하는 게 좋아? E나 F로 가든지 비슷한 거죠? 네 알기로 E로 갈 때

에 프로 할 때 주요 갈 때 이게 11 11 12 그러니까 이하고 에프 어딜 받은 11만 갈 수 있어 어디까지 최종 목적지 까지 11 이라는 거야 2에서 에 따뜻이 에서 2로 가는 것 7 밖에 안 되지 2 7에다 4를 더 미사가 최종 목적지까지 라는

그리고 요 h 은 그 다음에 를 잃지로 가는 거야 그 다음에 또 어디로 가든지 이 미소는 뭐 그 다음 여기 가면 이제 여기서 제 2로 가라는게 또 있고 오케이 여기서 일단 b 에서는 2 2로 가라야 되지 c 도 마찬가지 fc 로 가든걸 비교해 보면

7 9 10 이다 이거야 그러니까 7로 가는게 좋고 2로 가는게 좋다 이거지 얘는 8 8 11이에요 EFG 그러니까 앞에 두개로 선택하면 되는거지 그래서 네이블을 다 했죠 네이브를 끝나면 또 한 가지 더

이제는 그 뒤에 여기 뭐가 있든지 상관없이 여기에 모든 필요한 정보가 다 있어 SD EFG 그 다음에 EG를 몰라도 돼 FG 그 다음에 HI 몇 단계에 있든지 이거는 사실 상관없어 이제

이 부분은 몰라도 상관없는데 이것만 결정하면 돼. A에서 어디로 갈지. 그럴 때 최종 목적지까지 총 비용이 이게 A에서부터 최종 목적지까지 총 비용이다. 최소 어떻게? 2인 10일 더하면 33, 11, 11. 어디로 가면? C, C, D. C나 D로 가면 최종 목적지까지 비용이 11로 해결이 됩니다.

그럼 b로 가면 어떻게? c나 d로 가면 c가 보니까. 아, e나 e로 가면 d로 가면 d로 가면 d로 가면 d로 가면 d로 가면 d2나 f 둘 중에 아무데로 가면 됩니다. backtracking을 하면 최소 비용으로 갈 수 있는 경로가 몇 개가 나오나요? 몇 개? 세 개가 나오지.

A C E H J 이렇게 가도 되고 A D E H J 가도 되고 그 다음에 A D F I J 가도 되고 그 비용은 지금 자 이게 동적교육법이고요

자 이거를 이제 시험 문제는 그림을 이렇게 하라고 하면 채점하게 복잡하고 여러분도 힘든게 복잡하겠죠 요 표를 채워야 돼요 시험에서 이게 두개가 함께 돼 있어야 되는데 지금 여기서 시작해서 이렇게 하면 끝나는 겁니다 근데 여기는 숫자를 보면 다 이 그림에서 나왔던 숫자야

여기서 했던 것을 여기다 오수자들이 좀 이게 막 보고도 하고 모두가 부정에서 가장 작은 거 보고 한거 가만히 앉아 갖고 여기 나와 있는 숫자들 하고 그 다음에 이 표현 수자들을 잘 비교해 보세요 어떻게 채워야 될지를 어렵지 않게 판단할 수 있을 거예요

마지막 한 곳에 모두에게 마지막 마지막이고 에이에서 어디로 가야 되느냐 bcd 로 가야 되는 도중에 어디로 가야 되느냐 하는 거를 bcd 에 있는 전의 입을 노란색 박스에 있는 것들을 보고서 그 다음에 a 에서 bc들만 2사상 고수 자랑 가지고 한 거란 말이야

243 1178 243 1178 여기 있잖아요 지금 243 1178 이게 A에서 B로 가는 거 이건 B에서 J까지 이건 A에서 C 그다음에 이건 C에서 J

A에서 D, D에서 G. 그렇게 했는데 어디가 최소야? 그래서 C 또는 D로 가요. 그리고 이거는 뭐 A에서 J까지 총 최소 구경입니다. 참을 수 있겠죠? 네. 그럼 2단계. 물론 우리는 거꾸로 왔지만

이게 뭐겠어 B에서 E 그 다음에 이거는 E에서 G 이거는 B에서 F F에서 G 이건 B에서 G G에서 G 그지에서 짜는게 뭐다? 10이라고 10이고 그래서 어디로 가나? B에서는 E나요

그래서 여기 11, 17, 8 이게 어디에 사용이 돼? 이 레이블이잖아 이게 묶어서

요게 부품이 아까 레이블이잖아요. 물론 수송받고 EF하고서 11 그렇게 되어있었지. 그 다음은 EJP, COMA, J2. 맞죠 레이블? 저의 BCD의 레이블이에요. BCD 레이블 맞아요?

BCD 박스, 노란 박스 BCD 위에 있는거 그거랑 여기쯤, 그래서 그거랑 똑같잖아요 끝에 있는거 이것도 똑같이 A의 레이블이야 이게

여기도 마찬가지 ES ES ES ES

FGLABRE 4H4I7H6 이렇게 되어 있는데

- Okay.

- Sorry, you got to go watch it.

위에서

자, 이 밑에 나와 있는 표에 1 더하기 3은 4, 4 더하기 4는 8, 그게 저 위에 있잖아요. 그래서 4를 고르는 거에요. 9하고 7 중에서 7을 고르는 거에요. 6하고 7 중에서 6 고르는 거에요. 어쩔을 때 H로 가고 I가 갈 때 이게 목적지에요. 자, 그러면 이제 먼저 여기서 이것들을 설명하고 그 다음에 이제 이 표를 설명했어야 되는데 거꾸로 여러분들은 이거 기호부터 설명하면 너무 어지러우니까 이 표에 나와 있는 기호들을 보고 거꾸로 그 기호들의 의미를 생각해 보라는 말씀이지.

일단 n 2 4 3 이렇게 남아야 되는 뭐예요 스테이지 얘는 스티지야 그 다음에 s 4 가 있고 x 4 가 있어 s 는 그냥 상태라고 4 단계에 있는 상태 그럼 x 는 뭘까 x 는 대개 의사 결정이란 말이지 4 단계에서

3 의사결정이에요 근데 의사결정이라는게 h 에 있을 때 결정하는 거라 아예 있을 때 결정하는게 다르겠죠 x 이 일단 x 4 스타가 2분 이렇게 되는 꼭 좀 확률으로 주시면 s 4 주어져 있을 때 x 4 결정하는 겁니다 물론 선택은 두가지 각 여기서 선택이 하나밖에 없으니까 그냥 무조건 제 2야 근데

3단계에서 보면 2에서 갈 수 있는게 H하고 I, X3가 두가지가 될지 3단계 결정이 근데 그중에서 뭐가 X3가 최소한의 결정 OK? X3로 H와 I를 선택할 수 있는데 S3가 2면

결정에 조건이 달리는데 S3가 뭐냐에 따라서 S3가 E면 X3 스타는 H다 S3가 F면 X3 스타는 I다 그럼 여기에 나와 있는 이거는 뭐냐 F3 S3 X3 그 다음에 이게 또 나오잖아요 여기 나와 있는 게 지금 이거예요

합친 게 이게 예를 들어서 h 에서 2에서 h 로 간다 그랬을 때 총 2 f 라는 건 비용 함수야 그러면 2에서 h 간다 그러면 이게 s들이가 2고 x들이 있습니다. 2에서 h 가는게 비용이 얼마야? 1 1이지 그 다음에 뒤에 나오는 건 뭐냐? x들이는 내가 h 로 갔을 때 4단계에서 4단계에서 h 있을 때 최종 목적지까지 비용이 얼마냐?

그래서 1 더하기 3에서 4 이렇게 되는 겁니다. 내가 만약에 H로 하고 I로 간다면 2에서 I로 간다고 했을 때 비용은 얼마가 되느냐? 8이 되는데 그건 4 더하기 4에서 8이 됩니다. 기호들의 의미를 알겠죠? S는 상태, X는 나의 결정. 여기서 결정이라는 것은 현재 상태에서 다음으로 가는 목적지.

근데 스타는 왜 붙는거에요? 스타는 내가 선택할 수 있는게 E에서 H나 I 선택할 수 있지 그중에 좋은 결정에 스타가 붙여지는거에요 스타는 최적해 할 때 보통 우리가 X 스타 그렇게 해요 그동안 우리가 여러가지 선형 모형을 했는데 X가 얼마냐 뭐 XY이 얼마냐 X2가 얼마냐 했을때

최적해를 x1* x2* 그런 식으로 스타를 붙여서 표시를 해줍니다 자 이 표를 여러분이 완성을 할 수가 있어야 되겠습니다 이 표에 대해서 질문이 있어요 자 그럼 여기 나와 있는 이게 뭐냐 2단계에서 b라는 상태에 있으면 최적목적지까지가 11이다 얘기해요 b에서부터 7일까지

이거는 2단계에서 C에 있으면 C에서부터 J까지가 7이다 오케이? 그럼 마지막에 어... 이거는 뭐야 이거 잠깐x3 아 이게...

-뭘은 없을까? -오케이, 오케이, 오케이. 여기 지금 이게 13하고...

자 그러면 여기 11이라고 나와 있는 게 뭐냐 이게 바로 F1 1단계에서 A라는 상태에 있을 때 최소 비용으로 최종 목적지까지 가는 데 드는 비용이 얼마냐 이게 얼마가 11이다 이거야

B에서는 B에서 21, C에서는 7, 뒤에서는 8. 그게 F2STAR B, F2STAR C, F2STAR D 그런 것들입니다. 그게 레이블에 있는게 그게 바로 그것들이에요. 레이블에 있는 것 때문에 레이블에 있는 것 때문에 레이블에 있는 것들은 목적지와

다음 단계 목적지 그 다음에 최종 목적지까지 최소 비용 S2에서부터 자 이제 기호들을 우리 다 알겠죠?

네, 성공합니다. 뭐 이제 다 내일 모레 쉬면은 그 다음 두 번 하고 그 다음 주 월요일 한 번 더 있죠. 시험 시간에 시작하는 주. 그렇죠? 오늘이 6월 1일이고 6월 3일은 이날 수업 없고

6월 8일, 6월 10일, 6월 15일 한 번 더 수업하고서 그 다음에 수요일 날 시험구나? 화요일 우리가 월 수업이 되게 화요일 날 시험구나 수요일 지난번에 수요일을 보지 않았어요? 네 그렇게 되는 겁니다 네 네

17 지금 여러분들이 하는 과제가 언제 제출이죠? 이날 제출이에요? 네 할 수 있어요 그때까지? 네 만약에 좀 전에 나와있는 숫자들이 비용이 아니라 각각 가는 길에서 뭔가 수금을 해서

이게 된다 그러면 그걸 최대화를 해야 될 거란 말이지? 그럼 어떻게 풀겠어요? 최대가 되네 스테이지 4에서 J가 3, 4니까 똑같이 거기서 원래는 니니마니징을 했다는 거 거기서부터 차근차근 맥스 니니마니징 해가지고 HI 그 4단계는 상관없고 똑같을 거고 EFG가 어떻게 되는 거야?

그러니까 E에서도 결국에는 갈 수 있는 경로가 두 가지니까 그 두 가지를 놓고 이번에는 더 큰 거를 선택해가지고 그래야겠죠? 그래서 이번에는 어떤 걸 선택한가? 이번에는 max예요 그래서 이거 대신에 이걸 선택하는 거지 그래서 I로 간다 이거

아이가 있고 있지 않죠 이해도 이거 선택하지 않고 이것은 되죠 그 예 이것은 되죠 지랄 바라고 이 경우가 완전히 이제 반대가 되는 겁니다 자 네이브를 그렇게 하고 그 다음에 또 그 다음에 어떻게 비해서는

그 다음에 c는 다 똑같아. c에서 아무데나가고. 뒤에서는 b나 g로 가라. 그러면 여기 나온 c5, c1, c2가 여기 있는 숫자가 있죠. 그 다음에 a에서 b, cd로 가는 걸 비교해보니까. 이번에는 a에서 b로 가는거죠.

그래서 이게 롱 디스패스가 되는 겁니다. 그래서 총 비용이 아니라 총 뭐 이때는 뭐 뭐 어쨌든 비용을 최대한다고 하면 뭐 어쨌든 뭐가 됐든가 아니면 뭐 월해볼라. 맥시마이즈가 되는 겁니다. 알겠습니까? 네. 동쪽 기법 이제 알겠죠? 어 계산 수율성 어

이거 제가 설명했나요? 아니요 자 동쪽 계획북을 왜 이걸 하느냐 한마디로 얘기하면 계산을 최소화하면서 가능한 점을 다 비교하는 겁니다 계산을 최소화하면서

그러면 계산을 최소화하지 않다면 계산을 더 할 수도 있느냐 여기에 지금 경로가 총 몇 개에요? 이 문제를 생각해보세요 25개 25개 아니요 5의 5제곱 여기서 지금 갈 수 있는 게 선택이 몇 가지가 있어? 5개 1단계에서 2단계로 가는데 5가지가 가능해 그 다음에? 5개 또 5개

여기까지 5개가 가능하지? 5개가 5번. 5에 5승? 얼마? 5에 2승이면 25. 5에 3승이면? 125. 5에 4승이면? 600.

325 125 625 드라맨 3125

3125개가 있어요. 그럼 이 3125개의 경로를 다 비교하려면 일단 뭘 해야 돼? 다 나열해요. 3125개 하나하나에 대해서 길이를 계산해야 되겠죠? 경로 하나의 길이 계산하는데 얼마나 계산이 필요해요? 이게 컴퓨터 사이언스에서

알고리즘 효율성 비교할 때 계산 복잡도라는데 컴퓨테이션 컴플렉스 t 라고 해요 몇번이나 계산하자 이거지 경로 하나의 길이를 결정하려면 자 s 에서 a1 b1 c1 d1 2안에서 f로 간다 그러면은 그 경로의 길이 계산하기 위해서 더 쌤을 몇번 해야 돼

더하기 아 여섯 번 요거 한번 더해주면 되는거고 요거랑 요거 더해주고 나온 결과랑 이거 더해주고 두 번 세 번 네 번 다섯 번 덧셈 다섯 번 하면

경로 하나의 길이가 계산돼요. 네. 근데 경로가 몇 개? 3,125개. 5에 5승 개가 있어. 그러면 총 더 쓴 몇 번? 15,620. 5,620. 네. 만 얼마? 15,620.

3125개의 경로들에 대해서 길이를 다 계산한 다음에 그 중에서 제일 짧은거 결정하려면 지난 시간에 하지 않았나? 월드컵이 다가오죠. 32개 팀 중에서 1등을 뽑기 위해서

최소한 몇 경기를 해야 돼 한 경기만 해서 제일 잘한 뒤 결정할 수 있어 한 경기만 하면 뛰지 못한 팀이 나오잖아 최소한 모든 팀들이 다 경기를 하면서 1등을 뽑기 위해서 4번 경계수 4번 5번 그건 특정한 팀을 기준으로 한 거고 전체 경계수 개최해야 되는 경계수

두 팀만 있으면 몇 번 하면 돼? 열.. 아니 한 번 두 팀 있으면 한 번만 하면 되죠? 네 팀 있으면 두 번 - 세 번 - 세 번 준결승하고 결승해서 세 번이지 네 여덟 팀 있으면 일곱 번 여덟 팀 있으면

둘씩 짝지어서 8강전 한번 하고 4강전 하고 8강전 할 필요 없지 4강으로 올라가는 뭐라 그러는가 8강전 4강전 그 다음에 결승전이지 8강전 4개 4강전 2개 결승전 해서 7번이 되죠 16팀 있으면 8,4,2,1 패턴이 보여요 32팀 있으면 31번 16,8 결국 2에

몇 팀이야? 어.. 2회 4승, 2회 5승 마이너스 마이너스 1입니다 결론만 얘기하면은 만약에 그게 딱 30팀을 해서 토너먼트가 안될거에요 만약에 3팀이 있다면 어떨까요? 일단 2팀 붙이고 하나는 무슨걸 뭐라 그래요 9전승으로 올라와서 하면 어차피 3경기가 필요하잖아요 2경기가 필요하잖아요 3팀 있으면 땡

5집이 있으면 내용이 필요해요. 일단 NTI, NTI팀이 있으면 그중에서 한, 제일 작은 팀 뽑으려면 NNS번 비교를 해줘야 할 때, 여기도 마찬가지야 경로가 3125개가 있다. 길이를 다 계산했다. 그저 제일 짧은 거를 보고 싶다. 3124번 비교를 해야 돼. 비교 어떻게 하느냐. 여기서 숫자 2개를 비교해서 작은 놈을 모르는 거는 하나의 상을 뺀 다음에 마이너스는 앞에 게 작은 거 불렀으면 뒤 게 작은 거.

길이가 나왔는데 하나는 17이고 하나는 18이다 이거야 17에서 18 뺐어 마이너스다? 앞에다 짜는거 오케이? 만약에 플러스가 나오면 그럼 뒤에 짜는거 그런 식으로 3124번을 비교를 해야 돼요 자 그래서 더셈 15,000번 그 다음에 비교한다고 뺄셈 3124번에서 총 18,000 몇번을 해야지만

전체에서 가장 작은 경우를 찾을 수 있어 자 그런데 그냥 동쪽 기획법을 하면 몇 번 하면 된다? 189번 하면 된다. 이거랑 3123만 1240번. 그래서 동쪽 기획법이 효율적이다 이거에요. 훨씬 효율적이지. 31249번 이게 뭐에요? 이거를 Total Enumeration, Explicit Enumeration. 전수비가 하는거.

그런데 동쪽 교육법은 불필요한 더하기를 반복하지 않습니다. 총 3,100개의 경로들에서 더하기를 하다보면 중복되는 더하기를 나온다니까. 그거를 최소한의 동쪽 교육법의 계산 방법이다. 189번으로 가장 짧은 경로를 찾을 수 있다. 자세한 것들은 읽어보세요. 몇 번 몇 번 하는 것들.

자 그 다음에 이제 예제로 뭐 시험 문제 기말고사 나면 이런게 나오는 겁니다. 물론 앞에 것도 나올 수 있지만 다섯 팀의 의료진을 세개 국가에 나눠서 확인한다. 의료팀 수가 다섯 개가 있어요. 혜택을 보는 나라는 세개의 나라야. 뭘 결정하느냐

5개 팀을 abc 나라에 몇 팀으로 나눠서 보냈어요 몇개씩 몇 팀씩 보냈느냐 결정한거에요 자 근데 이거는 앞에서 우리가 한 문제들하고 어떻게 보면 비슷합니다 어떤 문제가 있었는데 프로듀스 믹스 앤 모아 프로듀스 믹스하고 뒤에 따라 나오는 일은 뭐였다고? 우리 학교조회 시험과 제일 먼저 살펴본 장난감 예제를 우리가 무슨 문제라고 그랬어요 프로듀스 믹스 앤

- 헤븐. - 헤븐. 뭔 헤븐? - 디스트리뷰션. - 응? - 디스트리뷰션. - 디스트리뷰션은 통계학에서 나오는 얘기고. 아, 우리도 물론 있지. 프로덕션 앤 디스트리뷰션 예제가 있었지. 근데 이건 프로덕트 믹스 앤 리소스 앨로케이션. 아, 좀. 근데 이거는 뭐 프로덕트 믹스는 아니고 그냥 리소스 앨로케이션 문제예요.

세계나라에 몇개 팀씩 보낼 것이냐를 결정하면 돼 결정할 방법 혹시 알아요? 방법의 수 세계나라에 다섯개 팀을 보내는 방법 만약에 의료진이 하나만 있다 그럼 세계나라에 나눠서 보내는 방법은 몇가지야? 한 팀밖에 없어

3가지. 3가지지. 한 팀 보낸다 그러면 한 나라는 받고 나머지 두 나라는 못 받지. 근데 그 세 나라가 받는 나라가 셋 중에 하나가 될 수 있으니까 세 가지지. 자 두 팀을 보낸다 그러면. 어? 20에서.

팀의 수 방법 대분 방법 간격 팀에 하나만 쓴 실비밖에 없어 두 개 있으면 몇 가지 방법 있어? 여섯 개 네? 여섯 개 왜 여섯 개야? 1팀 채널아 어디에 갈 수 있어?

두 번째 팀 어디 갈지 3개 중에 있는 거거든요 - 9개? - 9개 - 6개, 9개 - 9개 여기서 중요한 건 의료팀 간의 구분은 없어 예를 들어서 뭐 첫 번째 팀은 A급 팀이고 두 번째 팀은 B급 팀 그런 거 없어

같은 걸로 똑같은 팀이 딱 똑같은 서비스를 제공한 거예요 어떻게 돼? 여섯 개입니다 여섯 개? 어떻게 해서? 3H입니다 네? 3H입니다 3H? 아 미리 공부를 했네 공부 안 하고도 알 수 있는 건가요?

아니요, 통화하고 왔습니다 네? 통화하고 왔습니다 뭐하고 왔어? 항균과 통계하고 왔습니다 항균과 통계에서 보답해 나왜 H? 네 중복 조합 네 중복 조합이에요 중복 조합 공식도 기억해요? 네

중복 조합의 공식은 자 순서 여부 경우에 속 따지는게 순서 YES, NO 그 다음에 중복 중복 이쪽으로 YES, NO 그러면 순서 있고 중복 없는 건 PERMUTATION 그 다음에 순서 없이 중복 없는 건 CNR

그 다음에 순서 있고 중복 있는 거 PNR 순서 없고 중복 있는 거 HNR 여기서는 나라를 뽑는 거에 팀을 뽑는 게 아니라

무슨 말인지 하겠습니까? 이 문제는 어떻게 되느냐 이 봉지안에 국가 뭐 이건 바구니도 국가 1 국가 2 이렇게 공을 3개를 넣어놔 1 2 3 여기서 몇 번 꺼낸다?

5번 추출하는데 어떻게 추출하냐 다시 집어넣으면서 다시 집어넣는 거를 뭐라 그러지? 보건 어? 그래 보건 with replacement의 영어로는 하나 끄집어서 확인하고 다시 집어넣고 그게 보건이야 replace 제자리 여기서 replace 보통 교체하는데 여기서 이

경우에 수업할 때는 리플레이스먼트 가 제자리에 놓은다에 다시 이 바구니에다 집어넣고서 다시 0123을 놔두고 또 끊는다에야 그걸 집어넣고 빼고 집어넣고 빼고 넣고 넣고 빼고 집어넣고 빼고 집어넣고 5번에서 1번이 몇번 나왔는지 2번이 몇번 나왔는지 3번이 몇번 나왔는지 따지는거에요 그러니까 1번이 등복해서 나올 수 있어

그리고 일본이 처음에 나온 마지막에 나온 상관없어. 몇 번 나오는지만 중요해. 자 그러면은 그걸 우리가 이 중복 조합 HNR이라고 하는데 여기서 그러면 뭐냐. 5개 중에서 3개를 고르는 게 아니라 3개를 중복해서 5번 골라내는 거야. 그래서 어떤 나라에 몇 개 팀이 간지 결정하는 거예요. 그냥 HNR이 있으면 이 공식은 어떻게 되느냐. C로 바꿀 수 있는데 N+R-C에서 R 고르는 건 똑같아요. 이거는 검색해보면 왜 이게 똑같아지는지 설명하는 방법이 있을 겁니다. 파티션을 한다는 게 우리가 설명을 하는데 결론만 얘기하면 21가지 방법이 있습니다.

수분한 가지 어떻게 되느냐? 그냥 비교로 하면 이렇게 돼요. 300으로 나아가는 거. 국가 1, 2, 3에. 1, 2, 3에. 300.

0 3 0 0 3 요새가 있죠 4 5개씩 1 5개 다 가져가는거 그 다음에 4개 1 가져가는거 그 다음에 3개 2개 가져가는거

4일로 나누는 게 몇 가지가 나와요? 6가지 4일로 나누는 건 셋 중에 2개 오르는 거잖아 한 나라는 4개, 한 나라는 하나 이게 6가지가 나와요 3일로 나누는 거 6가지 6가지 그 다음에 또 뭐 있어?

1,2,2,2,2,1 이건 몇 가지 나와? 여섯 가지 세 가지 세 가지 나오지 두 나라는 두 팀 받고 한 나라는 한 팀 받으니까 한 팀 받는 나라만 결정해 세 가지가 나와요 그 다음에 또 뭐 있어? 300

311이 있지 311 311은 몇가지야? 세가지 세가지 다 합치면? 21가지 21가지 오케이? 네 이렇게 되는겁니다 자 그거를 자 이거 딱 보고서 그냥 아 2대 중으로 다 입어 그렇게 하면 되겠네

독점하게 동쪽계획법이 뭐 이런거 할 필요없이 편만 보고

-그만 보고서 어떻게 하는 게 좋겠다.

네. 이렇게 보세요. 미리 공부했어도 상관없어. 그냥 자신의 말로 설명을 해버려야 돼. 표만 보고서. 이 표가 뭘 의미하는지 알겠어요? 일단 이 표에 나오는 숫자가 뭔가 좋은 거야.

여기 보시면 혜택이라고 해서 배너핏인데 다우전 어디서는 플러스 이유를 잘 뭔 소리냐 의료팀이 숫자가 012345 이렇게 늘어나면 늘어날수록 국가 1,2,3의 혜택이라는 게 점점점점점 늘어나는데 하여튼 좋은 거지 팀을 많이 받으면 의료팀 많이 받으면 받으면 뭔가 커지잖아 혜택이

각각 국제 각각의 나라에 대해서 자기는 이 대기 코치도 최대가 되도록 그렇게 하겠지만 원하겠지만 우리가 원하는 거예요 코디에이션 하는가 세 나라의 혜택이 최대가 되도록 오케이 세 나라의 혜택의 합의 최대가 되도록 5개의 의료팀을 나눠서 보내는 건데 이것만 딱 보고 어떻게 해야 됨

의류팀 1일 때, 의류팀 수가 1일 때 국가 1, 2, 3에서 최대가 되는 거를 보고 의류팀 수가 2일 때 최대가 되는 걸 고르고 의류팀 3에서 최대가 되는 걸 고르고 의류팀 4에서 최대가 되는 걸 고르고 의류팀 5에서 최대가 되는 걸 고른 다음에 그 여러 가지 조합들이 있잖아요 그래서 거기서

이미 의료팀 1을 선정할 때는 뭘 넣어야 하는지 아니까 그 조합들에 대입하면서 최대를 구합니다. 어쨌든 이거 딱 보고서 다섯 개 팀을 한 달에 다 보내면 어디에다 보내겠어? 국가 2에서. 일단 150은 나와야 되는 거야 혜택의 합의. 네. 근데 한 달에 보내지 않고 나눠서 보내면 이거보다 150보다 커질 거냐 그걸 지금 생각해 보는 거야.

150보다 더 크게 나눠서 보낸 방법이 있어요? 110, 50, 160 - 150은 뭐야? 이렇게 이렇게? - 네 160 되긴 그보다 더 큰 거

-둘, 둘, 하나입니다 -네? -둘, 둘, 하나 -둘, 둘, 하나? -네, 둘 -둘, 둘, 하나? 하나, 둘 다행이다 언제 제대했어요?

1,3,1이 되야 해? 네. 1,3,1 이렇게? 네. 170. 120,1,70. 자, 이걸 동적기획법을 하는 것을 생각해 볼게요. 이런 표가 주어졌으면 시험 문제에 나온다, 이런 것을 나온다. 지금 질문을 해야 할 게 이겁니다

그림으로 나타내세요. 이 네트워크를 그려야 돼요. 그럼 이 네트워크가 뭐냐? 동그라미가 나타나는게 SN 이라는 상태가 뭐냐 하면 스테이지 1에서 5개 팀을 가지고 시작합니다. 자 이제 5개 팀을 가지고 3번째 나라에 몇 팀 주고 남은거 갖고 두 번째 나라에 주고 남은거 갖고 세 번째 나라에 주는 거예요.

그 마지막에 세 번째 달아 까지 그럼 몇 팀이 남아 쥐 로가 되어야지 그때 남겨놔지 1 2 3 4 당 지 나라에 대정을 했는데 그 남은 남지 있어 안되지 럭지 나라에서 어느 혜택이 최대가 되니까 자 그러면은 여기서 단계에서 단계 2관 국가에 대정한 것 같다

이건 국가 2. 그 다음에 3단계에서 4단계로 가는 것은 국가 3. 자 이게 지금 S1이 5개 팀이 남아있는 팀의 숫자입니다. 이게 지금 여기서 의미하는 건 앞에서 의미하거나 좀 달라요. 상태가. S2가 5라고 하면 첫 번째 나라에 누우라는 거야.

0 첫 번째 나라에 하나도 안 줬다는 얘기가 되는 거지 그럼 첫 번째 나라의 혜택은 뭐예요? 0 혜택은 0겠지 당연히

여기서 5에서 4로 간다는 얘기는 X1이 X1이 첫 번째 나라에 배정하는 걸 말하는 겁니다. X1 결정하고 국가에서 X2 결정하고 X3 결정하는 거예요. 혜택이 여기 있는 숫자들 5에서 0가 된다는 건 뭐야? X2가 0이 된다는 것은

X1이 5 5가 된다는 얘기고 혜택은? 최대 혜택이 아까 얼마였어? 100? 20 20 오케이? 네 여기다 쓸 수 있겠지? 0에서 0으로 가는 혜택이 제로지 이건 그렇지, 여기에서 아무 팀이 저기서 남아있지 않아요 첫 번째 팀에 다 가져갔으니까

자 그럼 s2 파악에서 제로 간다 그 다음에 제로 간다면 이게 x2가 5란 얘기가 되는 겁니다. ok? 네. 여기다 숫자 다 넣을 수 있겠죠? 네. 자 여기로 가는거 뭐야? x2가 1. x2가 1이고 혜택은?

40 20 20? 네 만약 X2가 0이면 히트하면 0죠 마지막 것도 쉽게 할 수 있죠 0에서 0으로 가는 건 X3가? 0 1에서 0으로 가는 건? 0 X3가 0

아 아 뭐 이렇게 마지막 표에 있는 숫자들 그냥 가지고 오는 데 순서는요 아 오케이 나를 왜 안맨 아래 뜬 보고서 x5가 이건 x5가 5지 으 으 자 표를 그리고 그 다음에 어떻게 된다

동쪽 계곡으로 푸는 것은 일단 여러분의 아이디어를 가지고 어떻게 하는지 알아야 할 것이고 그 다음에 중요한 것은 표로 나타내는 것이죠 이 핫패지로 다 나오는 겁니다 앞에서 한 거랑 똑같은 거를 반복하는 거예요 표를 채울 수 있겠어요?

최우선의 맨 마지막에 결론이 어떻게 됐다? 170. 170이 세 나라의 혜택의 합의 170이야. S1은 5로 시작합니다. 그래서 이건 S1이 5가 되는 거예요. 그리고 X1이 1, X2는

3 X3는 1 이렇게 하면 1, 3, 1 이렇게 나눠주면 세인다라의 혜택이 170으로 최대가 됩니다 어떻게 되냐? 네이블링을 하는 겁니다 네이블링을 네이블링을 이번에 핑크색 박스로 이렇게 해서 했어요

0에서 0으로 간다. 이건 S3고 이건 S4입니다. 이건 X3네 죄송합니다. X3* 이것도 X3*

XT의 스타가 1이에요 이제 요거는 S3가.. 아.. 아.. 아.. 요건 세 번째 나라의 혜택 첫 번째 숫자는 혜택 국가 3의 혜택이고 두 번째 숫자는 국가 3의 배정된 수

이건 뭐예요? 세 번째 단계에서는 무조건 남은 팀 전부 다 세 번째 나라에 배정한다 이거예요

남은팀이 뭐예요? 이게 S2입니다. 대정하는게 이게 X2입니다. 한 단계 앞으로 와서 이 부분을 보면 상태 2가 S2가 1일 때 지금 두 가지를 여기 지금 두 가지가 가능해요. 일로 갈 수도 있고 일로 갈 수도 있어. 일로 가는 건 뭐야 X2가?

하나 줄어드는 거죠. 여기는 그대로 다음 나라로 넘기는 겁니다. 한 팀이 있는 걸. 한 팀이 남아있단 말이에요. 예수 2가 1이라는 것은 이건 뭐냐. 국가 1에 4팀을 배정하고

그 다음에 국가 2, 3에 한 팀을 남겨놓은 거예요. 근데 그 한 팀을 국가 2로 보낼 것이냐, 3으로 보낼 것이냐 결정한 거야. 오케이? 네. 그래서 X2가 1이라 그러면 국가 2로 보낸 것이고 하나 남은 거를. X2가 0면은 국가 3. 세 번째 나라로 보낸 겁니다. 두 개를 비교했더니 어떻게 되냐 하나는 혜택이

50이고 하나는 20입니다. 이게 지금 한 팀이 남았을 때 국가인은 혜택이 20밖에 안되고 세 번째 나라가 받으면 혜택이 50이되요. 그러니까 두 번째 나라로 주신 말고 세 번째 나라로 주어야지만 혜택이 50% 최대가 되겠죠. 이걸 선택한 거죠. 그래서

20하고 50을 비교해야 돼. 50을 비교해야 돼. 50을 선택해야 돼. F2 뒤에 나오는 게 뭐다? 1, 2, 1, 2, 1. 숫자가 이렇게 나왔어. 1, 1이 돼야 되는데.

*Phone rings*

-몸에 스트리스. -몸에 스트리스. -스트리스. -몸에 스트리스.

앞에 건 상태 뒤에 거는 선택 결정 여기가 S2고 하나는 X2에요 두 번째 건 X2 얘도 S2 X2

자 그런 식으로 반복하면 되고 그 레이블들을 보내는 표에다 갖다 놓아주면 되는 겁니다 아 그 다음 거는 건너뛰겠어요 자 이건 스키 스키하고 음