인프런 커뮤니티 질문&답변
작성한 질문수
정렬 - 병합정렬 성능을 n*log n 으로 나타낼 수 있는 이유
해결된 질문
작성
·
375
3
선생님 :)
고등학교 때 배웠던 수학이 이용되는 게 신기하네요!
알고리즘 재밌게 공부하고 있습니다 ㅎㅎ
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]가 정렬이 완료되지 않은 채로 옮겨지게 될 것 같습니다.
답변 1
0
안녕하세요 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])
병합정렬 과정과 재귀함수의 움직임까지 따라가야 하니 조금 복잡할 수 있지만 제가 설명한 방식으로 큰 동작을 기억하시고 한 번 따라가 보시면 궁금증이 금방 해결될 것 같습니다!
더 궁금하신 점 있으시면 댓글 남겨주세요 ㅎㅎ
자료구조와 알고리즘은 구현도 구현이지만 가장 중요한 건 "개념"입니다.
밸런스 게임을 하자면...
개념을 이해하지 못하고 구현을 따라 하는 것 vs 개념은 정확히 알지만, 구현은 어려워서 포기한 것
중에 선택하자면 후자가 훨씬 더 좋은 선택입니다.
프로젝트마다 난도가 다르겠지만 많은 비즈니스 로직은 "자료구조와 알고리즘" 보다 보편적으로 난도가 낮다고 생각합니다.
따라서 더 어려운 "자료구조와 알고리즘"을 학습하고 비즈니스 로직을 짜는 것은 크게 어렵지 않지만,
더 쉬운 비즈니스 로직을 짜면서 "자료구조와 알고리즘"을 학습하기엔 시간도 오래 걸리고 더 비효율적이라고 생각합니다.
자신의 생각을 코드로 옮길 수 있는 능력은 "자료구조와 알고리즘"을 구현하면서 키울 수 있습니다.
오랜 시간 코딩을 한다면 더 잘하게 되죠.
다른 프로그래밍 언어를 학습하신지는 모르겠지만 만약 JS가 첫 언어라면 구현 자체가 어렵게 느껴지실 수도 있습니다.
저는 학부 시절에 언어 하나가 하나의 학문처럼 느껴졌었습니다.
하지만 시간이 지나면서 언어는 하나의 도구일 뿐이고 "나의 생각"을 언어로 표현하는 건 어려운 기술이 아니라는 것을 알게 됐습니다.
이 능력을 초급 스킬이라고 표현하겠습니다.
초급 스킬과 다르게 고급 스킬이란 문제를 해결하는 방법을 생각할 수 있는 것이라고 생각합니다.
(소설을 쓰더라도 소설의 내용을 생각하는 게 어렵지, 그걸 글로 표현하는 건 어렵지 않은 것이랑 비슷한 맥락입니다.)
자료구조와 알고리즘의 기본기가 탄탄하다면 프로젝트에 맞게 알고리즘을 구현, 즉 응용하는 건 어렵지 않다고 생각합니다.
모방은 창조의 어머니라는 말이 있죠 ㅎㅎ
한 예시로 심화편에서 배우는 "트리" 자료구조도 연결리스트를 응용하면서 구현합니다.
그리고 "트리" 자료를 응용해서 "이진 트리"로, "이진 트리"를 응용해서 "AVL 트리", "Red-Black 트리"라는 자료구조가 또 등장했습니다.
그리고 이 자료구조들을 알고 있는 사람들은 비즈니스 로직을 작성할 때 이러한 자료구조들 한 번 더 응용해서 문제를 해결할 수 있다고 생각합니다.
두서없이 생각나는 대로 적었는데 정리하자면
"자료구조와 알고리즘"를 학습하면 구현하고자 하는 프로젝트에 맞게 알고리즘을 구현하는 시야가 자연스럽게 생깁니다.
다시 도전하는 모습 너무 멋지십니다! 😉
정성스러운 답변에 공부 방향을 한 번 더 점검하게 되었습니다!
대학에서 전공 과목으로 왜 자료구조, 알고리즘을 배우는지 알 것 같습니다 ㅎㅎ
조바심을 내기 보다는 꾸준히 학습하며 구현하는 시야를 넓힐 수 있도록 하겠습니다! 감사합니다!
아하!
Q1의 1,2번이 nlogn
Q1의 3,4번이 nlogn
에 해당하는 부분이라는 점 이해했습니다!
2번 과정이 3번이랑 연결되어 있다고 생각을 했는데
확실하게 이해 했습니다!
Q2 이해 되었습니다!
Merge() 함수만 단편적으로 보고
해주신 부분처럼 재귀 함수 부분을 제외하고 생각한 궁금증이었네요!
수학을 좋아했던 저로서는
컴퓨터가 알아듣게 적용하는 알고리즘 과정이 신기하고 재밌습니다! :)
감사합니다!
저는 현재 프론트엔드 준비하는 비전공자입니다.
이전에 JS를 막 알아가는 단계에서 해당 강의를 처음 들었을 땐 어려워서 중도 포기를 했다가,
우선 기능 구현을 해보자는 마음으로 리액트를 공부하고 현재 다시 수강하니
자료구조와 알고리즘을 제대로 알지 못했을 때 구현한 코드들이 부끄럽습니다 ㅎㅎ
아직 공부 중인 입장이다보니 프로젝트가 움직일 수 있도록
쓰게 되는 코드만 쓰는 것 같은데,
구현하고자 하는 프로젝트에 맞게 알고리즘을 구현하는 시야는 현업에서 일을 하다 보면 늘게 될까요?