해결된 질문
24.09.16 19:31 작성
·
40
0
답변 3
0
2024. 09. 19. 00:28
안녕하세요, yys125님의 질문의 의도가 정확하게 제게 전달되었는지는 모르겠습니다만,
우선 merge 함수의 동작 자체는 옳게 이해하셨습니다.
최초에 arr[0], arr[1]만 merge 함수에 들어오면 말씀하신 대로 동작합니다. 각각 복사되고, 작은 것부터 앞에서 부터 꽂힙니다.
문제는 "뒤에 알아서 배열이 붙나요?"인데요,
이 부분은 mergeSort에서 재귀적으로 다시 mergeSort를 부른다는 것을 해석 못하신 것 같습니다.
지금 mergeSort는 전부 다 일일이 쪼개기 어려운 순간까지 배열을 잘게 나눕니다. 그 과정이 재귀적으로 되는 것입니다.
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
이 부분을 보면, 위의 2줄의 코드를 통해 m까지, m+1부터로 쪼개는 것을 알 수 있습니다.
그리고 그것이 모두 각각 리턴 받아서 합쳐진 것들을 합치는 것입니다.
이게 글로는 설명하기 어려워서 결국 하나씩 해보셔야 하는건데요,
[28, 9, 1, 10] 이 부분도 모두 나뉘어서 각각의 merge를 수행해서 돌아오게 됩니다.
일단, 값을 계산하려고 하지 마세요.
"쪼개는 것만 먼저"해보시길 권장드립니다.
올려주신 이미지처럼 줄로 긋되, 아래 내용을 쓰지 마세요.
mergeSort(arr, 0, 5)가 들어갔습니다. 이것을 계속 쪼개서 선만 만드세요.
그리고 그것에 대한 리턴은 "본인을 부른 함수로 전달해줘야 합니다."
그게 재귀함수의 정의입니다.
예를 들면,
mergeSort(arr, l, m)에서 최초 값을 불렀으면, 그 첫줄로 돌아가야 합니다.
지금 올려주신 이미지 상으로는 옆에 있는 것과 바로 merge하려고 하니 헷갈리시는 것 같습니다.
처음부터 모든 배열을 쪼개서 생각해야 합니다.
제 해설은 다시 글로 드려도 본 영상 9:15 시작만큼 해설해드리기가 어렵습니다.
왼쪽 부분, 오른쪽 부분을 나눠가면서 다시 작성한 것을 이미지로 대댓글 올려주시면
그 상태에서 다시 답변드리도록 하겠습니다!
0
0
안녕하세요, 인프런 AI 인턴입니다. yys 125님.
merge 함수의 동작 방식에 대해 궁금해 하시는군요. merge 함수는 합병 정렬(merge sort)의 핵심 부분으로, 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 역할을 합니다.
먼저, 기본적인 merge 함수의 동작 방식을 간단히 설명드리겠습니다. 이후 예제를 통해 자세히 살펴보겠습니다.
merge(arr, left, mid, right)
에서 arr
은 대상 배열, left
와 right
는 병합할 부분의 시작과 끝 인덱스, mid
는 중간 인덱스입니다.arr[left..mid]
와 arr[mid+1..right]
두 개의 정렬된 부분 배열을 가정합니다.말씀하신 예제의 문맥에서 다음과 같은 순서로 진행됩니다.
merge(arr, 0, 0, 1)
arr[left..mid]
=> arr[0..0]
=> [51]
arr[mid+1..right]
=> arr[1..1]
=> [31]
51 > 31
이므로 결과 배열의 첫 번째 요소는 31
.[51]
이 남아있으므로 결과 배열에 추가됩니다.[31, 51, 28, 9, 1, 10]
merge(arr, 0, 1, 2)
arr[left..mid]
=> arr[0..1]
=> [31, 51]
arr[mid+1..right]
=> arr[2..2]
=> [28]
31 > 28
이므로 결과 배열의 첫 번째 요소는 28
.31 < 51
이므로 결과 배열의 두 번째 요소는 31
.[51]
이 남아있으므로 결과 배열에 추가됩니다.[28, 31, 51, 9, 1, 10]
이해가 잘 가지 않으신다면, 질문의 아래 URL을 확인하시면 도움이 될 것 같습니다.
result[i]++
의 결과값에 대해 이해하는 과정을 설명합니다.저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.