Search
Duplicate
🔻

Push Swap 병합 정렬로 해결하기

간단소개
퀵소트, 모래시계, 그리디 외에 다른 방법인 병합정렬을 소개합니다
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
42cursus
Algorithm
태그
algorithm
Scrap
8 more properties

Push Swap using Merge Sort

이 글에선 5기 seseo 님이 고안하신 Merge Sort 접근법과, 이를 통해 제 과제에 병합정렬을 적용한 과정을 소개합니다.
100개 정렬
500개 정렬
 같은 성능의 병합정렬이여도, 구현 로직이 다르면 위 영상과 정렬 과정이 달라집니다. “아 삼각형을 계속 합치는 구나~” 정도 감을 잡으시면 좋을 것 같습니다.

 병합 정렬 평균 성능

분할 O(n), 병합 O(nlog3n)분할 \ O(n) ,\ 병합\ O(nlog_3n)
 100개 정렬 : ra rb = rr와 같은 명령어 최적화 후 → 평균 620개
 500개 정렬 : ra rb = rr와 같은 명령어 최적화 후 → 평균 4480개
 1000개 정렬 : ra rb = rr와 같은 명령어 최적화 후 → 평균 9510개
 입력값의 분포에 영향받지 않아 명령어 개수가 일정하게 나오는게 장점입니다.

 접근 아이디어 : 삼각형들이 어떤 모양으로 있어야 병합하기 좋은가?

  분할 : 삼각형 합치기 전 모양을 거꾸로 유추하기 (가정법)

1개의 정렬 집합을 정렬된 3개의 부분집합으로 분할(예측) 할 수 있습니다. 그리고 이렇게 정렬된 부분 집합은 삼각형의 모양입니다.

  스택의 가장자리 원소들만 비교해서 삼각형(크기=3) 만들기

각 Stack의 Top과 Bottom에 있는 원소중 3개를 선택하여 비교합니다.
이를 빈 공간에 정렬하면 가장 적은 명령어 횟수로 빈 공간에 크기3의 삼각형을 만들 수 있습니다.

  삼각형 3개를 병합하기

위 과정을 삼각형을 병합할 때 이용하겠습니다.
이번에는 삼각형 3개가 아래 그림처럼 있다고 볼께요.
스택의 가장자리에 있는 원소들 중에서 최댓값 or 최솟값을 찾아 병합하는 과정을 삼각형이 모두 없어질 때 까지 반복하면 삼각형 1개로 병합할 수 있습니다.

 오름차순 = 삼각형 3개중 최댓값을 찾아 push

 내림차순 = 삼각형 3개중 최솟값을 찾아 push

 삼각형 분할 규칙

1개의 삼각형이 3개의 삼각형으로 분할되는 과정은 아래처럼 정리할 수 있습니다.
이 규칙을 가지고 1개의 삼각형을 3개의 작은 삼각형으로 분할할 수 있습니다. 입력값이 N일때, 분할한 삼각형들을 3개씩 합쳐 크기 N의 삼각형을 만드는 것이 병합정렬의 key 아이디어입니다.
위 분할 규칙이 아래 그림에서 사용됩니다.
여기까지 보셨다면 필요한 병합정렬 아이디어는 끝입니다.
다만 배열이 아닌 스택을 이용해야 하기 때문에, 구현자가 선택한 자료구조(데크, 동적 배열, etc…) 분할&병합 순서에 따라 정렬 과정이 달라질 수 있습니다.
위 아이디어를 활용해서 병합 정렬 과정을 구현하시면 됩니다. 종이에 삼각형들을 그려가면서 구현해보세요.
구현시 고민해볼 거리들
크기 27의 삼각형을 어떻게 분할하고 병합할 것인가?
크기 81의 삼각형을 어떻게 분할하고 병합할 것인가?
크기 100의 삼각형은?
3개의 삼각형로 계속 나눌경우 발생한 나머지는 어떻게 처리할 것인가? (ex. 100 = 33 + 33 + 33 + 1)

 적용 : 병합하기 좋은 모양 만들기

이제 위 아이디어를 바탕으로 제가 적용한 풀이 과정을 설명드리겠습니다.
9개의 삼각형이 어떤 모양으로 있어야, 병합했을 때 원하는 모양의 3개의 삼각형이 될까?
과제를 진행하며 주로 했던 고민은 “1개를 3개로 분할하는건 알겠는데, 3개의 삼각형을 어떤 모양의 9개로 분할하는가?” 였습니다.
다행히도 병합에 최적인 최소 삼각형들의 모양에는 일정한 규칙(패턴) 있습니다. 이 패턴을 이용하면 3개의 삼각형을 9개의 삼각형으로, 다시 27개의 삼각형으로, 다시 81개의 삼각형으로 쉽게 연속 분할할 수 있습니다.

  삼각형 분할 패턴 (거울, Mirroring)

 예제 : 크기 100의 삼각형을 연속해서 분할하기

분할 규칙1과 2를 잘 보시면, 맨 밑 삼각형을 기준으로 위 2개대칭을 이룹니다.
이 규칙을 이용해서 한번 계속 분할해보겠습니다.

 100개의 첫번째 분할

100 = (33 + 34 + 33)
분할
병합하면 원래대로(분할 전 모양) 돌아옴을 확인

 똑같은 규칙으로 2번째 분할하기.

(33 + 34 + 33) = (11+11+11)+(11+12+11)+(11+11+11)
분할
삼각형 3개를 거울 반사(대칭) 규칙을 이용하여 다시 9개의 삼각형들로 재분할합니다.
병합해보면 원래대로(분할 전 모양) 돌아옴을 확인.
분할한 9개의 삼각형을 동일한 로직으로 병합하면 처음 3개 모양으로 합쳐지는 걸 확인할 수 있습니다.

 세번째 분할하기

(11+11+11) = (3+5+3) + (3+5+3) + (3+5+3) (11+12+11) = (3+5+3) + (4+4+4) + (3+5+3)
이제 같은 방법으로 9개를 27개로 재분할해보겠습니다.
이걸 거꾸로 병합하면 원상복구 되겠죠.

 최종 분할 결과

여기서 더 분할할 수 있지만, 저는 명령어 횟수를 맞추기 위해 삼각형의 크기가 6 미만일때까지 분할했습니다.

  병합하기 좋은 모양을 미리 알아낸 뒤 (삼각형 역추적) 그 설계도를 바탕으로 초기 삼각형 패턴을 Stack B에 똑같이 만듭니다. 이후 병합병합병합 을 진행하면 삼각형들이 Merge되면서 정렬됩니다.

1.
[예측] 정렬될 결과를 역으로 분할해서 병합에 용이한 최소 삼각형들의 모양(패턴)을 미리 알아낼 수 있습니다.
2.
[분할] 정렬이 처음에 시작되면, 최초 Stack A에 쌓인 랜덤한 값들을 Top에서부터 3/4/5개씩 Stack B로 쌓아나가면서 미리 계산한 최대 분할 모양으로 만듭니다.
3.
[병합] 이후 모두 병합될 때 까지 동일한 규칙으로 병합을 반복 합니다.

 합친 삼각형의 크기가 100이 될 때까지, 삼각형들을 계속해서 병합하면 된다.

이제 병합된 삼각형이 100개가 되었기 때문에 병합을 멈춥니다. 총 3번의 Merge를 거쳐 Stack A에 100개의 데이터가 정렬되었습니다.
위 100개 원소 병합정렬 과정의 비주얼라이저 버전입니다. 삼각형들이 Stack A와 B를 왔다 갔다 하면서 합쳐지는 것이 보이실겁니다.
100개 정렬
 위 로직은 정답이 아니라 구현 예시 중 한가지입니다.
구현자님께서 사용하신 자료구조와 분할&병합 로직에 따라 정렬 과정이 달라질 수 있습니다.
이 가이드를 바탕으로 더 빠르고, 효율적인 Merge Sort 로직을 구현해보시길 기대합니다.

 개선할 만한 점 (1104 추가 내용)

슬랙으로 많이 질문 주시는 부분, 비효율 적인 부분 정리하였습니다.
구현하실 때 이 부분도 함께 고민해보시면 좋을 것 같아요.
sangmiha 님께서 알려주신 분할 과정 비효율성 문제. (알려주셔서 감사합니다!)
1.
17개의 인자가 주어진 경우. 이를 3으로 나눌 경우 5, 7, 5로 나누어 짐 (가운데 7을 더 쪼갤 수 있는지?) (인자의 개수가 17일 때 뿐만 아니라 16일 때도 비슷한 문제가 발생함)
2.
인자가 18개가 주어질 경우 6, 6, 6으로 나누어 지는데 이걸 2,2,2,2,2,2,2,2,2로 나누어서 사용하면 비효율적이지 않을지?