merge 함수 자세한 동작 방법

(2025) 일주일만에 합격하는 정보처리기사 실기

정렬 스페셜 - 합병정렬

해결된 질문

작성

merge함수 상세 동작을 풀어보고싶은데 너무어렵습니다. 자세하게 설명 한 번 해주셨으면 좋겠습니다ㅜ

1번째 merge함수인

merge(arr,0,0,1)을 수행하면 arr[0]에는 31이 들어가고 arr[1]에는 51이 들어가고 종료되는 것이 아닌가요?

31, 51 다음에 28, 9, 1, 10은 자동으로 뒤에 따라 붙어서

31,51,28,9,1,10으로 배열이 만들어지고 종료되는건가요?

이 것을 정확하게 모르니

두번째 merge함수인 merge(arr,0,1,2)도 어떻게 수행해야할지 모르겠습니다 ㅜㅜ

python java c 정보처리기사

답변 3

주말코딩

지식공유자

안녕하세요, 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 시작만큼 해설해드리기가 어렵습니다.

왼쪽 부분, 오른쪽 부분을 나눠가면서 다시 작성한 것을 이미지로 대댓글 올려주시면

그 상태에서 다시 답변드리도록 하겠습니다!

주말코딩

지식공유자

안녕하세요, 질문을 지금 확인했습니다. 제가 외부에 있어서 내일까지 코드 한 번 보고 답변 다시 드리겠습니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. yys 125님.

merge 함수의 동작 방식에 대해 궁금해 하시는군요. merge 함수는 합병 정렬(merge sort)의 핵심 부분으로, 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 역할을 합니다.

먼저, 기본적인 merge 함수의 동작 방식을 간단히 설명드리겠습니다. 이후 예제를 통해 자세히 살펴보겠습니다.

기본적인 merge 함수 동작 방식 요약

입력 배열과 인덱스 범위: merge 함수는 배열과 세 개의 인덱스를 받습니다. 예를 들어 merge(arr, left, mid, right)에서 arr은 대상 배열, left와 right는 병합할 부분의 시작과 끝 인덱스, mid는 중간 인덱스입니다.
두 개의 정렬된 부분 배열: 이 인덱스를 기준으로 arr[left..mid]와 arr[mid+1..right] 두 개의 정렬된 부분 배열을 가정합니다.
정렬된 배열로 병합: 두 부분 배열을 하나의 정렬된 배열로 병합합니다.

말씀하신 예제의 문맥에서 다음과 같은 순서로 진행됩니다.

첫 번째 merge 함수: `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 함수: `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을 확인하시면 도움이 될 것 같습니다.

2022 3회: 여러 학생들이 코딩 문제에서 result[i]++의 결과값에 대해 이해하는 과정을 설명합니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변