push_swap

개요

• stack

  스택을 구현하고 그것을 운영하는 함수들을 만들어야 하는 프로젝트로 보인다.

• content

  스택의 각 원소들은 int 형 컨텐츠와 이전 원소의 주소, 다음 원소의 주소를 보관하는 양방향 링크드 리스트 구조로 설계해야겠다.

  이렇게 하면 스택과 원소를 분리할 수 없게 된다는 단점이 있다. 즉 하나의 원소를 여러개의 스택에 등록시키는 것이 불가능해진다.

• iterator

  스택위에서 움직이는 iterator을 만들어야 겠다. 진행방향 (reverse or straight)을 저장하고, 현재 원소 주소를 저장하는 구성이다.

  iterator는 개념적으로 어떤 원소를 가르키고 있지 않고 원소와 원소 사이에 존재하는 개념이다. iterator의 now는 없고, before 과 next 만 존재한다.
  예를 들어 next 의 index가 2일 경우 before 의 index는 1을 가리키고 있는 상태이고, iterator가 존재하는 위치는 1과 2 사이이다.

  iterator가 대상 stack의 종점에 도달한 뒤 next를 청구할 경우 NULL을 반환하도록 했다.
  iterator에 정보를 청구할 때 iterator->version 대상 stack->version 을 비교하고 일치하지 않을 경우 NULL을 반환하도록 했다.

진행 상황 정리

• 각원소, 스택, iterator을 디자인하고 구현했다.
• iterator을 만들어 반환하는 함수 get_iterator_mind_null()을 구현했다.
  • 여기서 mind_null은 반환값에 null이 올 수 있다는 의미이며, null일 경우 호출 함수에서 비상종료동작이 필요하다.

구성개요

• utils.c

  • emergency_exit()을 만들었다.

    해당 함수는 내부적으로 exit(1)을 실행하는 함수로 여러가지 에러 상황에 동적할당을 모두 해제하고 종료해주는 역할을 수행할 것이다.

  • check_input()을 계획중이다.

    해당 함수는 main함수에 전달된 입력값의 유효성 검사에 사용될 함수이다.

• iterator_manipulation.c

  • iter_next_content()을 만들었다.

    iterator을 인자로 받아 대상 스택의 다음 content를 반환해주는 함수이다. 또한 iterator의 표시 위치를 1 증가시킨다.

  • iter_retreat_content()을 만들었다.

    iterator을 인자로 받아 대상 스택의 이전 content를 반환해주는 함수이다.
    또한 iterator의 표시 위치를 1 거슬러 올라가게 한다.

• stack_push_pop.c

  • stack_pop_content()을 만들었다.

    스택을 전달 받아 스택의 top에 있는 content를 인출해준다.

  • stack_pop_back_content()을 만들었다.

    스택을 전달 받아 스택의 bottom에 있는 content를 인출해준다.

  • stack_push_content()를 만들었다.

    스택과 원소를 전달 받아 스택의 top에 전달받은 원소를 등록해준다.

  • stack_push_back_content()를 만들었다.

    스택과 원소를 전달 받아 스택의 bottom에 전달받은 원소를 등록해준다.

진행 상황 정리

• 각원소, 스택, iterator의 디자인을 일부 변경했다. (version 기능 추가 등.)
• ~~iterator을 만들어 반환하는 함수 get_iterator_mind_null()을 구현했다.~~
  _mind_null의 기능이 exit()을 사용할 수 있게 되어 필요 없어졌다. 따라서 삭제했다.
• emergency_exit()을 구현하고, stack의 push, push_back, pop, pop_back 함수를 구현했다.
• iterator 조작 함수를 구현했다.

진행개요

• parse_input()을 디자인하고 있다.

  위 함수의 기능은 main 함수에 들어오는 인풋을 해석하여 오류 여부를 판별하고, (오류면 emergency_exit()실행)
  오류가 아니라면 입력들로 content를 만들고 stack에 먼저번 입력부터 push back하여 첫번째 입력이 top에 오도록 stack을 만들어 반환한다.
  기능이 많아 parse_input_subsidiary() 를 하위함수로 두려고 한다. (static 함수)

• sorting 알고리즘 을 제외한 모든 기능의 구현을 완료했다.

진행개요

끝냈다.

• sorting 알고리즘은 merge sort 의 방식을 선택했다.

  사용할 수 있는 자료공간이 2개의 스텍으로 제한되는 점을 고려해서 다들 quick sort를 선택하는 것 같은데 왠지 나는 다르게 하고싶고 나만의 방식으로 직접 모두 고민하고 부딪히고 싶어 merge sort를 고집했다. 머리가 깨질뻔했다. 알고리즘 아이디어 자체는 어렵지 않은데 두개의 스텍을 번갈아 오가며 정렬하는 실재를 구현하는게 상당히 복잡했다. (적어도 내가 생각하기엔...)

  여러번 segfault를 거치어 뼈대를 만들고 실행 명령 수를 줄이는 과정에 꼬박 10시간이 걸렸다. 아쉽게도 목표인 500개 입력을 5500개의 명령 이하로 통과하는 코드를 짜는 것은 오늘은 무리인것 같다.

  최적화도 여러군데에서 여러번 진행했다.

  첫 번째 버전: 500개 6700회 두 번째 버전: 500개 6500회 세 번째 버전: 500개 6300회

  또한 오늘의 마지막인 네 번째 버전은 첫번째 배치 사이즈인 4개의 입력 이하의 입력에서 극도로 비효율적인 퍼포먼스를 보이는 것을 해결하고, 4개 5개 6개 까지의 입력에 대해 최적의 성능을 보일 수 있도록 수정하였다.

  

  :two_hearts:

진행개요

• 어제 평가에서 fail이 나왔다. 5개의 데이터가 입력되었을 때 명령어 12개 이하를 사용하는 일관된 퍼포먼스가 나오지 않아서이다.

  이 부분에 대해 추가적인 하드코딩 작업을 하였다.

5개 입력에 대한 처리

• 5개의 입력이 들어 있는 stack 을 넘겨 받아 2번째로 작은 수를 찾아 반환하는 함수를 만들었다. (하단 function design 참고)
  • 입력된 5개의 숫자 중 2번째로 작은 수를 찾는다. (명령실행 횟수 0)
  • 2번째로 작은 수 보다 같거나 작은 수 (가장 작은수, 2번째로 작은 수) 2개를 RA를 수행하며 A를 회전시키며 찾는다. (명령 실행 횟수 +2~5) 발견시 PB 로 B stack으로 넘겨준다.
  • 위 동작이 끝난 후 A stack에 남은 3개의 숫자를 3개를 정렬하는데 특화된 함수를 사용해 정렬한다. (명령 실행 횟수 +0~2)
  • B stack에 있는 2개의 숫자를 (top에서부터)내림차순이 되게끔 RB 를 사용한다. (명령 실행 횟수 +0~1)
  • 이후 PA 2회 시행하면 A stack에 5개의 숫자가 오름차순 정렬 상태가 된다. (명령 실행 횟수 +2)

실행결과

과제 요구사항에 맞는 12회 미만의 명령 사용을 보여준다.