쉐도잉 연습: What Is Dynamic Programming and How To Use It - 영상으로 영어 말하기 배우기

연습 모드 선택

각 모드는 전체 화면 연습실로 열립니다.

175 문장
문장이 너무 짧거나 길면 Edit를 눌러 조정하세요.
1
Hey CSDojo, it's YK here.
2
So in this video I'm going to talk about what dynamic programming is
3
and how to use it and as I explain how it works I'm going to assume that you're already familiar with recursion.
4
So what is dynamic programming exactly?
5
It's actually fairly simple even though it might sound difficult
6
It's basically a way of making your algorithm more efficient by storing some of the intermediate results
7
And it works really well when your algorithm has a lot of repetitive computations
8
So that you don't have to repeat those computations over and over again and
9
I'm gonna give you a concrete example of how it works with Fibonacci sequence
10
So just in case you're not familiar with it Fibonacci sequence is a sequence of numbers
11
that starts with two ones at the beginning and Each number after that is computed by adding up the two previous numbers
12
So the third Fibranch number is 2 because 1 plus 1 equals 2
13
And then the fourth Fibranch number is 3
14
because 1 plus 2 equals 3 and so on and this sequence keeps on going forever
15
So let's say we're trying to solve the problem of finding the n's Fibranch number
16
or writing a function called Fib of n
17
Which takes a positive integer n and finds and returns the n's Fibranch number
18
So if the given n is 3
19
We want to be able to find and return the third free lunch number, which is 2
20
And if the given n is 5, we want to be able to return the fifth free lunch number, which is 5
21
Let's see how we can solve this problem using dynamic programming
22
So if you want to solve a problem using dynamic programming, there are typically three steps you can take
23
The first step is to come up with a recursive solution to your problem
24
And then in your recursive solution, if you notice that there are a lot of repeated computations
25
You can then store some of the intermediate results so that you don't have to repeat those computations
26
This process is also called
27
Memoization or memoize and this is not to be confused with Memorize
28
and I've made that mistake before too and then the third step if you don't like using recursion anymore is
29
To come up with something called a bottom -up approach
30
So let's first see what a recursive solution might look like for this particular problem
31
So as I said earlier, we're going to write a function called fib of n
32
Which takes n a positive integer and returns the nth fibranche number
33
And if n is equal to 1 or 2
34
We know that the first and the second fibranche numbers are 1
35
We're going to return 1
36
But instead of returning it right away
37
We're going to store it in a temporary variable called the result and then return that instead.
38
And it's going to be clear why we need to do that later.
39
And if n is neither 1 nor 2, then we're going to return the sum of the two previous Fibonacci numbers instead.
40
Fib of n minus 1 plus Fib of n minus 2, store that in result, and then return it at the end.
41
So this solution works, but it's very very inefficient.
42
To see why, let's see an example where we are trying to find the fifth Fibonacci number by calling Fibonacci 5.
43
So to find the return value of Fibonacci 5,
44
we need to first compute the return values for Fibonacci 4 and Fibonacci 3 so we can add them up.
45
And to find Fibonacci 4, we need to first compute Fibonacci 3 and Fibonacci 2 and so on.
46
And that's what this diagram shows.
47
And looking at this diagram, you might notice that there are some competitions that we repeat over and over again.
48
For example, we need to compute the return value for Fibonacci 3 times,
49
and we need to compute the return value for Fibonacci 3 twice here.
50
And it's not a big deal when we are trying to find the 5th or 6th Fibonacci number,
51
but if we're trying to find the 100th Fibonacci number, it becomes an issue.
52
And actually the time it takes to find the n's Fibonacci number grows exponentially
53
Or roughly in the order of 2 to the power of n
54
And dynamic programming here says why not just store those return values
55
For example for Fibonacci 3 store the return value once we compute it
56
And then use that same value when we see Fibonacci 3 again instead of computing it again
57
And again, this process is called memoization.
58
So let's see what a memoized solution looks like in code
59
Let's again consider the example where we're trying to find the fifth few months number by calling Fib of 5
60
The idea of this solution is going to be that we're going to use an array whose length is
61
n plus 1 or 6 in this particular case
62
because n here is 5 and then we're going to store the return value for the functional fib of n.
63
at the index n.
64
So we're going to store fib of 1, which is the first fib of number right here at index 1,
65
and then fib of 2 at index 2, and so on.
66
And initially we're going to set all these values to null.
67
And we're going to write our function fib, and this is going to take two arguments instead of just one.
68
The first one is the same as before, n, a positive integer, and the second one is going to be this array
69
and so you'll need to initialize this array memo before you call this function.
70
Now at the beginning of this function, check if memo at index n is null or not.
71
If it's not equal to null, that'll mean that we've already seen this argument n and we've
72
We've already stored the return value for that at the index n in memo, so just return that instead
73
So return memo square brackets n
74
Otherwise, the following part is the same as before
75
If n is equal to 1 or 2, return 1, store 1 in result, and then return that at the end
76
And if that's not the case, then find the sum of the two previous equivalent numbers, and then return that instead
77
And then what's new in this function is that before you return this result, the return value
78
You need to store it in Memo at index n so that you can use it later
79
Let's now think about the time complexity for this solution.
80
We're going to call it t of n
81
This is going to be the time it takes to find the n's Fibonacci number with this particular method and
82
we're going to find that by multiplying the number of times we call this function,
83
fib, with the time it takes to execute each of those calls.
84
We're going to call that t.
85
Now, there are only two ways we're going to call this function fib.
86
The first way is when we call this function for the first time with the arguments n
87
and memo to find the entropy bunch number, and the second way is from this line right here,
88
and And notice that if you look at this whole block after this first if clause,
89
this whole block is only executed at most n times.
90
And this is true because there are n possible arguments to this function.
91
That's 1 through n.
92
And each time this function is called with each of those arguments, the return value will be stored in memo at index n.
93
So after the first time this function is called with each argument, we'll never get to this block.
94
And each time this block is executed, fib is called a most twice if we get to this line.
95
So the number of times fib is called is a most 2 times n plus 1.
96
So 2n comes from this block right here, and 1 comes from the first time we call this function fib and
97
the time it takes to execute each of those calls this t right here is
98
Going to be a constant time or a big O of 1
99
and this is because if you look at each operation in this function excluding
100
These recursive calls that follow each operation is a constant time operation and when you have a constant time operation
101
when you add them up, you still get a constant time operation, which is big O of 1.
102
And that's why we have big O of 1 here.
103
And so t of n, or the time it takes to find the n -spin -onage number with this particular method,
104
is going to be 2n plus 1 times big O of 1, which is big O of 2n plus 1,
105
which is equal to big O of n.
106
and this is a huge improvement from what we had earlier
107
which was big O of 2 to the power of n
108
and let's now examine how this memo array is actually filled
109
so let's say we're trying to find the fifth Fibonacci number again
110
and when we call fib with the argument 5
111
and memo of course we'll see
112
that we don't have a stored value at the index 5 yet
113
so we go down and we're gonna to ask ourselves what's the value of Fib of 4
114
and then 3 and so on and when we get to Fib of 2
115
we'll know that this value is 1 so we're going to store it at index 2 right here,
116
and same with Fibon1, that's 1 right here, and once we have these two values, we'll be able to find the third Fibonacci number,
117
which is Fibon3 right here, and then once we find the value by adding them up,
118
store that value right here so we can use it later, and then when we go up to Fibon4,
119
we'll add 1 and 2 right here and we get 3
120
and so on until we get here and
121
so as you can see this array is mostly filled from left to right so
122
when you see this you might say why not just explicitly build
123
this array from left to right from scratch instead of building it recursively
124
and that's the idea behind a bottom -up approach
125
so let's see what a bottom -up approach might look like in code
126
we're going to define a function called fib bottom up
127
which takes n a positive integer just like before
128
and returns the nth Fibonacci number and then
129
if n is equal to 1 or 2 of course we're going to return 1 and after
130
that we're going to define an array whose length is going
131
to be n plus 1 where n plus 1 is 6 of course
132
if we're trying to find the fifth Fibonacci number right here
133
if n is equal to 5 and after
134
that we're going to set the first and the second elements of this array bottom -up to be 1, these two items right here,
135
and then we're going to run a for loop for i from 3, which corresponds to this item right here,
136
up to n, and n corresponds to the last item right here of this array,
137
and whatever index we're examining currently we're going to set
138
that element at the index i
139
or bottom up square brackets i to be the sum of the two previous items
140
so in this particular example we'll have two here three here
141
and after that we're going to return the last item in bottom up
142
or bottom up square brackets n
143
and we're done the time complexity for this algorithm will be again big o of n
144
because we're going to define this array and go through this array only once
145
Okay, so that's how dynamic programming works
146
But now I'm gonna show you a quick demo with Python
147
and something called Jupyter Notebook to show you how this idea might play out in practice
148
So in this Jupyter Notebook, I have defined a few functions in Python Fib of n which is a recursive naive recursive solution and
149
Fib of memo and fib of 2 which represent a memoized solution and 5th bottom -up, which is of course a bottom -up solution.
150
So let's see how they compare to each other in performance
151
We're gonna try running fib of n first the naive recursive solution with fib of 5 and
152
That gives us 5 which is expected.
153
What about fib of 20?
154
That gives us the answer pretty quickly, too.
155
And what about fib of 35?
156
This actually takes 5 to 6 seconds on my computer
157
So it's obviously not the most efficient approach.
158
Let's see how fib of two and fib of memo the memoized solution compares to that
159
Let's try running fifth memo of five firsts and that gives us five which is expected
160
And what about fifth memo 35?
161
That's pretty quick, too.
162
And what about fifth memo 100 and 1000
163
This actually gives us an error and this error is called the recursion error
164
Python gives us this error actually because there are too many recursive calls on a call stack and
165
To fix that we can just use the bottom -up approach
166
One advantage of using a bottom -up approach is that we don't have to put any recursive calls on a call stack
167
So we don't have to worry about that.
168
So we're going to load this function and then run it with the argument 35
169
Which is pretty quick 1000 and then let's try 10 ,000 as well
170
And that's pretty instantaneous, too.
171
Okay, so that's my introduction to dynamic programming.
172
Let me know in the comment section below what you thought of this video,
173
and if you have any requests about what kind of videos I should make in the future,
174
let me know in the comment section below as well.
175
I'm YK from CSDojo, and I'll see you in the next video.

앱 다운로드

유창하게 말하는 데 필요한 모든 것

AI 발음 평가문장마다 점수 확인
IPA 발음 연습모든 소리 마스터
단어 학습나만의 단어장 만들기
단어 게임놀면서 외우기

같은 채널

FOR YOU

추천 영상

이 레슨의 어휘와 말하기 포인트

이 말하기 레슨은 영상 “What Is Dynamic Programming and How To Use It”을(를) 바탕으로 합니다. 가장 자주 반복되는 단어는 다음과 같습니다: fib, return, Fibonacci, value, function. 이 영상에는 섀도잉할 문장 175개와 단어 2286개가 있습니다. 말하는 구간의 길이는 14:27입니다. 화자는 분당 약 158단어로, 일상 대화에 가까운 자연스러운 속도로 말합니다. 단어의 85%가 영어에서 가장 많이 쓰이는 3,000단어에 속합니다. 나머지는 연습 전에 미리 확인해 두세요.

이 영상의 핵심 어휘

영상에 나오는 익혀 둘 만한 단어 15개를 발음, 뜻과 함께 정리했습니다.

단어발음뜻
memo 명사/ˈmɛməʊ̯/메모
sequence 명사/ˈsiː.kwəns/순서
execute 동사/ˈɛksɪˌkjuːt/처형하다
solve 동사/sɒlv/해결하다
algorithm 명사/ˈælɡəɹɪðm̩/알고리즘, 알고리듬
bracket 명사/ˈbɹækɪt/괄호
element 명사/ˈɛləmənt/요소
compare 동사/kəmˈpɛɚ/비교하다, 비유하다
efficient 형용사/ɪˈfɪʃənt/효율적인
examine 동사/ɪɡˈzæmɪn/검사하다, 조사하다
stack 명사/stæk/무더기
minus/ˈmaɪ.nəs/빼기
diagram 명사/ˈdaɪ.ə.ɡɹæm/다이어그램, 도표
naive 형용사/naɪˈiv/순진하다, 우직하다
correspond 동사/ˌkoɹəˈspɑnd/일치하다, 부합하다

영상에 나오는 구동사

단어뜻
go down 동사내려가다

이 영상의 문법

화자가 가장 많이 쓰는 문형을 영상 속 실제 표현과 함께 정리했습니다.

문형영상 속 표현
수동태 be + 과거분사 — 누가 하는지보다 무슨 일이 일어나는지에 초점is computed · is also called · is called
현재완료 have/has + 과거분사 — 과거의 일이 지금도 관련이 있을 때I've made · we've already seen · We've already stored
관계절 who / which + 절 — 사람이나 사물에 대한 추가 정보number, which is · operation, which is · five which is

주의할 발음

화자는 we're, don't, we'll 같은 축약형과 약화된 형태를 62번 사용합니다. 들리는 대로 짧게 발음하세요.

  • “sh”와 “zh” 소리: efficient /ɪˈfɪʃənt/, computation /ˌkɑmpjʊˈteɪʃn̩/, recursion /ɹɪˈkɜː(ɹ)ʒən/, memoization /ˌmɛmoʊaɪˈzeɪʃən/, exponentially /ɛkspə(ʊ)ˈnɛnʃəli/
  • 긴 단어 — 강세 위치에 주의: intermediate /ɪn.tə(ɹ)ˈmi.di.ət/, complexity /kəmˈplɛk.sɪ.ti/, temporary /ˈtɛmp(əˌɹ)ɛɹi/, repetitive /ɹɪˈpɛtɪtɪv/, memoization /ˌmɛmoʊaɪˈzeɪʃən/

한국어 화자가 어려워하는 소리:

  • /f/ — ㅍ(/p/)으로 바꾸지 말고 윗니를 아랫입술에 대기: define /dɪˈfaɪn/, efficient /ɪˈfɪʃənt/, confused /kənˈfjuːzd/, roughly /ˈɹʌf.li/, functional /ˈfʌŋkt͡ʃənəl/
  • /v/ — ㅂ(/b/)과 구별하기: solve /sɒlv/, naive /naɪˈiv/, variable [ˈvæɹ.i.ə.bl̩], repetitive /ɹɪˈpɛtɪtɪv/, recursive /ɹɪˈkɜː(ɹ)sɪv/
  • /z/ — ㅈ이 아니라 성대를 울리는 /s/: examine /ɪɡˈzæmɪn/, confused /kənˈfjuːzd/, clause /klɔːz/, memoization /ˌmɛmoʊaɪˈzeɪʃən/, initialize /ɪˈnɪʃəlaɪz/

이 영상으로 연습하는 방법

  1. 먼저 말하지 않고 영상을 끝까지 듣고 모르는 단어를 적어 둡니다.
  2. 0.75배속으로 한 문장씩 섀도잉을 시작하고, 익숙해지면 보통 속도로 돌아갑니다.
  3. 자신의 목소리를 녹음해 원본과 비교하고, memo, sequence, execute 같은 단어에 특히 주의합니다.

쉐도잉이란? 영어 실력을 빠르게 키우는 과학적 방법

쉐도잉(Shadowing)은 원래 전문 통역사 훈련을 위해 개발된 언어 학습 기법으로, 다언어 학자인 Dr. Alexander Arguelles에 의해 대중화된 방법입니다. 핵심 원리는 간단하지만 매우 강력합니다: 원어민의 영어를 들으면서 1~2초의 짧은 지연으로 즉시 소리 내어 따라 말하는 것——마치 '그림자(shadow)'처럼 화자를 따라가는 것입니다. 문법 공부나 수동적인 청취와 달리, 쉐도잉은 뇌와 입 근육이 동시에 실시간으로 영어를 처리하고 재현하도록 훈련합니다. 연구에 따르면 이 방법은 발음 정확도, 억양, 리듬, 연음, 청취력, 말하기 유창성을 크게 향상시킵니다. IELTS 스피킹 준비와 자연스러운 영어 소통을 원하는 분들에게 특히 효과적입니다.

섀도잉 방법: 단계별 전체 가이드 읽기 →