TIL
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 알고리즘에 대해 조사하기,
- 과정 설명하기
- 선형 자료구조에 대해서 조사하기.
- 기본 정렬 알고리즘 5개 :
백준
- 백준 알고리즘 문제 풀기
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 이 가능한가?
- A = { random numbers... }, 안에 있는 숫자들은 중복되면 안된다.
- 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들을 사용하는 상황이 정해져 있는가?
- 일반 rotate는 ->
- ./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을 기준으로 오름차순으로 정렬하는 것.
- 에러처리 요구사항 :
- push_swap에 정수가 아닌 인자.
- malloc시 인자..?
- integer가 들어오지 않았을 경우
- 가변인자로 들어온 숫자들의 중복이 일어났을 경우
- sorting이 제대로 되지 않았을 경우
- 애매한 상황 :
- 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];
}
}
}
}
알고리즘 과정 설명 :
- outer iteration : n - 1 번 반복 필요.
- inner iteration :
0 ~ 0, 0 ~ 1, 0 ~ 2, 0 ~ 3, 0 ~ 4, ... 0 ~ n-2 (인덱스) 번 반복 필요. 0 0 0 0 F 0 A Z X V E 0 B 미정렬...
처럼 B 이전까지 미정렬상태이고, B를 정렬하려고 하고 있으며, 오름차순 정렬 기준으로 F > B 라면,
F를 원래 B 위치까지 오른쪽으로 한칸 씩 밀어주어야 한다. >>0 0 0 0 _ F 0 A Z X V E 0 B 미정렬...
- 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인 경우를 예로 들어보자.
- index 0, 1 :
if (0 < 1) { mid = 0 merge_sort(0,0) merge_sort(1,1) }
- Index 1, 2 역시 마찬가지다.
- subArray의 size가 1,
- subArray의 size가 1인 경우를 예로 들어보자.
- index 3 :
if (3 < 3) { mid = ... ... // 이 조건문 안으로 실행되지 않는다. }
-
결론 : subArray의 size가 1, 2가 되는 경우에left >= right
를 만족시킨다. - 결론 : subArray의 size가 1이 되는 경우에
left >= right
를 만족시킨다. - subArray의 size가 2가 되는 순간,
merge
를 하도록 되어있다.
🎑: Kakao Pic.
merge_sort 코드 풀이 과정 :
- Merge_sort는 분할, 정복 과정을 거친다.
merge_sort, merge
- subArray가 2가 될 때까지만 함수를 진행한다.
== subArray가 1이 되기 전까지만 함수를 진행한다.
==left >= right
가 되는 순간, subArray의 size가 1이 된다. 0 0 0 0 0 0 | 0 0 0 0 0 0 0
- 정렬된 오른쪽과 왼쪽 배열을 합치는 과정을 밟는다.
학습에 도움된 사이트 :
미완 목표 :
- Push_Swap에서 에러처리해주어야 하는 부분에 대해서 생각해보고, 기록하기
- Push_swap 대략적으로 설계해보기
- 설계했을 떄, 시간복잡도와 공간복잡도에 대해서..?
- 2순위 : Push_swap 과 관련한 알고리즘 : merge, quick, bubble, 등 정리해보기
- 기본 정렬 알고리즘 5개 :
- 삽입정렬 알고리즘 과정 설명할 수 있도록 연습하기
- 버블정렬, 선택정렬 알고리즘 짜보기.
- 퀵정렬 알고리즘에 대해 조사하기,
- 과정 설명하기
- mergesort 알고리즘에 대해 조사하기,
- 과정 설명하기
- 기본 정렬 알고리즘 5개 :
백준
- 백준 알고리즘 문제 풀기
오늘 발견한 문제와 해결방안:
- 백준 한 문제를 풀지 못했다.
7. 학습 총평 :
- 각각의 sort들은 본 지 오래 되어서 잘 기억나지 않아, 다시금 공부해야 했다.
- 단기 기억력의 문제가 아니고, 단기기억이 장기기억에 올라가지 않아 생긴 문제로,이 문제를 해결하기 위해,
- 정렬 알고리즘의 정의부터 외우도록 했으며, 정렬 알고리즘의 구상 순서까지 텀을 둔 복습을 염두에 두었다.
- 이전에 정렬 알고리즘을 보았을 때, 충분한 복습이 이루어지지 않아 장기기억에 저장이 되지 않았다.
- 아직 집에 가기전에 끝내지 못한 목표들이 존재한다.오늘 아침에 일이 많았기 때문에, 시간만 3시간정도 더 주어진다면, 끝낼 수 있을거라 생각한다.
- 집에 가서 최대한 마무리 지어보도록 하곘다.
- 목표를 너무 많이 잡았기 때문이기도 하며, 20시 이후로 집에 갈 계획을 짜서 그렇다.
- c++을 공부하기로 마음먹었다.
8. 다음 학습 계획 :
- https://quizlet.com/latest 에서, 알고리즘의 정의와 알고리즘의 특징, 순서를 기억하도록 한다.
- dfs와 bfs에 대한 간단한 복습과 문제 몇문제를 풀어본다.
- 다음주에 볼 exam_02 준비를 한다.
- 정렬 알고리즘과 관련한 서적을 본다.
- c++ 연습을 하면서 포트폴리오를 준비한다.
'2021 > 일일 기록' 카테고리의 다른 글
2021 05 27 (목) (0) | 2021.05.28 |
---|---|
2021 05 27 (수) (0) | 2021.05.26 |
2021-04-05 (월) : 데이터 분석 (0) | 2021.04.06 |
2021-04-02(금) : 데이터 분석 (0) | 2021.04.02 |
2021-03-31(수) : 데이터분석, cub 진행 상황 (0) | 2021.04.01 |
Comments