TIL
2021 05 27 (목) 본문
20210527(목)
1. 학습 날짜 : 20210527(목)
2. 학습 시간 : 14:00 ~ 17:00, 17:30 ~ 21:30
3. 학습 주제 : push_swap 알고리즘 생각해내기, 명령어 집합 구현
4. 동료 학습 방법 :
5. 학습 목표 :
- Push_swap 명령어 집합 구현
- Push_swap pop() 오류 수정.
- 잘하면 연결리스트 전체 구조를 되돌아봐야 할 수 도 있을 것 같다.
- mental - 코드를 갈아 엎는게 왜 힘들까.
- 잘하면 연결리스트 전체 구조를 되돌아봐야 할 수 도 있을 것 같다.
- Push_swap 명령어 집합 구현
- sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrrRReverse 계열 : head에 있는 것을 top으로 옮긴다.
- Reverse 계열 : top에 있는 것을 head로 옮긴다
- quicksort 사용해서 배열을 만들어서 인자들을 정렬한다. - 5시까지 완성
- stderror에
Error\n를 출력해야한다. !!!!!!
6. 학습 내용 :
./push_swap 1 2 3 4 5 6 7 8 9 10
initialized
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1 200
popped
popped data : 200
10 9 8 7 6 5 4 3 2 1 200
# push(200) 후 pop(200)을 했는데 200이 계속 남이있는 상황.1차 예상 :
*data = l_list->tail->data;
aux_node = l_list->tail;
l_list->tail->prev->next = l_list->head;
l_list->head->prev = l_list->tail->prev;
l_list->tail = aux_node->prev; //여기에서 문제가 생긴 것으로 추정.
//왜..?
//
free(aux_node);2차 예상 :
int linked_list_push(t_ll **ab_arr, int num_stack, int data)
{
t_node *new_node;
t_ll *l_list;
l_list = ab_arr[num_stack];
new_node = (t_node *)malloc(sizeof(t_node));
if (!new_node)
return (ft_print_error());
//malloc 에러 시 t_ll, 안의 모든 노드들 삭제하고 프로그램 종료.
new_node->data = data;
if (l_list->size == 0)
{
l_list->head = new_node;
l_list->tail = new_node;
}
else
{
l_list->tail->next = new_node;
l_list->head->prev = new_node;
l_list->tail = new_node; //
}
new_node->next = l_list->head;
new_node->prev = l_list->tail;
l_list->size++;
return (1);
}Push 하는 부분에서 문제가 생긴 것이 확실해보인다.
정확히는 push()의 else부에서 문제가 생겼다.
else
{
l_list->tail->next = new_node;
l_list->head->prev = new_node;
l_list->tail = new_node; // 이 부분에서 바꾸어준 tail을
}
new_node->prev = l_list->tail; //변경된 tail을 다시 바꾸어서 사용하려고 했기 때문에 new_node->prev = new_node를 가리키고 있었다.해당 문제를 고치니 해결되었다.
Push_swap 명령어 집합 구현
sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr
swap 실험 성공
swap_ab(ab_array, STACK_A);
traverse_list(ab_array, STACK_A);
traverse_list(ab_array, STACK_B);
swap_ab(ab_array, STACK_A);
traverse_list(ab_array, STACK_A);
traverse_list(ab_array, STACK_B);/push_swap 1 2
initialized
1 2
empty stack
2 1
empty stack
./push_swap 1 2 3 4 5 6 7
initialized
7 6 5 4 3 1 2
empty stack
7 6 5 4 3 2 1
empty stackpush 실험
push_ab(ab_array, STACK_B);
push_ab(ab_array, STACK_B);
push_ab(ab_array, STACK_B);
push_ab(ab_array, STACK_B);
push_ab(ab_array, STACK_B);
push_ab(ab_array, STACK_B);
push_ab(ab_array, STACK_B);
traverse_list(ab_array, STACK_A);
traverse_list(ab_array, STACK_B);./push_swap 1 2 3 4 5 6 7
initialized
7 6 5 4 3 2 1
empty stack
7 6 5 4 3 2
1
7 6 5 4 3
1 2
7 6 5 4
1 2 3
7 6 5
1 2 3 4
7 6
1 2 3 4 5
7
1 2 3 4 5 6
empty stack
1 2 3 4 5 6 7*rev, rev 실험 : *
./push_swap 1 2 3 4 5 6 7
initialized
7 6 5 4 3 2 1
empty stack
1 7 6 5 4 3 2
empty stack
2 1 7 6 5 4 3
empty stack
3 2 1 7 6 5 4
empty stackrrev도 동일
명령어 집합 구현 성공
인자로 들어온 숫자들을 숫자 배열에 넣은 뒤 오름차 순으로 정렬하기
- 정수 배열을 위한 포인터를 main에 선언,
- argument들을 받아 배열에 저장한다.
- 동적할당.
- 배열에 저장할 때, STACK_A를 traversing하면서 배열에 저장해야됨.
- 배열을 "오름차순으로 정렬한다." Using quicksort. - 5시까지
- 집에 가면 QuickSort, MergeSort 다시 짜보고, 설명 할 수 있을 때 까지 설명해보기..
- TEST : 인자가 한개, 두개, 세개, 10개일 때 정렬이 제대로 되는가?
중간 평가
📦push_swap
┣ 📂includes
┃ ┣ 📜linked_list.h
┃ ┗ 📜push_swap.h
┣ 📂libft
┣ 📂srcs
┃ ┣ 📜arg_input.c
┃ ┣ 📜custom.c
┃ ┣ 📜inst.c
┃ ┣ 📜inst_2.c #명령어 집합 위한 inst, inst_2 추가.
┃ ┣ 📜linked_list.c #linked_list 의 push 수정.
┃ ┣ 📜main.c
┃ ┣ 📜utils.c #init_arg_arr, quicksort구현
┣ 📜.gitignore
┣ 📜Makefile
┣ 📜README.md
┗ 📜push_swap타 카뎃의 push_swap 정리 글 보기
의문점 :
⁉️ 이렇게 해야 [3]을 정렬한 다음에 바로 [2]를 정렬할 수 있습니다.
..?정렬하는 순서가 중요한 이유...?
⁉️ 세 그룹은 3등분되어 크기가 비슷할 것이므로 rrr을 반복한 후에 ra 또는 rb를 한 번 더 호출해서 되감기를 끝마칩니다.
💡3등분되어 크기가 비슷하므로, rrr를 실행한 뒤, ra 또는 rb가 필요한 스택에 있어서, ra 와 rb를 몇번 더 호출한다.
⁉️ 두 함수 조합하기 ?
원소를 덜어내다 ?
⁉️ 스택 B를 정렬하는 과정에서 [2]가 올라가버리고 나면 [3]은 정렬을 할 수가 없습니다.
약간 하노이의 탑 방식으로 전개하신듯 하다.
로직도 그렇고, 하노이의 탑 방식을 따른 듯 한데..
def A_to_B(r)
if r < 3
적절히 정렬
return //r이 3보다 작을 때는, 명령어 수를 줄이기 위해서..
스택A 원소 중에서 "적절한" 피봇을 2개 선택한다
for r개의 원소에 대해서
if (스택A의 top) >= 피봇[큰것] //큰 것은 stack의 head 부로 넘긴다.
ra명령으로 뒤로 넘긴다
ra호출횟수++
else //작은 것들은 stack B로 옮기는데, 작은 피벗을 기준으로, 작은 피벗보다 큰 것은 head로, 작은 피벗보다 작은 것은 tail에 둔다.
pb명령으로 b로 보낸다
pb호출횟수++
if (스택B의 top) >= 피봇 [작은것]
rb명령으로 뒤로 넘긴다
rb호출횟수++
for ra호출횟수, rb호출횟수
rrr호출 #[3]과 [2]를 스택 앞으로 가져온다
A_to_B(ra호출 횟수) #[3] // A의 3등분한 것 중 큰 chunk - [3] 에 대해서 재귀적으로 정렬해 진행한다.
B_to_A(rb호출 횟수) #[2] // B의 3등분한 것 중 작은 Chunk들에 대해서,재귀적으로 정렬하는데,
B_to_A(pb호출 횟수 - rb 호출 횟수) #[1] // 이 때, [2]를 정렬한 뒤에 [1]을 정렬한다.
//재귀적으로, 순서대로 정렬한다.
출처 : https://www.notion.so/push_swap-c15e6222def B_to_A(r)
if r < 3
적절히 정렬/pa로 보내기
return
스택B 원소 중에서 "적절한" 피봇을 2개 선택한다
for r개의 원소에 대해서
if (스택B의 top) < 피봇[작은것]
rb명령으로 뒤로 넘긴다
rb호출횟수++
else
pa명령으로 a로 보낸다
pa호출횟수++
if (스택B의 top) >= 피봇 [큰것]
ra명령으로 뒤로 넘긴다
ra호출횟수++
A_to_B(pa호출횟수 - ra호출횟수) #[3] //
for ra호출횟수, rb호출횟수
rrr호출 #[1]과 [2]를 스택 앞으로 가져온다
A_to_B(rb호출횟수) #[2]
B_to_A(ra호출횟수) #[1]
QuickSort 와 유사하게 진행되며, 하노이의 탑과 같은, 식으로 진행된다.
""분할 정복" 에서 A_to_B와 B_to_A의 흐름이 조금 다른데, 흐름이 다른 이유는 다음과 같다.
A에는 큰 수를, B에는 작은 수를 두기로 정하며,
따라서, A에는 큰 수를 오름차순으로,
B에는 작은 수를 내림차순으로 둔다. (Stack B에서, )
최종 목표는 top에서부터 오름차순으로 정렬하는게 목표이기 때문에, 그렇게 한다.
B에는 top을 기준으로, 내림차순으로(큰 숫자부터 밑으로 작은숫자까지) 정렬되어있어야한다.
오늘 이해한 바는 여기까지..
Push_swap 최종 정리 필요
학습에 도움된 사이트 :
| 주제 | 페이지 |
|---|---|
| Cadet's notion | https://www.notion.so/push_swap-c15e62229b954 보안 이유로 사이트 url을 잘라둠. |
오늘 발견한 문제와 해결방안:
- push_swap 알고리즘의 이해가 필요하다. 지금 한 30%정도 이해한듯하다.
- 설명할 수 있을 떄 까지 관련 알고리즘을 공부,
- quicksort도 다시 한 번 정의를 알아야하며, 코딩도 다시 해봐야함.
7. 학습 총평 :
- 알고리즘부 제외한 구현부분을 구현하는데 이틀 소요. (Testing까지)
- 알고리즘 공부와 그것의 구현부는 오늘로부터 3일정도 소요기간을 잡아야 할 것 같다.
8. 다음 학습 계획 :
- https://www.notion.so/push_swap-c15e62229b9 을 참고하여 공부한 뒤,
- quicksort도 다시 한번 공부한 뒤,
- 혼잣말이나, 같은 카뎃에게 설명한다.
- 알고리즘의 구현, 디버깅
'2021 > 일일 기록' 카테고리의 다른 글
| 2021 05 31(월) (0) | 2021.06.01 |
|---|---|
| 2021 05 28 (금) (0) | 2021.05.31 |
| 2021 05 27 (수) (0) | 2021.05.26 |
| 2021 05 24(월) (0) | 2021.05.24 |
| 2021-04-05 (월) : 데이터 분석 (0) | 2021.04.06 |
Comments