인프런 커뮤니티 질문&답변
작성한 질문수
병합정렬 질문 있습니다.
작성
·
84
·
수정됨
1
mergesort 함수만 재귀호출 했다고 말하셨는데 파라미터 인수값으로 들어오는 더미 배열이 minindex 기준으로 미리 정렬이 어떻게 되는걸까요?
제가 아는 바로는 하나의 요소만 남을 때까지 배열을 분리하고 merge를 하면서 정렬이 일어나는걸로 아는데요
mergesort라는 함수 밖에 선언한 게 없는데 인자로 넘어오는 배열값이 어떻게 분열만 하는데 정렬이 되냐는 말입니다.
강의 5-6분사이에 있는 내용입니다.
AI 답변 달지말아주세요. 감자님이 직접 답변 부탁드립니다.
답변 5
0
병합 정렬 코드를 로직에 따라 도식화 해보면 기저 조건까지 내려간 후에 호출된 부분으로 다시 돌아와서 merge()함수를 실행합니다.
이 흐름을 코드만 보고는 쉽게 알기가 어려워서 처음에 완성되어 있다고 가정하고 기저 조건과 재귀 조건을 설정합니다.
너무 어렵다 생각하시면 재귀 부분과 merge() 함수 부분에 breakpoint를 잡아두고 디버깅을 해보기 + 연습지에 로직을 차분히 따라가면서 그림을 통해 이해하시면 될 것 같습니다.
재귀 자체가 "결과적으로 이미 완성은 되어있으니 조건만 잘 셋팅하자."라는 느낌이라 직관적이지 않아 저도 눈에 안 들어오는 문제는 그려가면서 풀게 되더라구요.
어려운 것이 당연합니다. 다시 복습하고 있는 저도 아리쏭합니다......
제가 도식화한 그림인데 좋은 참고가 되었으면 좋겠습니다.
0
안녕하세요 뎡2님!
뎡2님이 질문한 내용을 인프런 질문게시판에서 검색해보았는데요.
27일 전부터 질문을 주셨네요.😥
다만 해당 강의의 질문이 아닌 인프런 게시판의 범용적인 질문게시판으로 주셔서 강의가 지정되지 않아 지식 공유자인 저한테도 따로 알림이 오지 않았던 것 같습니다.
추가로 궁금증이 있으시다면 지금 이 질문처럼 해당 강의에서 질문을 주시면 저에게도 알림이 오기 때문에 답변을 바로 드릴 수 있습니다.😀
아 드디어 답변이 감자선생님께 달렸네요...ㅜㅜ
이미지 첨부한 것과 같이 이미 질문을 네 번 한 게 있는데 AI인턴이 계속 먼저 답변을 달아버려서...알림이 안 간 게 아닐까요...?
음 그럼 감자선생님 미리 되어 있다라고 가정한 건 merge 함수도 만들어져 있고 호출된 상황이라고 생각하고 그렇게 정렬이 되었다 라고 보면 되는거죠?
질문하실 때 강의를 지정하셔서 질문해주시면 AI 답변과 무관하게 저에게 알림이 발송됩니다.
네 merge 함수도 구현되었다고 가정하고 이미 작은 정렬 문제는 해결되었다고 가정하는 것입니다!
0
0
안녕하세요 뎡2님!
AI 답변은 인프런 플랫폼 자체에서 동작하는 있는 봇이므로 지식 공유자가 따로 컨트롤 할 수는 없습니다.
해당 영상에서 설명드린 그림은 재귀를 설명드릴 때 "이미 해결되었다고 가정하고" 코드를 작성한 것을 시각화 한 것입니다.
재귀의 특성상 탑다운 방식의 설명이 이해하기 쉽다고 판단해서 그렇게 설명드렸습니다.
7분 20초 이후부터는 실제로 MergeSort() 함수 내 Merge() 함수의 동작 방식을 설명드리면서 두 개의 정렬된 배열이 어떻게 Merge가 되면서 정렬이 되는지 코드로 자세히 설명드리고 있습니다.
재귀의 특성상 "이미 해결되었다고 가정하고"가 일반적인 사고와 거리가 있어서 어려움이 많은 부분입니다.
궁금증이 해결되셨나요?😊
0
안녕하세요, 인프런 AI 인턴입니다. 뎡2님께서 병합 정렬에 대해 혼란스러워하시고 있는 부분을 조금 더 명확히 이해하실 수 있도록 도와드리겠습니다.
병합 정렬(Merge Sort)은 재귀적인 방법을 통해 배열을 단계적으로 쪼개고 그 결과를 병합하면서 최종적으로 정렬하는 알고리즘입니다. 병합 정렬의 핵심은 크게 두 가지 과정으로 나누어집니다.
분할(Divide): 주어진 배열이 하나의 요소가 남을 때까지 계속해서 반으로 나누어집니다. 이 과정은 재귀적으로 이루어지며, 각 작은 배열은 개별적으로 분열된 상태일 뿐 정렬이 이루어지지 않은 상태입니다.
병합 및 정렬(Merge and Sort): 이렇게 나누어진 작은 배열을 다시 병합하는 단계에서 연속된 원소들이 비교되며 정렬이 이루어집니다.
Merge단계에서 두 개의 정렬된 배열을 하나의 정렬된 배열로 만드는 과정이 있어야 전체 배열이 정렬됩니다.
뎡2님께서 언급하신 “mergesort라는 함수 밖에 선언한 게 없는데 인자로 넘어오는 배열값이 어떻게 분열만 하는데 정렬되는가”에 대한 의문은, 사실 병합 단계에서만 정렬이 일어나기 때문에 충분히 생기실 수 있는 혼돈입니다. 분할 자체는 정렬과 무관하게 단순히 쪼갤 뿐이며, 진정한 정렬은 병합 단계에서 수행됩니다.
기존에 작성된 답변들과 예시들도 참고하시면 도움될 것 같습니다:
병합정렬 성능을 n*log n 으로 나타낼 수 있는 이유 - 이 질문에서는 병합 정렬의 성능과 관련해서 성능 계산 방법을 다루고 있습니다.
병합 정렬 질문 - 병합 과정에서 발생하는 비교 횟수와 빅오 표기에 대한 설명이 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
재귀가 인간이 생각하는 사고 흐름과는 거리가 있어서 모두가 어려워 하는 부분이라 진입장벽이 큰 부분이라고 생각합니다.
그림을 깔끔하게 정리해서 한 눈에 보기 좋네요!
답변 감사합니다. 👏