-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
정렬 - 병합정렬 성능을 n*log n 으로 나타낼 수 있는 이유
22.10.09 11:33 작성 조회수 235
2
선생님 :)
고등학교 때 배웠던 수학이 이용되는 게 신기하네요!
알고리즘 재밌게 공부하고 있습니다 ㅎㅎ
Q1) 다름이 아니라, 병합 정렬의 성능 계산 방법이 궁금해서 질문 드립니다.
Merge() 함수 내 흩어진 배열을 합치는 부분으로 성능을평가한다.
분할된 배열을 병합할 때에는 n개의 데이터를 n번 비교한다
: 이 부분은 이해했습니다.
왼/오른쪽 데이터를 합칠 때 비교 연산이 이뤄지는데,
1개+1개 합칠 때 => 비교 연산 2번
2개+2개 합칠 때 => 비교 연산 4번
(1개+1개 합치고 => 2개 + 2개 합쳐서)
3개+3개 합칠 때 => 비교 연산 8번 맞을까요?
각 단계를 거칠 때마다 영역의 수가 반으로 줄어든다
: 가장 작은 단위까지 쪼개서, 차근차근 합하므로
8번 => 4번 => 2번
log₂n 으로 표현할 수 있는 부분을 간략히 log n으로 표현한다고 이해하면 될까요?
Q2) 추가로, 배열의 개수가 홀수 개인 경우도 적용이 될 것 같으면서도 애매한 부분이 있을 것 같아 질문드립니다.
(대입해보면 정렬은 되는 것을 확인했습니다)
양쪽을 비교하고 더 이상 비교 대상이 없을 땐 이후 값을 그대로 옮겨온다
라는 점을 생각했을 땐 홀수 개도 무리 없이 비교가 가능하다고 생각하는데,
막상 손으로 구현해보려니 이해가 안 가는 부분이 있습니다.
[1,3,2]를 정렬할 경우 [1]과 [3,2]로 나뉘게 되는데
[1]이 정렬이 완료가 되었다고 해서 [3,2]가 정렬이 완료되지 않은 채로 옮겨지게 될 것 같습니다.
답변을 작성해보세요.
0
감자
지식공유자2022.10.09
안녕하세요 alwayz0121님! ㅎㅎ
병합정렬을 재밌게 공부하시다가 궁금증이 생기셨군요?
바로 답변드리겠습니다.
Q1)
Q1에서 1, 2번은 똑같은 내용입니다.
2번에서 3개+3개를 합칠 때 6번(데이터 개수만큼= 3개+3개) 비교합니다.
만약 [1, 3, 2], [6, 4, 5] 라는 배열이 있다면 tempArr는 크기 6의 배열이 되고 tempArr의 크기(6)만큼 두 배열을 비교하며 정렬합니다.
이 부분은 병합 정렬의 성능(nlogn)에서 n에 해당하는 부분입니다.
(3번은 병합 정렬의 성능(nlogn)에서 logn에 해당하는 부분입니다.)
Q1의 4번은 이해하고 있으신 게 맞습니다!
log₂n = log n 입니다!
Q2
Q2는 구현상에서 이해가 안 된다는 말씀이신 것 같습니다.
이 부분은 재귀함수를 보면서 생각해야 합니다.
MergeSort() 함수 내 MergeSort() 함수가 두 번 호출되고 Merge() 함수를 호출하면서 병합합니다.
만약 [1], [3, 2]로 나뉘었다면
[1]은 MergeSort() 함수에서 첫 번째 MergeSort()에서 처리하고(처리 결과는 [1])
[3, 2]는 MergeSort() 함수에서 두 번째 MergeSort()에서 처리합니다. (처리 결과는 [2, 3])
그리고 이 두 개의 결과([1], [2, 3])를 가지고 Merge() 함수를 호출해 세 번 비교하면서 정렬이 완료됩니다. (처리 결과는 [1, 2, 3])
병합정렬 과정과 재귀함수의 움직임까지 따라가야 하니 조금 복잡할 수 있지만 제가 설명한 방식으로 큰 동작을 기억하시고 한 번 따라가 보시면 궁금증이 금방 해결될 것 같습니다!
더 궁금하신 점 있으시면 댓글 남겨주세요 ㅎㅎ
alwayz0121
질문자2022.10.09
아하!
Q1의 1,2번이 nlogn
Q1의 3,4번이 nlogn
에 해당하는 부분이라는 점 이해했습니다!
2번 과정이 3번이랑 연결되어 있다고 생각을 했는데
확실하게 이해 했습니다!
Q2 이해 되었습니다!
Merge() 함수만 단편적으로 보고
MergeSort() 함수 내 MergeSort() 함수가 두 번 호출되고 Merge() 함수를 호출하면서 병합합니다.
해주신 부분처럼 재귀 함수 부분을 제외하고 생각한 궁금증이었네요!
수학을 좋아했던 저로서는
컴퓨터가 알아듣게 적용하는 알고리즘 과정이 신기하고 재밌습니다! :)
감사합니다!
저는 현재 프론트엔드 준비하는 비전공자입니다.
이전에 JS를 막 알아가는 단계에서 해당 강의를 처음 들었을 땐 어려워서 중도 포기를 했다가,
우선 기능 구현을 해보자는 마음으로 리액트를 공부하고 현재 다시 수강하니
자료구조와 알고리즘을 제대로 알지 못했을 때 구현한 코드들이 부끄럽습니다 ㅎㅎ
아직 공부 중인 입장이다보니 프로젝트가 움직일 수 있도록
쓰게 되는 코드만 쓰는 것 같은데,
구현하고자 하는 프로젝트에 맞게 알고리즘을 구현하는 시야는 현업에서 일을 하다 보면 늘게 될까요?
감자
지식공유자2022.10.09
자료구조와 알고리즘은 구현도 구현이지만 가장 중요한 건 "개념"입니다.
밸런스 게임을 하자면...
개념을 이해하지 못하고 구현을 따라 하는 것 vs 개념은 정확히 알지만, 구현은 어려워서 포기한 것
중에 선택하자면 후자가 훨씬 더 좋은 선택입니다.
프로젝트마다 난도가 다르겠지만 많은 비즈니스 로직은 "자료구조와 알고리즘" 보다 보편적으로 난도가 낮다고 생각합니다.
따라서 더 어려운 "자료구조와 알고리즘"을 학습하고 비즈니스 로직을 짜는 것은 크게 어렵지 않지만,
더 쉬운 비즈니스 로직을 짜면서 "자료구조와 알고리즘"을 학습하기엔 시간도 오래 걸리고 더 비효율적이라고 생각합니다.
자신의 생각을 코드로 옮길 수 있는 능력은 "자료구조와 알고리즘"을 구현하면서 키울 수 있습니다.
오랜 시간 코딩을 한다면 더 잘하게 되죠.
다른 프로그래밍 언어를 학습하신지는 모르겠지만 만약 JS가 첫 언어라면 구현 자체가 어렵게 느껴지실 수도 있습니다.
저는 학부 시절에 언어 하나가 하나의 학문처럼 느껴졌었습니다.
하지만 시간이 지나면서 언어는 하나의 도구일 뿐이고 "나의 생각"을 언어로 표현하는 건 어려운 기술이 아니라는 것을 알게 됐습니다.
이 능력을 초급 스킬이라고 표현하겠습니다.
초급 스킬과 다르게 고급 스킬이란 문제를 해결하는 방법을 생각할 수 있는 것이라고 생각합니다.
(소설을 쓰더라도 소설의 내용을 생각하는 게 어렵지, 그걸 글로 표현하는 건 어렵지 않은 것이랑 비슷한 맥락입니다.)
자료구조와 알고리즘의 기본기가 탄탄하다면 프로젝트에 맞게 알고리즘을 구현, 즉 응용하는 건 어렵지 않다고 생각합니다.
모방은 창조의 어머니라는 말이 있죠 ㅎㅎ
한 예시로 심화편에서 배우는 "트리" 자료구조도 연결리스트를 응용하면서 구현합니다.
그리고 "트리" 자료를 응용해서 "이진 트리"로, "이진 트리"를 응용해서 "AVL 트리", "Red-Black 트리"라는 자료구조가 또 등장했습니다.
그리고 이 자료구조들을 알고 있는 사람들은 비즈니스 로직을 작성할 때 이러한 자료구조들 한 번 더 응용해서 문제를 해결할 수 있다고 생각합니다.
두서없이 생각나는 대로 적었는데 정리하자면
"자료구조와 알고리즘"를 학습하면 구현하고자 하는 프로젝트에 맞게 알고리즘을 구현하는 시야가 자연스럽게 생깁니다.
다시 도전하는 모습 너무 멋지십니다! 😉
alwayz0121
질문자2022.10.10
정성스러운 답변에 공부 방향을 한 번 더 점검하게 되었습니다!
대학에서 전공 과목으로 왜 자료구조, 알고리즘을 배우는지 알 것 같습니다 ㅎㅎ
조바심을 내기 보다는 꾸준히 학습하며 구현하는 시야를 넓힐 수 있도록 하겠습니다! 감사합니다!
답변 1