2021 05 28 (금)

20210528(금)

1. 학습 날짜 : 20210528(금)

2. 학습 시간 : 13:30 ~

3. 학습 주제 : push_swap 알고리즘의 이해

4. 동료 학습 방법 : cadet 한명

5. 학습 목표 : push_swap 알고리즘, quicksort의 이해

• https://www.notion.so/push_swap-c15e62229b9 을 참고하여 공부한 뒤,
• quicksort도 다시 한번 공부한 뒤,
• 혼잣말이나, 같은 카뎃에게 설명한다.
• 알고리즘의 구현, 디버깅

6. 학습 내용 :

QuickSort 다시 보기 :

int        partition(int *arr, int left, int right)
{
    int i, j, piv;
    int    aux;

    piv = arr[left];
    i = left;                    // i = left + 1 로 설정해놓을 경우, 원소가 두 개 일 때는 원소들을 바꾸지 못한다. (partition이 작동하지 않는다.)
    j = right;

    while (i < j)
    {
        while (arr[j] > piv)
            j--;
        while (i < j && arr[i] <= piv)
            i++;
        aux = arr[i];
        arr[i] = arr[j];
        arr[j] = aux;
    };
    arr[left] = arr[i];
    arr[i] = piv;
    return (i);
}

// i = left 이고, i = left + 1 이면 안되고, i + 1 이어야 하는 이유

i = left + 1 일 경우, subarray = [5 , 6, 7]을 정렬하고자 할 때, [6, 5, 7]과 같이 정렬된다.

pivot의 위치 + 1에서 i의 index를 시작해야할 줄 알았지만,

i = left 에서 시작해도 이미 pivot의 값을 변수로 저장하고 있었기 때문에 문제가 되지 않는다.

push_swap 튜토리얼 정리

• Quick Sort의 개념을 이용해서, 피벗을 기준으로, 한 쪽에는 피벗보다 작은 원소를, 다른 한쪽에는 피벗보다 큰 원소를 두어 피벗을 기준으로 나눈다.
• 이 튜토리얼에서는 피벗을 두개 사용한다.
  피벗을 두 개 사용하게 되면, 명령어는 비슷할 것 같지만, reverse 연산에 대해, 겹치는 연산을 rr이나 rrr로 한번에 reverse 시켜줄 수 있기 떄문에, 피벗을 두개로 둔다.
• 기본적으로, 분할정복 방식을 사용한다.
  • == 재귀.
  • 따라서, 점화관계나, 시스템을 일반화했을 떄, 또는 시스템화해서 경우를 생각해보면, 생각이 좀 편해진다.

피벗 2개 중 큰 피벗을 피벗 A, 작은 피벗을 피벗 B라고 명명한다.

• A스택에는 피벗A보다 큰 원소들을 Top을 기준으로 오름차순으로 정렬한다.
• B스택에는 피벗A보다 작은 원소들을 두되, Top을 기준으로 큰 원소들을 위에, 작은 원소들을 Bottom에 둔다.
  • 이는, 스택의 특성상, top B에서 top A로 원소들을 옮길 때, 역순으로 옮겨지기 때문에, 기존에 B에 내림차순으로 정렬되어있던 원소들이 A로 옮겨질 때 오름차순으로 다시 정렬되기 때문이다.

• A에는, 큰 원소를
• B에는 작은 원소를 남긴다.

• 병합 과정에서, B에서 A로 원소를 옮길 떄, 주의해야한다.

• 위 사진의 정렬됨.... 은 분할정복 과정에 의해서 상위 과정에서 [3]이 정렬되었기에 정렬된 상태에 존재한다.A_to_B 를 실행하게 되면, [3]에 대해서는 모두 정렬이 완성된 상태로 재귀에서 빼져나온다.------->재귀 / 또는 점화관계
• B_to_A를 실행하면, 정렬이 완성된 상태로 재귀에서 빠져나온다.
• A_to_B(ra호출 횟수) #[3] //이 부분이 끝나고 나와서. B_to_A(rb호출 횟수) #[2] //현재 위 사진의 부분. B_to_A(pb호출 횟수 - rb 호출 횟수) #[1]

재귀는 "귀납적인 사고"로 이해해야한다.

•  

B_to_A의 정복단계는 A_to_B의 정복단계와 다른 점이 존재하는데,

본 정렬과정은 스택의 top을 정렬하는데 사용하기 때문에, [2]를 정렬한 뒤 [3]을 정렬하고자 하면, 정렬과정에서 문제가 생기거나, 또는 명령어의 수가 늘어난다.

이를 방지해주기 위해, rrr 을 해주기 전에, [3]을 먼저 정렬해준 뒤에 A_to_B([3]) rrr명령어를 사용하여 마지막 표와 같이 만들어준 뒤에, [2]에 대해서 정렬해준다 A_to_B([2])

명령 횟수 정리

생각해보니까 전제 자체가 정렬해야 되는 모든 원소를 pivot에 의해 나눌 때, 균등하거나, 거의 균등한 크기로 나누어야 한다.
(n/ 3)

균등한 방법으로 pivot을 나누는 방법

pivot_array를 따로 만드는데, int ***pivot_array 형태.

pivot_array[0][0], pivot_array[0][1] 로, pivotA와 pivotB를 나타내며, row는 pivot을 사용하는순서를 말한다.

6. 학습에 참고한 사이트

학습에 도움된 사이트 :

Push_swap 참고 사이트 (cadet's blog)	https://www.notion.so/push_swap-c15e62229b954 보안상 이유로 링크 뒷부분 삭제함
Quicksort 이해	https://hongku.tistory.com/149

오늘 발견한 문제와 해결방안:

•  

7. 학습 총평 :

•  
•  

8. 다음 학습 계획 :