push_swap

Bigmountain·2021년 5월 12일
42Seoulpush_swap
0

Solve

  • 시행착오를 겪다가.. 결국 링크에서 해결책을 찾았다..

  • push_swap의 핵심은 stackB에 데이터의 section을 잘 나누어 대충 쌓아 놓는것이다.

  • Stack의 성질에 의해, StackB에는 내림차순으로 데이터를 정렬하면 StackA로 가져올 때, 삽입 위치를 빠르게 찾아갈 수 있다.

  • 따라서, 최초데이터를 잘 나눠서 작은값 부터 -> 큰 값을 모두 B로 저장한다.

    • 데이터를 잘 나누는 방법에 대해 Quick Sort의 개념이 도움된다.
    • 헷갈리기 쉬운것은 Quick Sort의 개념을 응용하는 것이지, Quick Sort알고리즘을 그대로 적용하려고 하면 push_swap의 효율성을 놓치게 된다. (난 그랬음 ㅡ..ㅡ)
    • Quick Sort의 최고 효율을 낼 수 있는 방법?
      • 정확한 pivot선정
    • Quick Sort의 partition을 나누는 과정?
      • push_swap에서는 어떠한 방법으로 partition을 나누었을 때 효율적일 수 있는지

  • push_swap은 최소 명령어 수행이 핵심이다. 따라서 명령어를 최소화 할 수 있는 전략을 고민해야 한다.

시행착오...

  • 두 개의 Stack으로 정렬 ?
  • 임시공간을 사용하는 병합정렬로 할 수 있을 까?
  • 최소단위부터 정렬 -> 병합하니깐 스택으로 가능하지 않을까..........
  • 먼저 가능성을 확인하기..

시도1. 병합정렬로 해보기

먼저 병합정렬 이해하기..

분할은 log2^n번일어남

  • n = 16

    • n = 2^4
    • [16 -> 8 -> 4 -> 2 -> 1]

  • n = 9

    • n = 2^3보다 크니깐 4번
    • [9 -> 5 -> 3 -> 2 -> 1]

  • n = 8

    • n = 2^3
    • [8 -> 4 -> 2 -> 1]

  • n = 12

    • n = 2^3 크니깐 4번
    • [12 -> 6 -> 3 -> 2 -> 1]

  • 병합정렬은 최소한으로 쪼갠 후, 정렬하면서 병합.

    • Level n에서 병합해야할 원소들은 정렬되어 있음.
    • leaf일 때, 좌측원소 = 1개 우측원소 = 1개 (즉 정렬되어있음)
      • 따라서, 대소 비교 후 2개의 정렬 된 원소를 가진 집합으로 병합
    • leaf - 1의 Level일 때
      • 좌측원소 = 2개, 우측원소 = 2개 (아래에서 정렬 된 대상)
      • 정렬된 대상을 비교하며, 4개의 정렬된 집합을 만듦.
    • 반복.

      Point
      n개의 원소를 가진 배열을 정렬하기 위해서 반씩 쪼개서, 합치면서 정렬을 한다.
      가장 작은 단위부터 두 묶음씩 차근차근 정렬하면서 올라오기 때문에..
      합치는 과정에서 비교연산의 횟수를 줄일 수 있다.
      (정렬되었기 때문에 stop point를 찾기가 쉬워짐.)

이 병합 정렬을.. 어떻게 stack에 적용을 할 수 있는가..............

먼저, 러프하게 짜보기..

설계...

1. 스택A에서 -> 스택B로 내림차순으로 보낸다.
2. 스택B -> 스택A로 전부 가져온다.
  • 루트노드, 즉 0~n개의 데이터를 병합할 때만 제외하고는 모두 A->B로 push, 정렬 함.
  • 최소 명령어로 정렬하기 위해서?
    • A의 삽입데이터가 B의 어느 인덱에 존재해야하는지 확인.
      (삽입 데이터보다 작은 값이 처음나오는 위치 바로위에 넣어야 함)
    • B스택의 전체크기를 기준으로, 중간위치를 구함.
    • 중간인덱스 이상이면 ?
      • 작은 값을 rb로 맨위로 올린 다음 pb하고, 올린만큼 다시 rra
      • 5 3 2 0 에서 4 삽입할 때,
      • 3 2 0 5 만들고 삽입하고 4 3 2 0 5에서 다시 최댓값을 원래대로 하기위해서 1내려주기
    • 중간 인덱스 미만이면 ?
      • 작은 값을 rrb로 맨위로 내린다음 pb하고, 내린횟수 + 1만큼 다시 올려주기(하나가 추가된만큼, 원래 위치를 유지)
      • 4 3 2 0에서 1삽입시 내려서 0 4 3 2만들고, 1넣고 1 0 4 3 2에서 다시 최대값을 원위치 시키기위해서 위로 + 1만큼 돌리기

최적화 방법 고민 해보기..

  • 데이터를 b에보내고, a에 남은 데이터가 정렬이 되어있다면 ?
    • ok, b에 있는거 a로 옮기고 끝내자.
    • 안된다.
    • 1 4 2 5 6 7 이렇게 있다면
      • b에 4 1 로 저장 했을태고
      • 2 5 6 7은 정렬 된상태에서, b를 다시 가져오면 1 4 2 5 6 7로 되버림.
    • 그래서 n개는 무조건 봐야함.
  • a에 3개 이하일때는 푸시 횟수를 줄이고.. 그냥 a에서 끝내자..
    • 줄일 순있지만... 큰차이없지..

이 방법으로는... 최적화하는 방법을 못찾겠다...

퀵 정렬로도 해보자..

설계..

1. 최초 stack을 내림차순정렬해서 int **로 저장해둔다.
  - 정렬 된 데이터를 참조하여 분할 범위를 정확히 반씩 줄여나갈 수 있다.
2. pivot을 현재 탐색 범위의 중간번째 데이터 값으로 정한다.
3. pivot이하의 값중 가장 빨리 보낼 수 있는 데이터를 찾아서, 먼저 B로보낸다.
4. B로 보내면서, B스택을 내림차순한다.
5. A가 비워지면 모든데이터를 A로 push만 한다.


* 1에서 내림차순한 이유
 - pivot기준으로 작거나 같은 값을 B로 보내기 때문에
 - 최초의 좌측범위를 볼때는 pivot값의 위치(인덱스)가 점점 줄어든다. 따라서 B로 보내는 범위를 좁혀가기 위한 전략으로 내림차순을 선택.
   ㅇ 100일때 최초 50번째 이하의 값을 B로(50개)
   ㅇ 다음에는 75번째 이하의 값을 모두 B로(25개)
   ㅇ ...

문제점

  • 3 ~ 4번에서, 가장 빨리 보낼 수 있는 데이터를 찾아서 정렬을 유지하며 보내는 과정이 문제가 되었다.
  • 그 이유는 1 ~ 100개중의 데이터를 정렬할 때 1회전에서는 1~50을 B로보내게 된다.
  • 이 과정에서 스택B가 1~20 , 40~50이 먼저 선택되어 정렬된채로 쌓였다고한다면
50
49
48
.
.
[ 21 ~ 39 ] 가 들어와야 함
.
.
20
19
.
.
.
3
2
1
  • 이후에 21, 30이 차례대로 들어온다고 한다면
  • 21을 삽입할 때
    • 20을 B의 상단으로 올리고
    • 21을 삽입
    • 다시 50을 top으로 되감기. 하게된다.
  • 30이 들어오면 위의 과정을 반복하기 때문에 비효율이 발생한다.

애초에 설계를 잘못했다. 정렬을 유지하며 push하는 과정은 비효율적이다.

문제점

  • ft_lstclear함수가 제대로 동작하는지 확인하기 위해 해당 함수를 호출 전, 후를 비교 했으나 두 경우 모두 leak이 발생하지 않았음...
    • leaks push_swap 으로 확인.

int	main(int argc, const char *argv[])
{
	t_list	*list;

	if (argc < 2)
		return (error_occur(0));
	else
	{
		if (!make_list(&list, argc, argv))
			return (0);
		while(1); // for leak test
	}
	ft_lstiter(list, &print_list);
	// ft_lstclear(&list, &delete_content); // check need
}
  • 동적 할당 된 대상이 존재하고 free되지 않고 프로그램이 돌아가는데 왜 누수가 발생하지 않지 ?
    • slack에서 joopark님의 답변으로 해답을 구했다.

      main 함수에서 malloc을 이용해 힙 영역에 동적 할당한 부분을 main 함수가 종료될 때 free 시켜주어야 합니다.
      return 전에 while문으로 종료가 되지 않도록 막아 놓는다면 그 순간에는 아직 종료가 되지 않았으므로 누수가 없다고 나오며 프로그램 종료와 함께 그 프로세스의 누수를 검사하면 main문에서 할당한 부분이 해제되지 않았기 때문에 누수가 발견될 겁니다.
      => leaks -atExit -- ./[프로그램]로 해결가능.
      ex) leaks -atExit -- ./push_swap 1 2 3

정리

  • leaks로 테스트하려면, 프로그램을 종료시키지 않기위해 무한루프를 코드에 심는다.
  • main함수에서, 누수가 발생하는 코드가 존재할 때에는 무한루프를 돌려도 해당 함수가 종료되지 않았기 때문에 leaks 로 누수를 감지할 수 없다.

뭔가 이상하다 근데 ..

  • 아래 코드로 테스트해봤을 때 1~4는.. 왜 저런결과를 보일까..
    • main [ 1, 2 ]
      • test, test2에서 동적할당 후 a = 0의차이.
      • but모두 leak검출되지 않음.
    • main [ 3, 4 ]
      • [3]: test() -> nothing() => leak검출되지 않음
      • [4]: test2() -> nothing() => leak검출 됨
    • main [ 5 ] : leak 발견되지 않음.
      • 이건 위에서 설명한 이유라면 납득이 감.
#include <stdlib.h>
#include <stdio.h>

int	nothing(void)
{
   return 1;
}


void	test(void)
{
    char *a = (char *)malloc(10);
    a[0] = 'a';
    return ;
}

void	test2(void)
{
    char *a = (char *)malloc(10);
    a[0] = 'a';
    a = 0;
    return ;
}

int	main1(void)
{
    test();
    while(1);
    return (0);
}

int	main2(void)
{
    test2();
    while(1);
    return (0);
}

int	main3(void)
{
    test();
    nothing();
    while(1);
    return (0);
}

int	main4(void)
{
    test2();
    nothing();
    while(1);
    return (0);
}


void	main5(void)
{
    char *a = (char *)malloc(10);
    a[0] = 'a';
    while(1);
    return (0);
}
  • 유추1

test에서 malloc된 메모리주소가, 함수가 종료될 때 반환되고..다른 함수가 호출되면서 덮어쓰인다.. ?

test에서는 malloc한 메모리를 함수 종료시 반환할 수 있음. 따라서 다음 함수 호출 시 그냥 덮여쓰임.

test2에서는, 동적할당 메모리를 0으로 바꾸었기 때문에 stack에서 함수가 종료될 때 사용한 메모리 주소를 반환하지 못함. 따라서 동적할당한 메모리에 다시 접근할 수 없음.

위의 유추가 맞다면 main1, 2에서는 왜 leak이 발생하지 않은거지 ??

더 이상 heap영역을 사용하지 않으니깐 프로그램이 종료되기 전까지는 leak의 유무를 판단할 수 없다 ??

=> 덮어쓰이는 개념은 아닌 것 같다. malloc은 heap영역이고, 함수 호출시 stack을 쓰니깐.

  • 유추2

결국 테스트한 main모두 leaks -atExit -- ./a.out하면 leak은 발생한다.

  • 1을 유추하다보니깐 시점의 차이로 leak검출 결과 차이가 있는것 같다..
  • 테스트 과정에서는 함수 호출 전, 후와 동적할당 변수의 재사용 모두.. leak검출 프로세스 과정에서 영향을 주는 것 같다..
  • 왜지 ?
    • 아..뭔가 heap에 남아있는거 <-> stack에 있는거 비교해서 leak을 잡아내지 않을까 싶은데...
    • 몰르겠다.

일단은, leaks로 검사하고싶으면 무한 loop 심지말고 --atExit 옵션을 주어서 실행하자...

위 원인을 찾으면.. 무한루프심어도 된다..

Test


# 랜덤으로 num개의 데이터를 만들어서 수행
[1] ./test.sh [num]
# 3 ~ 9개의 원소를 가지는 데이터의 순열을 찾아 돌려봄. 
# 5이상은 엄청느림. 중간에 못멈춰서 kill해야 함..
# 왠만하면 3 ~ 4만하기..
[2] ./test.sh all [num](3 ~ 9) => [num] element permutation test
profile
Bigmountain
:)
이전 포스트

프로세스의 이해

0개의 댓글