8강 - 병합 정렬(Merge Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #8 ]

Рет қаралды 48,748

동빈나

Күн бұрын

8강 - 병합 정렬(Merge Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #8 ] 강의 동영상입니다.

Пікірлер: 44

@standingdol3648 6 жыл бұрын

와....알고리즘 시험 칠때도 이해못하고 암기함걸 이재야 이거보고 알아가네요 굳

@serinheo 2 жыл бұрын

진짜..진짜...이해 잘 돼요 ㅠㅠㅠㅠ 이런 영상 공유해주셔서 너무 감사합니다

@kimjiyoung5797 3 жыл бұрын

와.. 마침내 이해함. 동빈나 스승님 고맙습니댜

@choogyullee2818 Жыл бұрын

당신이 최고입니다.

@jjwmn 6 жыл бұрын

저는 미국에 사는데 내일 모레 c++ final 있어요 진짜 일년동안 뭐 배웠나 싶었는데 이거 보고 겨우 이해합니다ㅋㅋㅋㅋㅋ 내년에 java 는 어떻게 들을까 싶네요ㅜㅜㅜㅋㅋㅋㅋㅋ 완전 video thank you so much 에요!!

@MyMusicHealer82 4 жыл бұрын

미쿡사는게부럽네요..개발자천국

@user-kj1ss5bw3n 2 жыл бұрын

이해가 너무 잘됩니다 감사합니다^^

@AsdFg-g5p 3 жыл бұрын

교수님 강의보다 훨씬 이해가 잘됩니다,,, 감사합니다 ㅠㅜ

@jeonie9682 3 жыл бұрын

진짜 천재시구나..

@위설아-b8f 4 жыл бұрын

만냑 가피 가플

@bowrain7880 4 жыл бұрын

좋은 강의 감사합니다~

@jjj5999 6 жыл бұрын

파이썬 강의 빨리 올려주세요! 현기증 난단 말이에요! 핡짝!!핡짝!!

@user-rw2eo6dn7g Жыл бұрын

와 대박 제 은인입니다

@오동훈-x8o 4 жыл бұрын

혹시 12:30초 에서 for(int t=m; t

@김소진-w5y 3 жыл бұрын

밑에 main 함수 보시면 mergeSort (array, 0, number - 1)라고 되어 있네요, 이미 n이 number보다 1 작은 수 입니다!

@phj8010 22 күн бұрын

int main(void){} 안에 int array[number] 에서 number이 빨간줄 뜨면서 "식에 상수값이 있어야 합니다."라고 뜨는데 이건 어떻게 해야하나요..?

@로션-f8l 4 жыл бұрын

9:38 저 두개가 같은 middle값이라고 하셨는데, 그럼 j = middle + 1 하는 이유가 뭘까요.. i를 첫번째 점으로 했으면, j도 첫번째 점인 그냥 middle로 해야하는 것 아닌가요??

@flyio8307 4 жыл бұрын

i는 시작부터 중간까지(middle)까지 j는 중간부터 끝까지 가야해서 중간다음인 middle+1부터 하는거에요.

@김정우-x6z 3 жыл бұрын

오홍홍 좋아용

@Doppio_00 3 жыл бұрын

갠적으로 퀵정렬보다는 훨씬 어려웟음 ㅠ 다른거보다 저걸 잘 읽엇어야함 일단 반으로 다 쪼개고 난 다음 나중에 합친다는걸 잘 읽엇어야댐 ㅠ_ㅠ 거참 콜롬버스 달걀처럼 누가 해놓은거 보기 전에는 디지게 어렵떠니 코드는 또 왜르케 간결한거임 이렇게 간결하게 정렬을 구현하다니 헟참나

@최세훈-b7p 4 жыл бұрын

if(i > middle) 부분 설명좀 해주실 분 계신가요? int i = m 이라고 선언이 되어있습니다. 5 7 / 6 8이라는 예시가 있다고 가정 / 5가 k의 배열 속으로 먼저 삽입된 후 를 가정하여 if( i > middle)이 선언되었다 하였을 때, 동영상을 통해 학습한 것으로는 middle의 값은 5 7 / 6 8 이라는 지점은 7 과 6의 값(0부터 시작시 1과 2의 지점) 가르키는 것이라고 이해하고 있습니다. 이러한 상황 속에서 i 값이 middle 값보다 커질 수 있는게 어떻게 가능한지 궁금합니다.

@임현강-w9g 4 жыл бұрын

middle이 7, 6 둘 다 가리키고 있는 것이 아닙니다. 말씀하신 경우에서 middle은 7이고 j가 6인 것입니다. 즉, middle은 왼쪽 덩어리 (이 경우 5 7)의 끝부분을 가리킵니다. ( middle값을 (m + n) / 2 로 잡아줬는데 5 7 6 8이 전체 배열이라고 치면 5 -> 0, 8 -> 3의 인덱스를 갖고 '/'연산은 몫만 반환하기 때문에 1반환. 즉, 7만을 가리키는 것이 맞음 ) i는 처음에 5로 시작해서 5가 들어가고나면 7로 넘어갑니다. 그 다음엔 j가 6에서 시작하여 6이 들어가고 8로 넘어갑니다. 그럼 이제 i == 7, j == 8인 상태에서 둘을 비교하고 더 작은 i가 들어가게면서 mid+1 ( 최초의 j값 )을 가리키게 됩니다. 이제 if (i > middle)인 경우가 발생하였고 이는 "왼쪽 덩어리 다 들어갔으니 오른쪽 덩어리 전부 갖다 넣으면 됨"을 의미합니다. 아마 그림때문에 조금 헷갈리신 것 같은데 5 7 / 6 8 은 서로 다른 두개의 배열이 아닙니다. 사실은 하나의 배열이고 두 덩어리처럼 사용하기 위해서 인덱스로만 구분해놓은 것입니다. 동영상에서 언급된 "mid부분이 사실 실제 메모리상으론 붙어있는 것이다"라는 말이 이것 때문입니다. 참고로 한 쪽 덩어리가 모두 들어갔을 때 나머지 덩어리를 전부 그대로 넣어주면 되는 이유는 머지소트에서 말하는 머지(병합)는 각각 정렬이 되어있는 두 덩어리를 합치면서 정렬을 해주는 것이기 때문입니다. 두 덩어리의 가장 앞 원소 둘 중에 가장 작은 값이 있을테니 그것을 비교하여 넣어주는 것이고, 한 쪽 덩어리가 모두 들어갔다면 나머지는 처음 조건에 의해 이미 정렬이 되어있는 상태이니 그대로 넣어주기만 하면 되는 것입니다.

@kyh4112 4 жыл бұрын

제가 이해를 제대로 한건지 확인부탁드릴게요ㅠ 예를들어 i= 6 7 / j= 4 8이라고 한다면 4 6 7 ~순으로 배열이 되는데 여기서 보면 i가 먼저 배열이 끝나잖아요.(4부터 8까지. 즉 끝까지 배열이 되기 전에 i인 6과 7은 정렬 완료) i가 먼저 배열이 끝난다고 쓴걸 (i>middle)이라고 표현한게 여기서 i=6인거고 middle (7+4)/2=5.5 따라서 i>middle이라는 말인거죠?

@임현강-w9g 4 жыл бұрын

@@kyh4112 i > middle은 왼쪽배열(사실은 두개의 배열 중 왼쪽 배열이 아니라 하나의 배열을 두개처럼 보기 위해 인덱스로 구분한 것이고 그 중 왼쪽부분) 의 모든 원소가 먼저 끝나는 경우를 말하는 게 맞습니다. ( 반대로 오른쪽 배열이 먼저 끝났으면 if (i > middle) ~~ else ~~ 에서 else쪽으로 넘어갈 것입니다.) 뒤에 말씀하신 부분은 조금 틀렸습니다. i, j, k, middle은 모두 '인덱스'를 의미합니다. 배열의 원소를 나타내는 변수가 아닙니다. ( 본인께선 인덱스가 아닌 원소값으로 말씀하셨습니다. ) 6 7 / 4 8 의 경우에서 간략히 읊어보겠습니다. start == 0 이고 end == 3입니다. ( 인덱스 ) middle = ( i + j ) / 2 이기 때문에 1이 됩니다. i = start 이기 때문에 i는 0 j = middle + 1이기 때문에 2가 됩니다. 즉, 두개의 배열 ( 거듭 강조하지만 실제로 두개의 배열인 것이 아니라 하나의 배열을 두개처럼 보기 위해서 인덱스로 구분한 것임 ) 중에서 왼쪽 배열의 첫번째 인덱스 == i, 왼쪽 배열의 마지막 인덱스 == middle, 오른쪽 배열의 첫번쨰 인덱스 == j가 된 것입니다. 숫자로 따져보면 원소 6의 인덱스 0이 i 원소 7의 인덱스 1이 middle 원소 4의 인덱스 4가 j가 되어있는 상태입니다. 4가 빠지면서 j는 3으로 바뀌어 8의 인덱스를 나타냄 6이 빠지면서 i는 1로 바뀌어 7의 인덱스를 나타냄 ( 이때 i == middle ) 7이 빠지면서 i는 2로 바뀌어서 원래 4의 인덱스를 나타냄 ( 이떄 i > middle ) while( i

@kyh4112 4 жыл бұрын

@@임현강-w9g 와 대박 이해 안할수가 없네요. 감사합니다ㅠ 이해했어요:) 복받으세요~

@kingtotoro Жыл бұрын

@@임현강-w9g 현강님 설명 덕분에 이해했습니다. 영상에서 Middle과 n을 설명하는 그림이 좀 많이 헷갈리게 나와있네요

@user-id9dd7hi2o 2 жыл бұрын

함수를 만들때 void merge(int * a ~~~ 이렇게 쓰는거랑 void merge(int a[] ~~~ 랑 무슨 차이가 나는 건가요

@skh77017 Жыл бұрын

갓동빈 ㄷㄷ 이거보고 바로 손코딩함

@user-hw5iu5ol2w 4 жыл бұрын

배열의 길이를 변수로 설정하시면 안돼요

@김흰둥이-i9l 4 жыл бұрын

[병합 정렬] 절반으로 나누고 병합하면서 정렬한다 mergeSort(a, m, middle); (left는 왼쪽으로 나눌게 없어질때까지 실행된다) mergeSort(a, middle + 1, n); (right는 left가 끝나면 실행된다) merge(a, m, middle, n); (right가 끝나면 병합이 실행된다) 예시 7 6 5 8 3 5 9 1 1. left가 실행된다 7 6 5 8 -> 7 6 -> 7 2. left가 끝났으니 right가 실행된다 6 3. right가 끝났으니 merge함수가 실행된다 7과 6을 비교 후 6 7로 정렬 4. 정렬될 때까지 반복한다 전체적인 실행순서 7 6 5 8 -> 7 6 -> 7 -> 6 -> merge(6, 7) -> 5 8 -> 5 -> 8 -> merge(5, 8) -> merge(5, 6, 7, 8) -> merge(1, 3, 5, 5, 6, 7, 8, 9) -> 1 3 5 5 6 7 8 9 3 5 9 1 -> 3 5 -> 3 -> 5 -> merge(3, 5) -> 9 1 -> 9 -> 1 -> merge(1, 9) -> merge(1, 3, 5, 9)

@thugken 2 жыл бұрын

살짝 길잃을뻔했는데 설명 감사합니다 ㅠㅠ

@복잡볶음면 5 жыл бұрын

mergesort 재귀함수에서 계속 나누면서 병합하는데 그럼 8>4>2>1 이렇게 나누는건데 재귀함수안에 merge함수도 들어가있으니까 4 4 로 쪼갰을떄 이미 정렬이 되는거 아닌가요 ?ㅠㅠ

@user-kt4nr8vp5w 5 жыл бұрын

merge 부분는 mergesort에서 제일끝에 있죠 .즉 각 mergesort함수가 종료되기 전에 merge병합 되는 겁니다. 8,4,2,1 분할하며 내려갈때까지 mergesort함수들은 모두 종료 되지않아요 다 열려 있죠 . 그러다가 이제 1부터 올라오면서 병합하며 각 함수들이 종료됩니다. 이해안되시면 n을 작게해서 직접 코드순에 따라 그려보세요.