1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [세미나 : 기술 인터뷰]

2
00:00:02,640 --> 00:00:04,630
[케니 유, 하버드 대학교]

3
00:00:04,630 --> 00:00:08,910
[이 CS50 수 있습니다.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
안녕 모두, 내가 케니입니다. 저는 현재 중학교 공부 컴퓨터 과학입니다.

5
00:00:12,420 --> 00:00:17,310
전 전 CS TF, 그리고 나는 underclassman 때이이 있었으면 좋겠다

6
00:00:17,310 --> 00:00:19,380
내가이 세미나를주지 이유 죠.

7
00:00:19,380 --> 00:00:21,370
그래서 당신이 즐기시기 바랍니다.

8
00:00:21,370 --> 00:00:23,470
본 세미나는, 기술 면접에 대해 얘기입니다

9
00:00:23,470 --> 00:00:26,650
그리고 모든 자원은이 링크에서 찾을 수 있습니다

10
00:00:26,650 --> 00:00:32,350
여기이 링크 자원의 몇.

11
00:00:32,350 --> 00:00:36,550
그래서 꽤 몇 가지 문제가, 사실은, 문제의 목록을 만들었어요.

12
00:00:36,550 --> 00:00:40,800
우리가 조언을 찾을 수 있습니다 또한 일반 리소스 페이지

13
00:00:40,800 --> 00:00:42,870
인터뷰를 준비하는 방법에 대한,

14
00:00:42,870 --> 00:00:46,470
당신이 실제 인터뷰하는 동안 무엇을해야하는지에 대한 도움말을,

15
00:00:46,470 --> 00:00:51,910
뿐만 아니라 나중에 참조 할 수 있도록 문제와 자원을 접근하는 방법.

16
00:00:51,910 --> 00:00:53,980
그것은 모든 온라인입니다.

17
00:00:53,980 --> 00:00:58,290
그리고 이번 세미나 면책 조항을 시작해 to

18
00:00:58,290 --> 00:01:00,690
이렇게 안돼 - 인터뷰 준비를

19
00:01:00,690 --> 00:01:02,800
이 목록에 제한되어서는 안됩니다.

20
00:01:02,800 --> 00:01:04,750
이은, 안내하기위한 것입니다

21
00:01:04,750 --> 00:01:08,890
당신은 확실히, 나는 소금 입자로 말을 전부를해야합니다

22
00:01:08,890 --> 00:01:14,620
뿐만 아니라 당신의 면접 준비를하는 데 도움이 모든 것을 사용합니다.

23
00:01:14,620 --> 00:01:16,400
>> 나는 다음 슬라이드를 통해 빠르게거야

24
00:01:16,400 --> 00:01:18,650
그래서 우리는 실제 사례 연구로 이동할 수 있습니다.

25
00:01:18,650 --> 00:01:23,630
소프트웨어 엔지니어링 postion에 대한 인터뷰의 구조,

26
00:01:23,630 --> 00:01:26,320
일반적으로는 30-45분 것은,

27
00:01:26,320 --> 00:01:29,810
회사에 따라 여러 발.

28
00:01:29,810 --> 00:01:33,090
종종 당신은 화이트 보드에 코딩됩니다.

29
00:01:33,090 --> 00:01:35,960
따라서이 같은 있지만, 종종 작은 규모의 화이트 보드.

30
00:01:35,960 --> 00:01:38,540
당신이 전화 인터뷰를 문제가있는 경우, 당신은 아마 사용할 것

31
00:01:38,540 --> 00:01:44,030
collabedit하거나 Google 문서 중 하나 그래서 그들은 당신이 코딩 살고 볼 수 있습니다

32
00:01:44,030 --> 00:01:46,500
당신은 전화로 인터뷰하는 동안.

33
00:01:46,500 --> 00:01:48,490
인터뷰 자체는 일반적으로 2 ~ 3 문제입니다

34
00:01:48,490 --> 00:01:50,620
컴퓨터 과학 지식을 테스트합니다.

35
00:01:50,620 --> 00:01:54,490
그리고 거의 확실히 코딩 포함됩니다.

36
00:01:54,490 --> 00:01:59,540
당신이 볼 수있는 질문의 종류는 일반적으로 데이터 구조 및 알고리즘입니다.

37
00:01:59,540 --> 00:02:02,210
그리고 문제가 이러한 종류의 일을에

38
00:02:02,210 --> 00:02:07,830
사람들이 좋아하는 당신을 물어볼 것입니다, 어떻게 시간과 공간의 복잡성, 큰 O입니까?

39
00:02:07,830 --> 00:02:09,800
종종 그들은 또한 높은 수준의 질문을

40
00:02:09,800 --> 00:02:12,530
따라서, 시스템을 설계

41
00:02:12,530 --> 00:02:14,770
어떻게 코드를 배치까요?

42
00:02:14,770 --> 00:02:18,370
어떤 인터페이스, 어떤 클래스, 귀하의 시스템에 어떤 모듈이있어,

43
00:02:18,370 --> 00:02:20,900
이러한이 어떻게 함께 상호 작용합니까?

44
00:02:20,900 --> 00:02:26,130
따라서 데이터 구조 및 알고리즘뿐만 아니라 설계 시스템.

45
00:02:26,130 --> 00:02:29,180
>> 우리는 사례 연구에 뛰어 들기 전에 몇 가지 일반적인 도움말을 제공하고 있습니다.

46
00:02:29,180 --> 00:02:32,300
나는 가장 중요한 규칙은 항상 큰 소리로 생각을 할 수있다 생각합니다.

47
00:02:32,300 --> 00:02:36,980
인터뷰는 사고 과정을 보여줄 수 있어야합니다.

48
00:02:36,980 --> 00:02:39,820
면접관은 측정하기 위해 인터뷰의 요점은

49
00:02:39,820 --> 00:02:42,660
당신이 어떻게 생각하고 어떻게 문제를 통해 이동합니다.

50
00:02:42,660 --> 00:02:45,210
당신이 할 수있는 최악의 일은 전체 인터뷰 내내 수 조용입니다.

51
00:02:45,210 --> 00:02:50,090
그건 그냥 안 좋네요.

52
00:02:50,090 --> 00:02:53,230
당신은 질문을 제공하는 경우, 당신은 또한 질문을 이해하고 있는지 확인하려고.

53
00:02:53,230 --> 00:02:55,350
따라서 자신의 단어에 다시 질문을 반복

54
00:02:55,350 --> 00:02:58,920
그리고 시도는 철저하게 몇 가지 간단한 테스트 케이스를 일을하는

55
00:02:58,920 --> 00:03:01,530
당신이 질문을 이해했는지 확인합니다.

56
00:03:01,530 --> 00:03:05,510
몇 가지 테스트 케이스를 통해 작업하면 당신에게이 문제를 해결하는 방법에 대한 직관을 제공합니다.

57
00:03:05,510 --> 00:03:11,210
당신은 몇 패턴이 문제를 해결하기 위해 발견 할 수 있습니다.

58
00:03:11,210 --> 00:03:14,500
그들의 큰 팁은 좌절하지하는 것입니다.

59
00:03:14,500 --> 00:03:17,060
좌절하지 마십시오.

60
00:03:17,060 --> 00:03:19,060
인터뷰는 도전하지만, 당신이 할 수있는 최악의 일,

61
00:03:19,060 --> 00:03:23,330
침묵 할뿐만 아니라, visibly 좌절하는 것입니다.

62
00:03:23,330 --> 00:03:27,410
당신은 인터뷰에 해당 인상을주고 싶지 않아.

63
00:03:27,410 --> 00:03:33,960
한가지 당신 - 그래서, 많은 사람들이, 그들이 인터뷰로 이동,

64
00:03:33,960 --> 00:03:37,150
그들은 먼저 최선의 해결책을 찾기 위해 노력을 시도

65
00:03:37,150 --> 00:03:39,950
때 정말 눈부시게 명백한 해결책는 없습니다.

66
00:03:39,950 --> 00:03:43,500
그것은 느려질 수 있습니다, 그것은 비효율적 일 수도 있지만, 그냥 명시해야합니다

67
00:03:43,500 --> 00:03:46,210
그냥 좀 더 일을하기에 시작 지점이 있습니다.

68
00:03:46,210 --> 00:03:48,270
또한 솔루션을 지적하는 측면에서, 느린

69
00:03:48,270 --> 00:03:52,160
큰 O 시간 복잡도 나 공간의 복잡성,

70
00:03:52,160 --> 00:03:54,450
당신이 이해하는 면접관 to 보여줍니다

71
00:03:54,450 --> 00:03:57,510
이러한 문제 코드를 작성할 때.

72
00:03:57,510 --> 00:04:01,440
그래서 일단 가장 간단한 알고리즘을 마련 걸 두려워하지 말라고

73
00:04:01,440 --> 00:04:04,950
그리고 거기에서 더 나은 작동합니다.

74
00:04:04,950 --> 00:04:09,810
질문까지? 좋아,.

75
00:04:09,810 --> 00:04:11,650
>> 그럼 시작하자 첫 번째 문제에 뛰어.

76
00:04:11,650 --> 00:04:14,790
"N의 정수의 배열을 감안할 때, 배열을 shuffles 함수를 작성합니다

77
00:04:14,790 --> 00:04:20,209
N 개의 정수의 모든 순열이 동등하게 가능성이있는 것으로 같은 장소에서. "

78
00:04:20,209 --> 00:04:23,470
그리고 당신이 사용할 수있는 임의의 정수 생성기가 가정

79
00:04:23,470 --> 00:04:30,980
그 반은 범위, 0 ~ 전까지 범위의 정수를 생성합니다.

80
00:04:30,980 --> 00:04:32,970
모든 사람들이이 질문을 이해합니까?

81
00:04:32,970 --> 00:04:39,660
내가 N 개의 정수의 배열을 제공, 그리고 당신이 셔플을 원하는.

82
00:04:39,660 --> 00:04:46,050
내 디렉토리에 나는 무슨 뜻인지 설명 할 수있는 몇 가지 프로그램을 썼습니다.

83
00:04:46,050 --> 00:04:48,910
나는 셔플 20 요소의 배열을 갈거야

84
00:04:48,910 --> 00:04:52,490
-10에서 9까지,

85
00:04:52,490 --> 00:04:57,050
그리고 당신은 같은 목록을 출력하고 싶습니다.

86
00:04:57,050 --> 00:05:02,890
그래서 내 정렬 입력 배열이며, 당신이 셔플을 원하는.

87
00:05:02,890 --> 00:05:07,070
우리는 또 할거야.

88
00:05:07,070 --> 00:05:13,780
모두가 질문을 이해합니까? 좋아,.

89
00:05:13,780 --> 00:05:16,730
그럼 당신에게 달려 있습니다.

90
00:05:16,730 --> 00:05:21,220
몇 가지 아이디어는 무엇입니까? 당신은 N ^ 2, N 로그 N, N으로 할 수 있습니까?

91
00:05:21,220 --> 00:05:34,400
제안을 엽니 다.

92
00:05:34,400 --> 00:05:37,730
좋아,. 에미가 제안한 따라서 하나의 생각,

93
00:05:37,730 --> 00:05:45,300
첫번째 0에서 20 임의의 숫자, 임의의 정수, 범위를 계산합니다.

94
00:05:45,300 --> 00:05:49,840
따라서 우리의 배열이 20의 길이가 가정합니다.

95
00:05:49,840 --> 00:05:54,800
20 요소의 다이어그램에서,

96
00:05:54,800 --> 00:05:58,560
이곳은 우리의 입력 배열입니다.

97
00:05:58,560 --> 00:06:04,590
그리고 지금, 그녀의 제안은 새로운 배열을 만드는 것입니다

98
00:06:04,590 --> 00:06:08,440
그래서이 출력 배열 될 것입니다.

99
00:06:08,440 --> 00:06:12,880
그리고 내가 란드에 의해 반환 된에 따라 -

100
00:06:12,880 --> 00:06:17,580
난다면,, 17, 보자

101
00:06:17,580 --> 00:06:25,640
첫 번째 위치에 17 요소를 복사합니다.

102
00:06:25,640 --> 00:06:30,300
이제 우리는 삭제할 필요가 - 우리는 여기에 모든 요소를​​ 이동해야합니다

103
00:06:30,300 --> 00:06:36,920
이상 우리가 말에 격차와 중간에 구멍이 있는지.

104
00:06:36,920 --> 00:06:39,860
그리고 지금 우리는 과정을 반복합니다.

105
00:06:39,860 --> 00:06:46,360
이제 우리는 0과 19 사이의 새로운 임의의 정수를 선택하십시오.

106
00:06:46,360 --> 00:06:52,510
우리는 여기에서 새 I를 가지고 있고, 우리는이 위치에이 요소를 복사합니다.

107
00:06:52,510 --> 00:07:00,960
그럼 우리가 위에 항목을 이동하고 우리는 완전히 새로운 배열을 가지고 때까지이 과정을 반복합니다.

108
00:07:00,960 --> 00:07:05,890
이 알고리즘의 실행 시간은 무엇입니까?

109
00:07:05,890 --> 00:07:08,110
음,이 미치는 영향을 생각해 보자.

110
00:07:08,110 --> 00:07:10,380
우리는 모든 요소를​​ 이동합니다.

111
00:07:10,380 --> 00:07:16,800
우리가이 있는데 난을 제거하면, 우리는 왼쪽으로 한 후 모든 요소를​​ 이동합니다.

112
00:07:16,800 --> 00:07:21,600
그래서 O (n)이 비용이다

113
00:07:21,600 --> 00:07:26,100
때문에 우리가 첫 번째 요소를 제거하면?

114
00:07:26,100 --> 00:07:29,670
따라서 각 제거, 우리는 제거 -

115
00:07:29,670 --> 00:07:32,170
각 제거는 O (n)이 작업을 부과

116
00:07:32,170 --> 00:07:41,520
우리가 삭제를 향한이 때문에,이 O (N ^ 2) 셔플로 연결됩니다.

117
00:07:41,520 --> 00:07:49,550
좋아,. 그럼 좋은 시작. 좋은 시작.

118
00:07:49,550 --> 00:07:55,290
>> 또 다른 제안은 누스 셔플로 알려진 무언가를 사용하는 것입니다

119
00:07:55,290 --> 00:07:57,540
또는 피셔 - 예이츠 셔플.

120
00:07:57,540 --> 00:07:59,630
그리고 실제로 선형 시간 셔플입니다.

121
00:07:59,630 --> 00:08:02,200
그리고 아이디어는 매우 비슷합니다.

122
00:08:02,200 --> 00:08:05,160
다시 말하지만, 우리는 우리의 입력 배열을 가지고

123
00:08:05,160 --> 00:08:08,580
대신 우리의 입 / 출력을 위해 두 배열을 사용,

124
00:08:08,580 --> 00:08:13,590
우리는 우리의 질질 부분을 추적하기 위해 배열의 첫 번째 부분을 사용

125
00:08:13,590 --> 00:08:18,400
우리는 추적하고 우리는 unshuffled 부분에 대한 우리의 배열의 나머지 부분을 두십시오.

126
00:08:18,400 --> 00:08:24,330
그래서 여기 내 말 무슨 뜻인지입니다. 우리는로 시작 - 우리는 i를 선택

127
00:08:24,330 --> 00:08:30,910
0에서 20 배열입니다.

128
00:08:30,910 --> 00:08:36,150
현재 포인터는 첫 번째 인덱스를 가리키고 있습니다.

129
00:08:36,150 --> 00:08:39,590
우리는 내가 여기를 선택

130
00:08:39,590 --> 00:08:42,740
지금 우리는 스왑.

131
00:08:42,740 --> 00:08:47,690
이 5 살이 4 게 아니라면

132
00:08:47,690 --> 00:08:57,150
결과 배열은 여기 오 여기 4해야합니다.

133
00:08:57,150 --> 00:09:00,390
그리고 지금 우리는 여기에 마커를 확인합니다.

134
00:09:00,390 --> 00:09:05,770
왼쪽에있는 모든, 질질 is

135
00:09:05,770 --> 00:09:15,160
그리고 오른쪽에있는 모든이 unshuffled 있습니다.

136
00:09:15,160 --> 00:09:17,260
그리고 지금 우리는이 과정을 반복 할 수 있습니다.

137
00:09:17,260 --> 00:09:25,210
우리는 지금 1 20 사이의 임의의 인덱스를 선택합니다.

138
00:09:25,210 --> 00:09:30,650
그래서 여기에 우리의 새로운 가정 해 보겠습니다.

139
00:09:30,650 --> 00:09:39,370
이제 우리는 여기에 현재 새로운 위치로이 전을 교환.

140
00:09:39,370 --> 00:09:44,790
그래서 우리는 이런 식으로 앞뒤로 교환 않습니다.

141
00:09:44,790 --> 00:09:51,630
내가 더 구체적인 할 수있는 코드를 가져 보자.

142
00:09:51,630 --> 00:09:55,290
우리는 내가 우리의 선택 시작 -

143
00:09:55,290 --> 00:09:58,370
내가가 0으로 우리가 시작, 우리는 임의의 위치 제이를 선택

144
00:09:58,370 --> 00:10:02,420
배열의 unshuffled 부분에, 내가 N-1.

145
00:10:02,420 --> 00:10:07,280
내가 여기 온 경우, 여기 배열의 나머지 부분 사이의 임의의 색인을 선택

146
00:10:07,280 --> 00:10:12,410
우리는 스왑.

147
00:10:12,410 --> 00:10:17,550
이 셔플 귀하의 배열을하는 데 필요한 모든 코드입니다.

148
00:10:17,550 --> 00:10:21,670
질문?

149
00:10:21,670 --> 00:10:25,530
>> 음, 하나는 질문을 필요로하는 것은, 왜이 정확합니까?

150
00:10:25,530 --> 00:10:28,360
왜 모든 순열은 동일 가능성이 높습니다?

151
00:10:28,360 --> 00:10:30,410
그리고, 이것의 증명을 통과하지 않습니다

152
00:10:30,410 --> 00:10:35,970
하지만 컴퓨터 과학의 많은 문제는 유도를 통해 입증 할 수 있습니다.

153
00:10:35,970 --> 00:10:38,520
어떻게 많은 것은 유도에 대해 잘 알고있는?

154
00:10:38,520 --> 00:10:40,590
좋아,. 좋아.

155
00:10:40,590 --> 00:10:43,610
그럼 당신은 간단 유도하여이 알고리즘의 정확성을 입증 할 수

156
00:10:43,610 --> 00:10:49,540
귀하의 유도 가설이있는 곳, 그 가정

157
00:10:49,540 --> 00:10:53,290
제 셔플은 모든 순열 동등하게 가능성을 반환

158
00:10:53,290 --> 00:10:56,120
최대 우선 요소에.

159
00:10:56,120 --> 00:10:58,300
지금은, + 1을 고려하십시오.

160
00:10:58,300 --> 00:11:02,550
그리고 우리가 Google 색인 제이가 바꿔 치기를 선택하는 방식으로,

161
00:11:02,550 --> 00:11:05,230
다음은 세부 사항을 해결 -이로 연결

162
00:11:05,230 --> 00:11:07,390
이 알고리즘은 반환 이유를 적어도 전체 증명

163
00:11:07,390 --> 00:11:12,800
동등하게 가능성이 확률로 모든 순열.

164
00:11:12,800 --> 00:11:15,940
>> 좋아요, 그럼 다음 문제가 발생했습니다.

165
00:11:15,940 --> 00:11:19,170
따라서 ", 제외, 제로, postive 정수의 배열을 제공

166
00:11:19,170 --> 00:11:21,290
최대 합계를 계산하는 함수를 작성합니다

167
00:11:21,290 --> 00:11:24,720
입력 배열의 continueous subarray의. "

168
00:11:24,720 --> 00:11:28,370
여기 예를 들어, 모든 숫자가 긍정적 인 경우,이

169
00:11:28,370 --> 00:11:31,320
그리고 현재 최선의 선택은 전체 배열을하는 것입니다.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, 10과 같습니다.

171
00:11:34,690 --> 00:11:36,780
거기에 일부 제외가있는 경우

172
00:11:36,780 --> 00:11:38,690
이 경우에 우리는 처음 두 필요

173
00:11:38,690 --> 00:11:44,590
-1 및 / 또는 -3를 선택하는 것은 우리의 합계를 나타납니다 때문입니다.

174
00:11:44,590 --> 00:11:48,120
때때로 우리는 배열의 중간에 시작해야 할 수도 있습니다.

175
00:11:48,120 --> 00:11:53,500
때때로 우리 모두의 아무것도 선택하고 싶지, 그것은 아무것도 안하는 것이 좋습니다.

176
00:11:53,500 --> 00:11:56,490
그리고 가끔은 물러나야하는 것이 좋습니다

177
00:11:56,490 --> 00:12:07,510
그 후 점은 슈퍼 큰 때문입니다. 모든 아이디어는 그래서?

178
00:12:07,510 --> 00:12:10,970
(학생, 이해할 수없는) >> 그래.

179
00:12:10,970 --> 00:12:13,560
나는 -1하지 말아요 가정 해 보겠습니다.

180
00:12:13,560 --> 00:12:16,170
그런 다음 나는 1,000 20,000 선택

181
00:12:16,170 --> 00:12:18,630
아니면 3 억 선택합니다.

182
00:12:18,630 --> 00:12:20,760
음, 가장 좋은 선택은 모든 숫자를하는 것입니다.

183
00:12:20,760 --> 00:12:24,350
이 -1, 제외 임에도 불구하고,

184
00:12:24,350 --> 00:12:31,340
전체 합계는 내가 -1을하지 못한 것이 좋습니다.

185
00:12:31,340 --> 00:12:36,460
그래서 앞서 언급 한 방법 중 하나는 분명 당연한 것이 었습니다

186
00:12:36,460 --> 00:12:40,540
첫 번째와 폭력 솔루션입니다.

187
00:12:40,540 --> 00:12:44,340
이 문제의 폭력 솔루션은 무엇입니까? 응?

188
00:12:44,340 --> 00:12:46,890
[제인] 글쎄, 난 폭력 솔루션 것 같아요

189
00:12:46,890 --> 00:12:52,600
가능한 모든 조합을 (이해할 수없는)를 추가하는 것이다.

190
00:12:52,600 --> 00:12:58,250
[유] 좋아. 그럼, 제인의 아이디어는 가능한 모든을하는 것입니다 -

191
00:12:58,250 --> 00:13:01,470
나는 paraphrasing 해요 - 가능한 모든 연속 subarray을하고,

192
00:13:01,470 --> 00:13:07,840
의 합계를 계산하고 가능한 모든 연속 subarrays의 최대보십시오.

193
00:13:07,840 --> 00:13:13,310
어떻게 고유 내 입력 배열에 subarray를 식별?

194
00:13:13,310 --> 00:13:17,380
내가 뭘 두 가지 필요 하죠처럼? 응?

195
00:13:17,380 --> 00:13:19,970
(학생, 이해할 수없는) >> 맞아.

196
00:13:19,970 --> 00:13:22,130
낮은 색인과 상단 바운드 인덱스에 행

197
00:13:22,130 --> 00:13:28,300
고유 연속 subarray를 결정합니다.

198
00:13:28,300 --> 00:13:31,400
[여자 학생] 우리는 고유 한 숫자의 배열 추정 있습니까?

199
00:13:31,400 --> 00:13:34,280
[유] 아니, 그녀의 질문에 그래서, 우리는 배열을 가정 아르 수 있습니다 -

200
00:13:34,280 --> 00:13:39,000
우리 어레이는 고유 번호입니다, 그리고 대답은 '노'입니다.

201
00:13:39,000 --> 00:13:43,390
>> 우리는 우리의 폭력 솔루션, 시작 / 끝 인덱스를 사용하는 경우

202
00:13:43,390 --> 00:13:47,200
고유 지속적으로 subarray를 결정합니다.

203
00:13:47,200 --> 00:13:51,680
우리는 가능한 모든 시작 항목을 반복하면,

204
00:13:51,680 --> 00:13:58,320
모든 최종 항목에> 또는 =, 시작하고 <N에게

205
00:13:58,320 --> 00:14:05,570
당신은 합계를 계산 한 후 우리는 우리가 지금까지 본 적이있는 최대 금액을.

206
00:14:05,570 --> 00:14:07,880
이 들었나?

207
00:14:07,880 --> 00:14:12,230
이 솔루션의 가장 큰 O는 무엇입니까?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
매우 ^ 2를 향한 없습니다.

210
00:14:18,860 --> 00:14:25,250
우리는 0에서 N으로 반복합니다

211
00:14:25,250 --> 00:14:27,520
그래서 그 루프 하나.

212
00:14:27,520 --> 00:14:35,120
우리는 루프를 들어, 거의 처음부터 끝까지 다시 다른 반복합니다.

213
00:14:35,120 --> 00:14:37,640
그리고, 그 안에, 우리는 모든 항목을 요약해야

214
00:14:37,640 --> 00:14:43,810
그래서 그 루프에 다른입니다. 그래서 우리는 세 루프에 대한 중첩, N ^ 3을 갖추고 있습니다.

215
00:14:43,810 --> 00:14:46,560
좋아,. 이 시작 지점으로갑니다.

216
00:14:46,560 --> 00:14:53,180
우리 솔루션은 N ^ 3보다 더 나빠하지 않습니다.

217
00:14:53,180 --> 00:14:55,480
모두가 폭력 솔루션을 이해합니까?

218
00:14:55,480 --> 00:14:59,950
>> 좋아,. 더 나은 솔루션은 동적 프로그래밍이라는 개념을 사용하고 있습니다.

219
00:14:59,950 --> 00:15:03,040
당신은 CS124을하면되는데,이, 알고리즘 및 데이터 구조입니다

220
00:15:03,040 --> 00:15:05,680
이 기술을 잘 알고 될 것입니다.

221
00:15:05,680 --> 00:15:12,190
그리고 아이디어는 먼저 작은 문제에 대한 해결책을 구축하려고합니다.

222
00:15:12,190 --> 00:15:17,990
시작과 끝 :이 사람이 내 말 무슨 뜻인지, 우리는 현재 두 가지 걱정해야합니다.

223
00:15:17,990 --> 00:15:29,340
그리고 짜증나니까. 우리가 그 매개 변수 중 하나를 제거 할 수 있다면 무엇입니까?

224
00:15:29,340 --> 00:15:32,650
우린 우리의 원래 문제가 주어 - 하나의 아이디어에서 가깝습니다

225
00:15:32,650 --> 00:15:37,470
범위에서 subarray의 최대 합계 [O, N-1]를 찾습니다.

226
00:15:37,470 --> 00:15:47,400
그리고 지금 우리는, 우리의 현재 색인 내가, 우리가 알고있는 새로운 subproblem을 가지고

227
00:15:47,400 --> 00:15:52,520
우리는 우리가 결론을해야합니다 알아요. 우리 subarray은 현재 색인에서 끝나야합니다.

228
00:15:52,520 --> 00:15:57,640
남은 문제는 그래서, 어디 우리 subarray을 시작해야하나요?

229
00:15:57,640 --> 00:16:05,160
이 말이 돼? 좋아,.

230
00:16:05,160 --> 00:16:12,030
그래서이 일을 코딩 한 결과, 무슨 뜻인지 살펴합시다.

231
00:16:12,030 --> 00:16:16,230
codirectory에서 subarray라는 프로그램이있어

232
00:16:16,230 --> 00:16:19,470
그리고, 항목의 수를 소요

233
00:16:19,470 --> 00:16:25,550
그리고 내 질질 목록에서 최대 subarray 합을 반환합니다.

234
00:16:25,550 --> 00:16:29,920
따라서이 경우에, 우리의 최대 subarray은 3입니다.

235
00:16:29,920 --> 00:16:34,850
그리고 그건 그냥 2 1을 사용하여 갔죠.

236
00:16:34,850 --> 00:16:38,050
의 다시 실행할 수 있습니다. 또한 세입니다.

237
00:16:38,050 --> 00:16:40,950
하지만 이번에는 우리는 3를 얻었는지 확인합니다.

238
00:16:40,950 --> 00:16:46,690
우리는했다 - 우리가 3 자체를

239
00:16:46,690 --> 00:16:49,980
그것은 양쪽에 제외로 둘러싸여 있기 때문에,

240
00:16:49,980 --> 00:16:55,080
합에게 <3을 가져집니다.

241
00:16:55,080 --> 00:16:57,820
의 10 항목을 실행할 수 있습니다.

242
00:16:57,820 --> 00:17:03,200
가 7로이 시간, 우리는 선도적 인 3, 4를.

243
00:17:03,200 --> 00:17:09,450
이 시간은 8이고, 우리는 1, 4, 3를 취하여 것을을 구하십시오.

244
00:17:09,450 --> 00:17:16,310
그럼 당신에게 방법에 대한 직관을주고 우리는이 transformed 문제를 해결할 수 있습니다,

245
00:17:16,310 --> 00:17:18,890
의이 subarray를 살펴 보자.

246
00:17:18,890 --> 00:17:23,460
우리는이 입력 배열을 제공, 우리는 답은 8 알하고 있습니다.

247
00:17:23,460 --> 00:17:26,359
우리는 1, 4, 3을.

248
00:17:26,359 --> 00:17:29,090
그러나의 우리가 실제로 그 답을 얻었는지 살펴 보도록하겠습니다.

249
00:17:29,090 --> 00:17:34,160
의 이러한 인덱스의 각에 마감 된 최대 subarray 살펴 보도록하겠습니다.

250
00:17:34,160 --> 00:17:40,780
첫 번째 위치에 종료하는 최대 subarray은 무엇입니까?

251
00:17:40,780 --> 00:17:46,310
[학생] 제로. >> 제로. 그냥 -5도 취하지 않습니다.

252
00:17:46,310 --> 00:17:50,210
여기뿐만 아니라 영거야. 응?

253
00:17:50,210 --> 00:17:56,470
(학생, 이해할 수없는)

254
00:17:56,470 --> 00:17:58,960
[유] 아, 죄송 해요, 그것은 -3입니다.

255
00:17:58,960 --> 00:18:03,220
이 2 그래서이 -3입니다.

256
00:18:03,220 --> 00:18:08,690
좋아,. 그럼 -4 그 위치를 종료 할 수있는 최대 subarray이 뭐죠

257
00:18:08,690 --> 00:18:12,910
-4은 어디 있는거야? 제로.

258
00:18:12,910 --> 00:18:22,570
하나? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
자, -2가에있는 위치에서 끝나야합니다.

260
00:18:28,060 --> 00:18:39,330
따라서 6, 5, 7, 그리고 마지막 하나는 4입니다.

261
00:18:39,330 --> 00:18:43,480
이 내 항목임을 알고

262
00:18:43,480 --> 00:18:48,130
난이 인덱스의 각에 종​​료해야합니다 변환 문제에 대한,

263
00:18:48,130 --> 00:18:51,410
그리고 마지막 대답은 단지이다,에서 스윕을

264
00:18:51,410 --> 00:18:53,580
및 최대 개수를.

265
00:18:53,580 --> 00:18:55,620
따라서이 경우는 8입니다.

266
00:18:55,620 --> 00:19:00,010
이것은 최대 subarray이 색인에 끝을 의미

267
00:19:00,010 --> 00:19:04,970
그리고 전에 어딘가에 시작했다.

268
00:19:04,970 --> 00:19:09,630
모든 사람은이 변형 subarray을 이해합니까?

269
00:19:09,630 --> 00:19:22,160
>> 좋아,. 음,이에 대한 재발을 찾아 보자.

270
00:19:22,160 --> 00:19:27,990
그냥 처음 몇 항목을 생각해 보자.

271
00:19:27,990 --> 00:19:35,930
그래서 여기가, 8 0, 0, 0, 1, 5했습니다.

272
00:19:35,930 --> 00:19:39,790
그리고 거기에 여기 -2이었고, 그 6 내려 왔어.

273
00:19:39,790 --> 00:19:50,800
나는 위치에서 항목을 전화면 내가 subproblem은 (i),

274
00:19:50,800 --> 00:19:54,910
어떻게 이전 subproblem에 대한 답변을 사용할 수 있습니다

275
00:19:54,910 --> 00:19:59,360
이 subproblem 대답?

276
00:19:59,360 --> 00:20:04,550
제가 보면이 항목이 있다고 가정합니다.

277
00:20:04,550 --> 00:20:09,190
어떻게 보면 답 6 계산할 수

278
00:20:09,190 --> 00:20:18,780
이 배열이 배열의 이전 subproblems에 대한 답변의 조합? 그래?

279
00:20:18,780 --> 00:20:22,800
[여자 학생] 당신은 금액의 배열을

280
00:20:22,800 --> 00:20:25,430
위치에 바로 전, 8 있으므로

281
00:20:25,430 --> 00:20:32,170
그리고 당신은 현재 subproblem을 추가합니다.

282
00:20:32,170 --> 00:20:36,460
[유]는 그녀의 제안이 두 숫자 보는 것입니다 그래서

283
00:20:36,460 --> 00:20:40,090
이 번호와 번호입니다.

284
00:20:40,090 --> 00:20:50,130
그래서 8 subproblem에 대한 답변 (- 1 I)을 의미합니다.

285
00:20:50,130 --> 00:20:57,300
그리고의 내 입력 배열 A. 전화 할게

286
00:20:57,300 --> 00:21:01,470
위치 i를에 끝나는 최대 subarray을 찾으려면하면,

287
00:21:01,470 --> 00:21:03,980
나는 두 가지 선택이 있습니다 나도 subarray를 계속할 수

288
00:21:03,980 --> 00:21:09,790
그 이전의 색인에 종료하거나 새 배열을 시작합니다.

289
00:21:09,790 --> 00:21:14,190
나는 이전 색인에서 시작 subarray를 계속한다면

290
00:21:14,190 --> 00:21:19,260
그럼 내가 달성 할 수있는 최대 금액은 이전 subproblem에 답

291
00:21:19,260 --> 00:21:24,120
플러스 현재 배열 항목.

292
00:21:24,120 --> 00:21:27,550
그러나, 나는 또한, 새로운 subarray을 시작 선택할 수 있습니다

293
00:21:27,550 --> 00:21:30,830
이 경우의 합계는 0입니다.

294
00:21:30,830 --> 00:21:42,860
1, 플러스 현재 배열 항목 - 그래서 답은 0 최대, subproblem 전입니다.

295
00:21:42,860 --> 00:21:46,150
이 재발하지 않니?

296
00:21:46,150 --> 00:21:50,840
우리 재발는 우리가 발견 한 것처럼 subproblem 전입니다

297
00:21:50,840 --> 00:21:54,740
, 이전 subproblem의 최대 더불어 현재 배열의 항목과 동일

298
00:21:54,740 --> 00:22:01,490
이는, 이전 subarray을 계속 의미

299
00:22:01,490 --> 00:22:07,250
또는 0, 현재 인덱스에서 새 subarray를 시작합니다.

300
00:22:07,250 --> 00:22:10,060
그리고 일단 우리가 우리의 마지막 대답은 다음 솔루션이 테이블을 구축 한

301
00:22:10,060 --> 00:22:13,950
단지 subproblem 배열에서 선형 스윕을

302
00:22:13,950 --> 00:22:19,890
및 최대 개수를.

303
00:22:19,890 --> 00:22:23,330
이건 내가 무슨 말을하는지의 정확한 구현 한 것입니다.

304
00:22:23,330 --> 00:22:27,320
그래서 우리는 새로운 subproblem 배열, subproblems을 만듭니다.

305
00:22:27,320 --> 00:22:32,330
첫 번째 항목은 0 또는 첫 번째 항목, 두의 최대 중입니다.

306
00:22:32,330 --> 00:22:35,670
그리고 subproblems의 나머지 부분에 대한

307
00:22:35,670 --> 00:22:39,810
우리는 우리가 발견 한 정확한 재발을 사용합니다.

308
00:22:39,810 --> 00:22:49,960
이제 우리는 우리의 subproblems 배열의 최대 계산, 그건 최종 답변입니다.

309
00:22:49,960 --> 00:22:54,130
>> 따라서 공간이 얼마나 우리는이 알고리즘에 사용하고 있습니까?

310
00:22:54,130 --> 00:23:01,470
만 CS50를 취했다면, 당신은 매우 많은 공간을 논의하지 수 있습니다.

311
00:23:01,470 --> 00:23:07,750
음, 한가지 유의할 사항은 제가 크기 N과 함께 malloc이라는 것입니다.

312
00:23:07,750 --> 00:23:13,590
그건 당신에게 무슨 제안합니까?

313
00:23:13,590 --> 00:23:17,450
이 알고리즘은 선형 공간을 사용합니다.

314
00:23:17,450 --> 00:23:21,030
우리는 더 나은 작업을 수행 할 수 있습니까?

315
00:23:21,030 --> 00:23:30,780
당신이 최종 답을 계산 필요는 것을 알 것이 있나요?

316
00:23:30,780 --> 00:23:33,290
내 생각에 더 좋은 질문이되고, 어떤 정보

317
00:23:33,290 --> 00:23:40,680
우리는 마지막까지 모든 방법을 수행 할 필요가 없습니다합니까?

318
00:23:40,680 --> 00:23:44,280
이제, 우리는이 두 행을 보면,

319
00:23:44,280 --> 00:23:47,720
우리는, 이전 subproblem에 관심

320
00:23:47,720 --> 00:23:50,910
그리고 우리는 우리가 지금까지 본 적이 최대 관심.

321
00:23:50,910 --> 00:23:53,610
최종 답변을 계산하기 위해, 우리는 전체 배열을 필요하지 않습니다.

322
00:23:53,610 --> 00:23:57,450
우리는 마지막 번호 마지막 두 숫자 만 필요합니다.

323
00:23:57,450 --> 00:24:02,630
최대의 subproblem 배열, 마지막 번호 마지막 번호입니다.

324
00:24:02,630 --> 00:24:07,380
그래서, 사실, 우리가 함께 이러한 루프를 융합 할 수

325
00:24:07,380 --> 00:24:10,460
및 선형 공간에서 일정한 공간으로 이동합니다.

326
00:24:10,460 --> 00:24:15,830
현재 합 지금까지, 여기 subproblem 우리 subproblem 배열의 역할을 대체합니다.

327
00:24:15,830 --> 00:24:20,020
따라서 현재의 합계는, 지금까지 이전 subproblem에 대한 답입니다.

328
00:24:20,020 --> 00:24:23,450
그리고 그 합계는, 지금까지 우리의 최대의 이루어집니다.

329
00:24:23,450 --> 00:24:28,100
우리도 진행하는데로 우리는 최대를 계산합니다.

330
00:24:28,100 --> 00:24:30,890
그래서 우리는, 일정한 공간을 선형 공간에서 이동

331
00:24:30,890 --> 00:24:36,650
우리는 또한 subarray 문제에 대한 선형 해결책을 가지고 있습니다.

332
00:24:36,650 --> 00:24:40,740
>> 질문 이러한 종류의 당신은 인터뷰하는 동안 얻을 것이다.

333
00:24:40,740 --> 00:24:44,450
시간 복잡도는 무엇입니까, 공간 복잡도는 무엇인가?

334
00:24:44,450 --> 00:24:50,600
당신은 좀 더 할 수 있습니까? 주위에 유지하는 데 필요되는 부분이 있습니까?

335
00:24:50,600 --> 00:24:55,270
난 당신이 직접 수행 할 분석을 강조하기 위해 이런 짓을

336
00:24:55,270 --> 00:24:57,400
당신은 이러한 문제를 통해 최선을 다하고 있습니다.

337
00:24:57,400 --> 00:25:01,710
항상 "내가 더 잘 할 수 있습니까?"자신을 요청해야

338
00:25:01,710 --> 00:25:07,800
사실, 우리는이보다 더 할 수 있습니까?

339
00:25:07,800 --> 00:25:10,730
트릭 질문의 정렬. 당신이 필요하기 때문에, 안 돼

340
00:25:10,730 --> 00:25:13,590
최소한 문제에 대한 입력을 읽습니다.

341
00:25:13,590 --> 00:25:15,570
당신이해야 할 사실은 적어도이 문제에 대해 입력을 읽었다

342
00:25:15,570 --> 00:25:19,580
당신이 선형 시간보다 더 잘할 수 있다는 것을 의미

343
00:25:19,580 --> 00:25:22,870
당신은 일정한 공간보다 더 잘할 수 없습니다.

344
00:25:22,870 --> 00:25:27,060
그래서이 사실,이 문제에 대한 가장 좋은 솔루션입니다.

345
00:25:27,060 --> 00:25:33,040
질문이 있으십니까? 좋아,.

346
00:25:33,040 --> 00:25:35,190
>> 주식 시장 문제 :

347
00:25:35,190 --> 00:25:38,350
"긍정적, 제로, 또는 부정적인 N 개의 정수의 배열 감안할 때,

348
00:25:38,350 --> 00:25:41,680
즉, N 일 동안 주식의 가격을 나타냅니다

349
00:25:41,680 --> 00:25:44,080
당신이 할 수있는 최대 이익을 계산하는 함수를 작성

350
00:25:44,080 --> 00:25:49,350
당신이 N 일 이내에 정확하게 한 주식을 사고 팔 것을 고려. "

351
00:25:49,350 --> 00:25:51,690
기본적으로, 우리는 낮은 구입 높은 판매하고 싶습니다.

352
00:25:51,690 --> 00:25:58,580
그리고 우리는 우리가 할 수있는 최선의 이익을 파악하고 싶습니다.

353
00:25:58,580 --> 00:26:11,500
내 팁으로 돌아 간다, 어떻게 즉시 명확하고 간단한 대답은하지만 속도가 느린거야?

354
00:26:11,500 --> 00:26:17,690
그래? (학생, 이해할 수없는) >> 예.

355
00:26:17,690 --> 00:26:21,470
>> 그래서 당신은하지만 가서 주식 가격을 살펴볼 수

356
00:26:21,470 --> 00:26:30,550
에서 시간에 각 점 (이해할 수없는).

357
00:26:30,550 --> 00:26:33,990
[유] 그래, 그럼 그녀 솔루션 - 컴퓨팅 그녀의 제안

358
00:26:33,990 --> 00:26:37,380
최저와 최고를 계산 반드시 작동하지 않습니다

359
00:26:37,380 --> 00:26:42,470
가장 높은이 가장 낮은 전에 발생할 때문입니다.

360
00:26:42,470 --> 00:26:47,340
따라서이 문제에 대한 폭력 솔루션은 무엇입니까?

361
00:26:47,340 --> 00:26:53,150
나는 고유 제가 만든 이익을 결정하는 데 필요한 두 가지 사항은 무엇입니까? 맞아.

362
00:26:53,150 --> 00:26:59,410
폭력 솔루션입니다 - 그럼, 조지의 제안은 우리가 이틀 필요가있어

363
00:26:59,410 --> 00:27:02,880
독특한 두 일 이익을 결정합니다.

364
00:27:02,880 --> 00:27:06,660
그래서 우리는, 구입 / 판매 좋아, 모든 쌍을 계산

365
00:27:06,660 --> 00:27:12,850
음수 또는 양수 또는 0이 될 수있는 이익을 계산합니다.

366
00:27:12,850 --> 00:27:18,000
우리가 일의 모든 쌍으로 반복 한 후 확인하는 최대 이익을 계산합니다.

367
00:27:18,000 --> 00:27:20,330
그래서 최종 답변이 될 것입니다.

368
00:27:20,330 --> 00:27:25,730
그리고 그 해결책이 있기 때문에, O (N ^ 2)로 N 이쌍를 선택합니다 -

369
00:27:25,730 --> 00:27:30,270
당신이 마지막 일 중에서 선택할 수 있습니다 일.

370
00:27:30,270 --> 00:27:32,580
좋아, 내가 여기 폭력 솔루션으로 가지 않을거야.

371
00:27:32,580 --> 00:27:37,420
나는 N 로그 N 솔루션은이 말을거야.

372
00:27:37,420 --> 00:27:45,550
현재 N 로그 N입니다 어떤 알고리즘을 알 수 있습니까?

373
00:27:45,550 --> 00:27:50,730
속임수의 질문이 아니 란다.

374
00:27:50,730 --> 00:27:54,790
>> 정렬을 병합합니다. 병합 정렬은 N 로그 N입니다

375
00:27:54,790 --> 00:27:57,760
그리고 사실,이 문제를 해결하는 한 가지 방법은 사용하는 것입니다

376
00:27:57,760 --> 00:28:04,400
라는 아이디어 병합 정렬 종류는 일반적으로 나눠서 맡을.

377
00:28:04,400 --> 00:28:07,570
다음과 같이 그리고 아이디어입니다.

378
00:28:07,570 --> 00:28:12,400
당신은 최고 거래를 계산 / 왼쪽 반으로 쌍을 판매하고 싶습니다.

379
00:28:12,400 --> 00:28:16,480
당신은 두 일 동안의 첫 번째 N과 함께 할 수있는 최선의 이익을 찾아보세요.

380
00:28:16,480 --> 00:28:19,780
그럼 당신은 최고의 거래를 oompute / 오른쪽 절반에 쌍을 판매 할

381
00:28:19,780 --> 00:28:23,930
2 일간 그래서 마지막 n.

382
00:28:23,930 --> 00:28:32,400
이제 문제는 어떻게 우리가 다시 함께 이러한 솔루션을 병합 않습니다인가요?

383
00:28:32,400 --> 00:28:36,320
그래? (학생, 이해할 수없는)

384
00:28:36,320 --> 00:28:49,890
좋아요 >>. 그럼 내가 그림을 그려 보자.

385
00:28:49,890 --> 00:29:03,870
그래? (조지, 이해할 수없는)

386
00:29:03,870 --> 00:29:06,450
정확히 >>. 조지의 솔루션은 정확히 맞아.

387
00:29:06,450 --> 00:29:10,040
그의 제안은 그래서 먼저, 가장 구매 / 판매 쌍을 계산

388
00:29:10,040 --> 00:29:16,050
그리고 왼쪽 반으로 발생합니다 그러니, 왼쪽, 왼쪽 것을이라고 불러.

389
00:29:16,050 --> 00:29:20,790
최선의 오른쪽 절반에서 발생하는 쌍을 구입 / 판매하고 있습니다.

390
00:29:20,790 --> 00:29:25,180
우리는이 두 숫자를 비교한다면, 우리는 사건을 누락

391
00:29:25,180 --> 00:29:30,460
여기 구입하고 오른쪽 절반 어딘가에 팔.

392
00:29:30,460 --> 00:29:33,810
우리는 왼쪽 반으로 구입, 오른쪽 반으로 판매하고 있습니다.

393
00:29:33,810 --> 00:29:38,490
그리고 두 반쪽에 걸쳐 최고의 구매 / 판매 쌍을 계산하는 가장 좋은 방법은

394
00:29:38,490 --> 00:29:43,480
여기에 최소 계산하고 여기에 최대를 계산하는 것입니다

395
00:29:43,480 --> 00:29:45,580
과의 차이를.

396
00:29:45,580 --> 00:29:50,850
구매 / 판매 쌍은 여기가 발생하여 두 경우를 따라서

397
00:29:50,850 --> 00:30:01,910
여기뿐 또는 두 가지 모두 절반에이 세 숫자에 의해 정의됩니다.

398
00:30:01,910 --> 00:30:06,450
다시 우리의 솔루션을 병합에 대한 우리의 알고리즘은 자

399
00:30:06,450 --> 00:30:08,350
우리는 최고의 구매 / 판매 쌍을 계산하려면

400
00:30:08,350 --> 00:30:13,120
우리가 왼쪽 부분에 구입하여 오른쪽 절반에 팔.

401
00:30:13,120 --> 00:30:16,740
그리고 할 수있는 가장 좋은 방법은, 최초의 반으로 최저 가격을 계산하는 것입니다

402
00:30:16,740 --> 00:30:20,360
가장 오른쪽 반 가격과의 차이를.

403
00:30:20,360 --> 00:30:25,390
그 결과 세 이윤은이 세 숫자는, 당신은 세 가지의 최대를

404
00:30:25,390 --> 00:30:32,720
그리고 그 말은 당신이 첫 번째와 마지막 일 동안 만들 수있는 최선의 이익입니다.

405
00:30:32,720 --> 00:30:36,940
다음은 중요한 선은 빨간색입니다.

406
00:30:36,940 --> 00:30:41,160
이 왼쪽 반으로 답을 계산하는 재귀 호출입니다.

407
00:30:41,160 --> 00:30:44,760
이것은 오른쪽 절반에 답을 계산하는 재귀 호출입니다.

408
00:30:44,760 --> 00:30:50,720
이 두 루프에 각각 왼쪽과 오른쪽 절반에 분, 최대 계산합니다.

409
00:30:50,720 --> 00:30:54,970
지금은 모두 절반에 걸쳐 이익을 계산

410
00:30:54,970 --> 00:31:00,530
그리고 최종 답은이 세의 최대입니다.

411
00:31:00,530 --> 00:31:04,120
좋아,.

412
00:31:04,120 --> 00:31:06,420
>> 그럼, 물론, 우리는 알고리즘을 가지고 있지만 더 큰 문제는

413
00:31:06,420 --> 00:31:08,290
이 시간 복잡도는 무엇인가?

414
00:31:08,290 --> 00:31:16,190
그리고 병합 정렬을 언급하는 이유는이 양식에 대한 답변을 나눌 것입니다

415
00:31:16,190 --> 00:31:19,200
두 개로하고 다시 우리의 솔루션을 통합

416
00:31:19,200 --> 00:31:23,580
정확히 병합 정렬의 형태입니다.

417
00:31:23,580 --> 00:31:33,360
그래서 나는이 기간을 통해 가자.

418
00:31:33,360 --> 00:31:41,340
우리는 단계의 수를 될 수있는 기능을 t (N)을 정의하는 경우

419
00:31:41,340 --> 00:31:50,010
N 일 경우,

420
00:31:50,010 --> 00:31:54,350
두 재귀 호출

421
00:31:54,350 --> 00:32:00,460
각 t (N / 2), 비용 거예요

422
00:32:00,460 --> 00:32:03,540
그리고 이러한 호출의 두 종류가 있습니다.

423
00:32:03,540 --> 00:32:10,020
지금은, 왼쪽 반 이상을 계산해야합니다

424
00:32:10,020 --> 00:32:17,050
난 상 / 2 시간, 플러스 오른쪽 절반의 최대에 수행 할 수있는.

425
00:32:17,050 --> 00:32:20,820
그래서 막 습니됩니다.

426
00:32:20,820 --> 00:32:25,050
그리고 어떤 일정한 일을 플러스.

427
00:32:25,050 --> 00:32:27,770
그리고이 재발 방정식

428
00:32:27,770 --> 00:32:35,560
정확히 병합 정렬의 재발 방정식입니다.

429
00:32:35,560 --> 00:32:39,170
그리고 우리는 병합 정렬 N 로그 N 시간 것을 알고있다.

430
00:32:39,170 --> 00:32:46,880
따라서, 우리의 알고리즘은 로그 N 시간 습니하고 있습니다.

431
00:32:46,880 --> 00:32:52,220
이 반복 않니?

432
00:32:52,220 --> 00:32:55,780
이 아주 간단한 뉴스 레터를 살펴 :

433
00:32:55,780 --> 00:32:59,170
T (N)은 최대 이익을 계산하는 단계의 수입니다

434
00:32:59,170 --> 00:33:02,750
N 일의 과정 동안.

435
00:33:02,750 --> 00:33:06,010
우리는 재귀 호출을 분할하는 방법

436
00:33:06,010 --> 00:33:11,980
, 첫 번째 N / 2 일에 우리의 솔루션을 호출하는 것입니다

437
00:33:11,980 --> 00:33:14,490
그래서 한 통화가 ...

438
00:33:14,490 --> 00:33:16,940
그리고 우리는 후반에 다시 전화하십시오.

439
00:33:16,940 --> 00:33:20,440
그럼 두 통화입니다.

440
00:33:20,440 --> 00:33:25,310
그리고 우리는, 우리가 선형 시간에 수행 할 수있는, 왼쪽 부분에 최소를 찾을 수

441
00:33:25,310 --> 00:33:29,010
우리가 선형 시간에 할 수있는 오른쪽 절반의 최대를 찾습니다.

442
00:33:29,010 --> 00:33:31,570
따라서 N / 2 + N / 2는 N입니다.

443
00:33:31,570 --> 00:33:36,020
그럼 우리가 연산을하는 것입니다 어떤 일정한 작업을 수 있습니다.

444
00:33:36,020 --> 00:33:39,860
이 반복 방정식은 정확히 병합 정렬의 재발 방정식입니다.

445
00:33:39,860 --> 00:33:55,490
따라서, 우리 셔플 알고리즘은 또한 N N를 기록합니다.

446
00:33:55,490 --> 00:33:58,520
따라서 공간이 얼마나 우리를 사용하고 있습니까?

447
00:33:58,520 --> 00:34:04,910
가 코드로 돌아가 보자.

448
00:34:04,910 --> 00:34:09,420
>> 더 나은 질문은 얼마나 많은 스택 프레임을 우리는 어느 특정 순간에해야합니까 무엇입니까?

449
00:34:09,420 --> 00:34:11,449
우리는 재귀를 사용하고 있기 때문에,

450
00:34:11,449 --> 00:34:23,530
스택 프레임의 수는 우리의 공간 사용을 결정합니다.

451
00:34:23,530 --> 00:34:29,440
가 N = 8을 고려하자.

452
00:34:29,440 --> 00:34:36,889
우리는 8 일 셔플 전화

453
00:34:36,889 --> 00:34:41,580
처음 네 항목에 셔플를 호출됩니다,

454
00:34:41,580 --> 00:34:46,250
이는 처음 두 항목에 대한 셔플를​​ 호출합니다.

455
00:34:46,250 --> 00:34:51,550
그럼 우리 스택입니다 - 이건 우리의 스택입니다.

456
00:34:51,550 --> 00:34:54,980
그리고 우리는 1 일에 다시 셔플 전화

457
00:34:54,980 --> 00:34:58,070
그리고 우리의 기본 케이스가 뭔지, 그래서 우리는 즉시 반환합니다.

458
00:34:58,070 --> 00:35:04,700
우리가 이렇게 많은 스택 프레임 이상이 있습니까?

459
00:35:04,700 --> 00:35:08,880
아니, 우리는 호출을 할 때마다 때문에,

460
00:35:08,880 --> 00:35:10,770
셔플에 재귀 호출,

461
00:35:10,770 --> 00:35:13,950
우리는 절반으로 크기를 나눕니다.

462
00:35:13,950 --> 00:35:17,020
우리는 어느 특정 순간에이 스택 프레임의 최대 수 있도록

463
00:35:17,020 --> 00:35:28,460
로그 N 스택 프레임의 순서에 있습니다.

464
00:35:28,460 --> 00:35:42,460
각 스택 프레임은 일정한 공간이

465
00:35:42,460 --> 00:35:44,410
공간의 따라서 총 금액

466
00:35:44,410 --> 00:35:49,240
우리가 사용하는 공간의 최대 금액은 O (로그 n)이 공간입니다

467
00:35:49,240 --> 00:36:03,040
여기서 n은 일 수 있습니다.

468
00:36:03,040 --> 00:36:07,230
>> 지금, 항상 스스로에게 물어, "우리가 더 잘할 수 있을까?"

469
00:36:07,230 --> 00:36:12,390
그리고 특히, 우리는 이미 해결 한 문제이를 줄일 수 있습니다?

470
00:36:12,390 --> 00:36:20,040
힌트 : 우리는이 전에 다른 두 문제를 논의하고 셔플 않을거야.

471
00:36:20,040 --> 00:36:26,200
우리는 최대 subarray 문제에이 주식 시장 문제를 변환 할 수 있습니다.

472
00:36:26,200 --> 00:36:40,100
우리가 어떻게이 작업을 수행 할 수 있습니까?

473
00:36:40,100 --> 00:36:42,570
둘 중 하나? 에미?

474
00:36:42,570 --> 00:36:47,680
(에미, 이해할 수없는)

475
00:36:47,680 --> 00:36:53,860
[유] 그렇지.

476
00:36:53,860 --> 00:36:59,940
최대 subarray 문제 자,

477
00:36:59,940 --> 00:37:10,610
우리는 지속적으로 subarray으로 합계를 찾고 있습니다.

478
00:37:10,610 --> 00:37:16,230
그리고 주식의 문제에 대한 에미의 제안,

479
00:37:16,230 --> 00:37:30,720
변경 또는 델타를 고려합니다.

480
00:37:30,720 --> 00:37:37,440
그리고이의 사진입니다 -이 주식의 가격입니다,

481
00:37:37,440 --> 00:37:42,610
하지만 각 연속 일 사이의 차이를 가져 갔다면 -

482
00:37:42,610 --> 00:37:45,200
그래서 우리는 최고 가격이 최대 수익을 우리가 할 수있는 것을 볼

483
00:37:45,200 --> 00:37:50,070
우리가 구매 및 여기에 판매하는 경우입니다.

484
00:37:50,070 --> 00:37:54,240
그러나가 지속적으로 살펴 보자 -가 subarray 문제 살펴 보도록하겠습니다.

485
00:37:54,240 --> 00:38:02,510
그래서 여기, 우리는 할 수 있습니다 - 여기에서 여기로 이동,

486
00:38:02,510 --> 00:38:08,410
우리는 긍정적 인 변화를 가지고 있고, 그 다음에 여기서으로 떠날 우리는 부정적인 변화가 있습니다.

487
00:38:08,410 --> 00:38:14,220
하지만, 우리가 큰 긍정적 인 변화가 여기에서 여기로 이동.

488
00:38:14,220 --> 00:38:20,930
그리고 이러한 우리의 최종 이익을 얻을 요약 할 사항입니다.

489
00:38:20,930 --> 00:38:25,160
그럼 우리가 더 많은 부정적인 변화 자네가 있습니다.

490
00:38:25,160 --> 00:38:29,990
우리의 최대 subarray 문제로 우리의 재고 문제를 감소하기위한 핵심

491
00:38:29,990 --> 00:38:36,630
일 사이의 델타를 고려하는 것입니다.

492
00:38:36,630 --> 00:38:40,630
그래서 우리는, 삼각지라는 새로운 배열을 생성

493
00:38:40,630 --> 00:38:43,000
, 0이 될 수있는 첫 번째 항목을 초기화

494
00:38:43,000 --> 00:38:46,380
다음 각 삼각주은 (i), 차이 것을 알려

495
00:38:46,380 --> 00:38:52,830
내 입력 배열은 (i), 그리고 배열 ​​(I - 1).

496
00:38:52,830 --> 00:38:55,530
그럼 우리가 최대 subarray에 대한 일상적인 프로 시저를 호출

497
00:38:55,530 --> 00:39:01,500
델타의 배열에 전달.

498
00:39:01,500 --> 00:39:06,440
그리고 최대 subarray은 선형 시간, 때문에

499
00:39:06,440 --> 00:39:09,370
이 감소,이 델타 배열을 만드는 과정,

500
00:39:09,370 --> 00:39:11,780
또한 선형 시간

501
00:39:11,780 --> 00:39:19,060
그리고 주식에 대한 최종 해결책은 O (n)이 작동 플러스 O (n)이 작품, 여전히 O (n)이 작품이다.

502
00:39:19,060 --> 00:39:23,900
그래서 우리는 우리의 문제에 대한 선형 시간 해결책을 가지고 있습니다.

503
00:39:23,900 --> 00:39:29,610
모든 사람들이 이러한 변화를 이해합니까?

504
00:39:29,610 --> 00:39:32,140
>> 당신은 항상 가지고 있어야한다고 일반적으로 좋은 생각

505
00:39:32,140 --> 00:39:34,290
당신이 보는 것을 새로운 문제를 줄이기 위해 노력하고 있습니다.

506
00:39:34,290 --> 00:39:37,700
그것은 오래된 문제에 익숙 경우,

507
00:39:37,700 --> 00:39:39,590
오래된 문제에를 줄여보십시오.

508
00:39:39,590 --> 00:39:41,950
그리고 당신은 당신이 이전 문제에 사용한 모든 도구를 사용할 수 있는지

509
00:39:41,950 --> 00:39:46,450
새로운 문제를 해결합니다.

510
00:39:46,450 --> 00:39:49,010
따라서 포장을, 기술 면접은 도전하고 있습니다.

511
00:39:49,010 --> 00:39:52,280
이러한 문제는 아마도 더 어려운 문제 중 일부입니다

512
00:39:52,280 --> 00:39:54,700
당신은 인터뷰에서 볼 수 있다는

513
00:39:54,700 --> 00:39:57,690
당신은 방금 적용하는 모든 문제를 이해하지 않는 경우, 그래서 괜찮아.

514
00:39:57,690 --> 00:40:01,080
이것들은 점점 더 어려워 문제 중 일부입니다.

515
00:40:01,080 --> 00:40:03,050
연습, 연습, 연습.

516
00:40:03,050 --> 00:40:08,170
나는 유인물에 많은 문제를했다, 그래서 확실히 그를 확인하시기 바랍니다.

517
00:40:08,170 --> 00:40:11,690
그리고 인터뷰에서 행운을 빌어 요. 내 모든 자료는이 링크에 게시되어 있습니다

518
00:40:11,690 --> 00:40:15,220
내 고위 친구 중 하나는, 모의 기술 면접을 할 제공해 왔습니다

519
00:40:15,220 --> 00:40:22,050
당신이 관심 있다면, 이메일이 이메일 주소 야오 윌.

520
00:40:22,050 --> 00:40:26,070
당신은 몇 가지 질문이있는 경우, 당신은 날 요청할 수 있습니다.

521
00:40:26,070 --> 00:40:28,780
당신들은 기술 인터뷰에 관한 특정 질문이 있습니까

522
00:40:28,780 --> 00:40:38,440
또는 우리가 지금까지 본 적없는 문제가 있습니까?

523
00:40:38,440 --> 00:40:49,910
좋아,. 음, 인터뷰에서 행운을 빌어 요.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]