2021 05 24(월)

20210524(월)

1. 학습 날짜 : 20210524(월)

2. 학습 시간 : 13:10 ~ 14 :45, 15:15 ~ 16:45, 17:00 ~ 18:30

3. 학습 주제 : Push_swap 과제 해석, 요구사항 분석

4. 동료 학습 방법 : 개인

5. 학습 목표 : push_swap 과제 분석, 요구사항 분석

오늘 목표

---

• 1순위 : Push_swap "mandatory", "Bonus" 요구사항 분석
  • 단, Bonus는 mandatory를 확실하게 끝낸 후에 평가받는다.
• Push_Swap에서 에러처리해주어야 하는 부분에 대해서 생각해보고, 기록하기
• 프로그램 요구사항 설명 가능
• Push_swap 과 관련한 정보 찾아보기
• Push_swap 대략적으로 설계해보기
  • 설계했을 떄, 시간복잡도와 공간복잡도에 대해서..?

• 2순위 : Push_swap 과 관련한 알고리즘 : merge, quick, bubble, 등 정리해보기
  • 기본 정렬 알고리즘 5개 :
    • 삽입정렬 알고리즘 과정 설명할 수 있도록 연습하기
    • 버블정렬, 선택정렬 알고리즘 짜보기.
    • 퀵정렬 알고리즘에 대해 조사하기,
      • 과정 설명하기
    • mergesort 알고리즘에 대해 조사하기,
      • 과정 설명하기
  • 선형 자료구조에 대해서 조사하기.

 

 

백준

• 백준 알고리즘 문제 풀기

exam_02

• Exam_02 준비하기 : printf, gnl 중 택 1
• leaks 사용법 숙지

6. 학습 내용 :

Push_Swap 요구사항 분석

general instructions

• ./push_swap
• Makefile이 있어야한다.
• Libft.
• Norm
• ? : norm은 V2 / V3 ?

mandatory

• A, B 스택.
  • A = { random numbers... }, 안에 있는 숫자들은 중복되면 안된다.
    • 스택 a에 숫자들을 오름차순으로 정렬하는게 목표.
    • 오름차순 : top에서부터 차례로 스택의 끝까지 값이 증가해야 한다.
  • ⁉️ n(A) = 0 이 가능한가?
• instruction 종류 : n(inst) = k...

push_swap.pdf 해석

• 주어지는 것 :
  • 스택 2개
  • inustruction 집합.
  • sort 할 int set.
    • ? : input 이 int가 아니면?
      ? : input 이 없다면?
• 만들어야 할 프로그램 :
  • ./push_swap
  • 명령어를 가장 적게 사용하도록 계산하고, stdout에 출력되도록 한다.
  • ra, rb, rr / rra, rrb, rrr의 차이 :
    • 일반 rotate는 ->
      The first element becomes the last one. : 첫번째 자리에 마지막 원소가 온다.
    • Reverse rotate 는 <-
      The last element becomes the first one. : 마지막 자리에 첫번째 원소가 온다.
    • ⁉️ : 각각의 instruction들을 사용하는 상황이 정해져 있는가?

• ./push_swap 프로그램에 대한 요구사항 :
  • 가변인자를 받을 수 있어야한다.
  • 첫번째 인자가 top에 있어야함. ./push_swap 1 9 8 7 6 5 4 3 : 3 4 5 6 7 8 9 1(top)
  • 명령들을 최소한으로 사용하게 한다.
  • 명령들은 '\n'으로 구분되게 해야한다.

통과 기준

• operation 기준보다 많은 instruction의 사용
• sorting이 제대로 되지 않을 경우
  • sorting이 제대로 되었는지도 보여야하나..?
• integer가 아닌 인자, integer 범위를 넘어가는 인자, 중복 인자 : 에러 처리.
  • 또, 에러처리를 해줄만한 부분이 어떤 부분이 있는지에 대해서 생각해보자.

 

Push Swap 요구사항 정리 / 해석

• 스택 2개와 주어진 instruction들을 사용해서 스택 a에 ./push_swap의 가변인자로 전달된 integer들을 top을 기준으로 오름차순으로 정렬하는 것.

• 에러처리 요구사항 :
  1. push_swap에 정수가 아닌 인자.
  2. malloc시 인자..?
  3. integer가 들어오지 않았을 경우
  4. 가변인자로 들어온 숫자들의 중복이 일어났을 경우
  5. sorting이 제대로 되지 않았을 경우
• 애매한 상황 :
  1. Push_swap에 인자가 하나만 들어왔을 경우

 

 

 

 

Sorting 알고리즘 정리

Bubble Sort

정의 : 인접한 두 항목의 값 비교해서 일정한 기준을 만족하면 서로의 값을 교환하여 정렬.
일정한 기준 : (수에 대한 오름차순, 내림차순)

#include <stdio.h>

void    bubble_sort(int *arr, int arr_size)
{
    int        i, j, k;

    for (i = 1; i < arr_size; i++)
        for (j = i + 1; j < arr_size; j++)
        {
            if (arr[i - 1] > arr[i])
            {
                //swap
                k = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = k;
            }
        }
    return ;
}

 

 

 

Insertion Sort

정의 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

void    insert(int *arr, int size)
{
    int        i, j, k;

    for (i = 1; i < size; i ++)
    {
        for (j = 0; j < i; j++)
        {
            if (arr[j] > arr[i])
            {
                for (k = i - 1; k >= j; k--)
                    arr[k + 1] = arr[k];
                arr[j] = arr[i];
            }
        }
    }
}

알고리즘 과정 설명 :

1. outer iteration : n - 1 번 반복 필요.
2. inner iteration :
   0 ~ 0, 0 ~ 1, 0 ~ 2, 0 ~ 3, 0 ~ 4, ... 0 ~ n-2 (인덱스) 번 반복 필요.
3. 0 0 0 0 F 0 A Z X V E 0 B 미정렬...
   처럼 B 이전까지 미정렬상태이고, B를 정렬하려고 하고 있으며, 오름차순 정렬 기준으로 F > B 라면,
   F를 원래 B 위치까지 오른쪽으로 한칸 씩 밀어주어야 한다. >>
4. 0 0 0 0 _ F 0 A Z X V E 0 B 미정렬...
5. B를 F 이전 위치까지 옮겨준다.

-> 사진 첨부 : 카카오톡.

 

 

Selection Sort

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

void    selection(int *arr, int size)
{
    int        i, j, min, k, min_index;

    for (i = 0; i < size - 1; i++)
    {
        min = arr[i];
        for (j = i + 1; j < size; j++)
        {
            if (min > arr[j])
            {
                min = arr[j];
                min_index = j;
            }
        }
        arr[min_index] = arr[i];
        arr[i] = min;
        min_index = -1;
    }
    return ;
}

 

 

merge sort

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

• 안정 정렬이란?
  • 정렬 시 동일한 값에 대해서 순서가 바뀌지 않는 알고리즘
• 불안정 정렬이란?
  • 정렬 시 동일한 값에 대해서 순서가 바뀌는 알고리즘

병합정렬 코드 분석 :

# include <stdio.h>
# define MAX_SIZE 8

int sorted[MAX_SIZE] // 추가적인 공간이 필요

// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  /* 분할 정렬된 list의 합병 */
  while(i<=mid && j<=right){
    if(list[i]<=list[j])
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  // 남아 있는 값들을 일괄 복사
  if(i>mid){
    for(l=j; l<=right; l++)
      sorted[k++] = list[l];
  }
  // 남아 있는 값들을 일괄 복사
  else{
    for(l=i; l<=mid; l++)
      sorted[k++] = list[l];
  }

  // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(int list[], int left, int right){
  int mid;

  if(left<right){
    mid = (left+right)/2 // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {21, 10, 12, 20, 25, 13, 15, 22};

  // 합병 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 7)
  merge_sort(list, 0, n-1);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

void merge_sort(int list[], int left, int right){
  int mid;

  if(left<right){
    mid = (left+right)/2 // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
    merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
    merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
    merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
  }
}

• (left >= right) 에 관해. : 언젠가는 left 가 right 보다 커지거나 같아지는가 ?
  • 네.
• 그럼 어떤 경우에 left 가 right 보다 커지거나 같아지는가?
  • subArray의 size가 1,
    또는 2일 때.
  • size가 2일 때는 (left >= right) 조건을 만족시키지 않는다.
  • subArray 의 size가 2인 경우를 예로 들어보자.
    1. index 0, 1 :
    2. if (0 < 1) { mid = 0 merge_sort(0,0) merge_sort(1,1) }
    3. Index 1, 2 역시 마찬가지다.

• subArray의 size가 1인 경우를 예로 들어보자.
  1. index 3 :
  2. if (3 < 3) { mid = ... ... // 이 조건문 안으로 실행되지 않는다. }

• 결론 : subArray의 size가 1, 2가 되는 경우에 left >= right를 만족시킨다.
• 결론 : subArray의 size가 1이 되는 경우에 left >= right를 만족시킨다.
• subArray의 size가 2가 되는 순간, merge를 하도록 되어있다.

🎑: Kakao Pic.

merge_sort 코드 풀이 과정 :

1. Merge_sort는 분할, 정복 과정을 거친다.
2. merge_sort, merge
3. subArray가 2가 될 때까지만 함수를 진행한다.
   == subArray가 1이 되기 전까지만 함수를 진행한다.
   == left >= right 가 되는 순간, subArray의 size가 1이 된다.
4. 0 0 0 0 0 0 | 0 0 0 0 0 0 0
5. 정렬된 오른쪽과 왼쪽 배열을 합치는 과정을 밟는다.

---

---

 

 

학습에 도움된 사이트 :

주제	사이트
정렬 알고리즘	https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
알고리즘 정의 정리	https://quizlet.com/kr/597284527/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-flash-cards/
병합정렬 알고리즘	https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

미완 목표 :

• Push_Swap에서 에러처리해주어야 하는 부분에 대해서 생각해보고, 기록하기
• Push_swap 대략적으로 설계해보기
  • 설계했을 떄, 시간복잡도와 공간복잡도에 대해서..?

• 2순위 : Push_swap 과 관련한 알고리즘 : merge, quick, bubble, 등 정리해보기
  • 기본 정렬 알고리즘 5개 :
    • 삽입정렬 알고리즘 과정 설명할 수 있도록 연습하기
    • 버블정렬, 선택정렬 알고리즘 짜보기.
    • 퀵정렬 알고리즘에 대해 조사하기,
      • 과정 설명하기
    • mergesort 알고리즘에 대해 조사하기,
      • 과정 설명하기

백준

• 백준 알고리즘 문제 풀기

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

• 백준 한 문제를 풀지 못했다.

7. 학습 총평 :

• 각각의 sort들은 본 지 오래 되어서 잘 기억나지 않아, 다시금 공부해야 했다.
• 단기 기억력의 문제가 아니고, 단기기억이 장기기억에 올라가지 않아 생긴 문제로,이 문제를 해결하기 위해,
• 정렬 알고리즘의 정의부터 외우도록 했으며, 정렬 알고리즘의 구상 순서까지 텀을 둔 복습을 염두에 두었다.
• 이전에 정렬 알고리즘을 보았을 때, 충분한 복습이 이루어지지 않아 장기기억에 저장이 되지 않았다.

• 아직 집에 가기전에 끝내지 못한 목표들이 존재한다.오늘 아침에 일이 많았기 때문에, 시간만 3시간정도 더 주어진다면, 끝낼 수 있을거라 생각한다.
• 집에 가서 최대한 마무리 지어보도록 하곘다.
• 목표를 너무 많이 잡았기 때문이기도 하며, 20시 이후로 집에 갈 계획을 짜서 그렇다.

• c++을 공부하기로 마음먹었다.

8. 다음 학습 계획 :

• https://quizlet.com/latest 에서, 알고리즘의 정의와 알고리즘의 특징, 순서를 기억하도록 한다.
• dfs와 bfs에 대한 간단한 복습과 문제 몇문제를 풀어본다.
• 다음주에 볼 exam_02 준비를 한다.
• 정렬 알고리즘과 관련한 서적을 본다.
• c++ 연습을 하면서 포트폴리오를 준비한다.