[TIL][Krafton Jungle] 4주차 - (4) : 스터디 리뷰 & 세그멘트 폴트 문제 해결

오늘은 코알라(코딩 알고리즘 라이브) 스터디를 처음 시작한 날이다.

 

스터디에서 푼 문제에 대한 리뷰와 세그멘테이션 폴트를 해결한 내용을 작성하겠다.

 

---

 

코알라 스터디

코알라 스터디 디코방

 

코딩 알고리즘 공부를 계속하고 싶어서 정글 교육생들과 함께 스터디를 만들었다.

 

매주 일요일에 3문제씩 실제 코테처럼 응시한 뒤, 각자 본인이 문제에 대한 접근법을 설명하는 방법이다.

 

알고리즘 문제 푸는 능력을 빠르게 키우는 건,

잘 하는 사람들의 문제 접근 방법을 들여다 보는 것이라 생각한다.

 

그래서 알고리즘에 익숙한 사람들과 같이 어떻게 접근했는지 방법을 들어보면서,

내 실력도 빠르게 키울 수 있었으면 좋겠다.

 

그리고 또 알고리즘 실력이 부족하다고 생각되서 참여하기가 꺼려지는 분들은

점수 매기는 거 아니니까 많이 들어와서 같이 실력 키워봅시다 !

 

 

 

아무튼.

 

이번주 문제는 이분 분할 / 우선순위 큐 + 그리디 / 스택 + 그리디 문제를 출제해봤다.

 

처음부터 어렵게 내면 다 도망갈까봐 쉽게 냈는데

반대로 너무 쉬워서 도움 안된다고 할까봐 걱정했는데,

 

아무도 3번째 문제는 시간내로 못품.

 

근데 이런 수준이면 코테는 어림도 없겠다 싶어서 더 열심히 해야겠더라..

 

그 중 가장 생각해 내기 어려웠던 문제인 스택 + 그리디 문제를 리뷰해 보겠다.

 

BaekJun - #2812 : 크게 자르기(Stack 자료구조)

출처 : https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

코딩 테스트를 무작위 유형으로 출제하니까

 

특정 알고리즘으로 풀어야 하는 문제라는 것을 모른 상태로 문제를 응시한다는 것이 굉장히 낯설고 어려웠다.

 

원래 실제 기업 코딩 테스트는 그런 상황이겠지만,

아직 코린이인 나는 Stack 자료구조를 빠르게 훑고 간 나머지,

Stack으로 접근해야 한다는 접근이 굉장히 어려운 발상이었다.

 

 

이 문제는 특정 수를 주고, 이 수에서 n개의 수를 빼서 최대의 값을 가지는 수를 만드는 것이다.

 

예를 들면,

1924에서 2개를 빼서 가장 큰 수는

1과 2를 뺀, 94이다.

 

 

나는 문제를 접근할 때, 특정 유형의 문제로 보이지 않으면 일단

입력 예시에 맞추어 구현을 하면서 이해를 한 뒤 문제 상황을 하나씩 해결해 나가다가,

우선순위가 필요하다면 우선순위 큐를 사용하는 방식으로 문제를 해결하려고 접근한다.

 

근데 이 문제는 전체적인 상황을 파악한 뒤,

스택 이라는 자료구조를 사용해야 한다는 것을 캐치하는게 맹점이었다.

 

이 문제를 통해스택의 자료구조는

오른쪽이나 왼쪽으로 1방향으로 훑지만, 판단을 이전 상황과 비교하며 수행해야 할 때 사용할 수 있다고 생각했다.

 

이 문제가 그랬다.

 

수를 하나씩 삽입하되 이전 수보다 지금 수가 크다면 삽입했던 걸 지워야 하는 방식이었다.

 

근데 문제의 지저분한 특정 상황이 많아져서 코드가 길어졌다.

 

아래 코드가 이 문제를 해결한 코드이다.

 

import sys

n,k = map(int,sys.stdin.readline().split())
number = sys.stdin.readline().strip()

pop_count = 0
stack = []

sliced_index = 0
for i in range(n):
    while pop_count < k:
        if not stack:
            stack.append(int(number[i]))
            break
        elif int(number[i]) <= stack[-1]:
            stack.append(int(number[i]))
            break
        else:
            stack.pop()
            pop_count += 1

    if pop_count == k:
        sliced_index = i
        break

while len(stack) > n-k :
    stack.pop()
    sliced_index = n+1

for i in range(sliced_index,n):
    stack.append(int(number[i]))

if len(stack) >= 2:
    for i in range(len(stack)-1):
        print(stack[i],end='')
print(stack[-1])

 

코드가 상당히 지저분하고, 난해하다.

 

문제 자체가 그랬던 것도 있지만,

생각보다 특정 생각하기 힘든 상황들이 코드를 작성하고 여럿 떠오르면서 살이 붙은 상황이다.

 

전체적으로는 만약 stack의 탑의 수보다 현재 수가 더 크면 탑을 pop하고 버린 뒤 현재 수를 넣고,

pop한 횟수를 측정하는 방식인데,

 

만약 계속 내림차순인 수가 stack에 순회하며 append된다면,

pop은 하지않고 stack에 계속 쌓이는 상황이 발생해서 while문을 하나 밑에 더 넣어줬다.

 

마지막 print문도 두개로 나눠진 이유는 마지막 '%' 가 의도치 않게 출력되어 저렇게 마지막엔 end=''를 넣어주지 않기 위해 나눴는데,

 

더 나은 방식으로 clean하게 정리해서 짤 수도 있을 것 같지만, 시간이 부족해서 그렇게 하진 못했다.

 

---

 

RB-Tree 구현 연장선 (Segmentation Fault 해결)

IDE의 친절한 디버깅 없이 많은 양의 코드를 직접 구현하고, 실수를 찾아내는 것은 역시 쉽지가 않았다.

 

하지만 우리는 임시 디버깅 파일인 Make 파일과, test파일이 있기에, 로깅과 주석을 적절히 활용해서 문제 구간은 쉽게 찾을 수 있었다.

 

문제가 발생했던 테스트의 함수는 아래의 코드였다.

 

void test_find_erase(rbtree *t, const key_t *arr, const size_t n) {
  for (int i = 0; i < n; i++) {
    node_t *p = rbtree_insert(t, arr[i]);
    assert(p != NULL);
  }

  for (int i = 0; i < n; i++) {
    node_t *p = rbtree_find(t, arr[i]);
    printf("arr[%d] = %d\n", i, arr[i]);
    assert(p != NULL);
    assert(p->key == arr[i]);
    rbtree_erase(t, p);
  }

  for (int i = 0; i < n; i++) {
    node_t *p = rbtree_find(t, arr[i]);
    assert(p == NULL);
  }

  for (int i = 0; i < n; i++) {
    node_t *p = rbtree_insert(t, arr[i]);
    assert(p != NULL);
    node_t *q = rbtree_find(t, arr[i]);
    assert(q != NULL);
    assert(q->key == arr[i]);
    assert(p == q);
    rbtree_erase(t, p);
    q = rbtree_find(t, arr[i]);
    assert(q == NULL);
  }
}

void test_find_erase_fixed() {
  const key_t arr[] = {10, 5, 8, 34, 67, 23, 156, 24, 2, 12, 24, 36, 990, 25};
  const size_t n = sizeof(arr) / sizeof(arr[0]);
  rbtree *t = new_rbtree();
  assert(t != NULL);
  test_find_erase(t, arr, n);

  delete_rbtree(t);
}

 

어제 직접 노드를 삭제한 뒤 free()해주지 않아서 발생한 것 같다고 얘기했었는데,

그 방식을 사용해도 해결되지 않아 하루종일 코드를 뒤졌다.

 

그 전에 sementation fault가 발생했던 위 함수 중 특정 구간을 확인해보니,

 

for (int i = 0; i < n; i++) {
    node_t *p = rbtree_find(t, arr[i]);
    printf("arr[%d] = %d\n", i, arr[i]);
    assert(p != NULL);
    assert(p->key == arr[i]);
    rbtree_erase(t, p);
  }

 

이 곳이었다.

 

erase가 3번까지 작동하더니 바로 아몰랑 Segmentation Fault Error를 발생시켰다.

 

erase문을 주석처리하면 문제 없이 실행된다는 것을 확인 한 후, 내가 만든 커스텀 erase 함수가 문제가 있다는 것을 알게 됬다.

 

그래서 직접 만든 함수를 뜯어 고쳐보려 하니,

도무지 어디가 문제가 발생했는지 알 수가 없고,

내가 원하는 방식으로 잘 진행 되는 코드일 것만 같았다.

 

int rbtree_erase(rbtree *t, node_t *p) {
  // TODO: implement erase
  node_t *y = p;
  color_t eNodeOri_C = p->color;
  node_t *x = p->right;
  if(p->left == t->nil){
    x = p->right;
    rb_transplant(t,p,p->right);
  }
  else if(p->right == t->nil){
    x = p->left;
    rb_transplant(t,p,p->left);
  }
  else{
    y = sub_rbTree_min(t,p->right);
    eNodeOri_C = y->color;
    x = y->right;
    if(y->parent == p){
      x->parent = y;
    }
    else{
      rb_transplant(t,y,y->right);
      y->right = p->right;
      y->right->parent = y;
    }
    rb_transplant(t,p,y);
    y->left = p->left;
    y->left->parent = y;
    y->color = p->color;
  }

  if(eNodeOri_C == RBTREE_BLACK){
    rb_delete_fixup(t,x);
  }
  t->root->parent = t->nil;
  free(p);
  return 0;
}

node_t *sub_rbTree_min(rbtree *t, node_t *n){
  node_t *sub_min_node = n;
  while(sub_min_node != t->nil){
    sub_min_node = sub_min_node->left;
  }
  return sub_min_node;
}

void rb_transplant(rbtree *t, node_t *u, node_t *v){
  if(u->parent == t->nil){
    t->root = v;
  }
  else if(u == u->parent->left){
    u->parent->left = v;
  }
  else{
    u->parent->right = v;
  }
  v->parent = u->parent;
}

void rb_delete_fixup(rbtree *t, node_t *n){
  while( n != t->root && n->color == RBTREE_BLACK){
    if(n == n->parent->left){
      node_t *w = n->parent->right;
      if(w->color == RBTREE_RED){
        w->color = RBTREE_BLACK;
        n->parent->color = RBTREE_RED;
        left_rotate(t,n->parent);
        w = n->parent->right;
      }
      if(w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK){
        w->color = RBTREE_RED;
        n = n->parent;
      }
      else{
        if(w->right->color == RBTREE_BLACK){
          w->left->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          right_rotate(t,w);
          w = n->parent->right;
        }
        w->color = n->parent->color;
        n->parent->color = RBTREE_BLACK;
        w->right->color = RBTREE_BLACK;
        left_rotate(t,n->parent);
        n = t->root;
      } 
    }
    else{
      node_t *w = n->parent->left;
      if(w->color == RBTREE_RED){
        w->color = RBTREE_BLACK;
        n->parent->color = RBTREE_RED;
        right_rotate(t,n->parent);
        w = n->parent->left;
      }
      if(w->right->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK){
        w->color = RBTREE_RED;
        n = n->parent;
      }
      else{
        if(w->left->color == RBTREE_BLACK){
          w->right->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          left_rotate(t,w);
          w = n->parent->left;
        }
        w->color = n->parent->color;
        n->parent->color = RBTREE_BLACK;
        w->left->color = RBTREE_BLACK;
        right_rotate(t,n->parent);
        n = t->root;
      }
    }
  }
  n->color = RBTREE_BLACK;
}

 

위 코드는 문제가 발생한 erase의 코드이다.

(위 코드에서 문제점을 찾는다면 당신은 코딩의 신)

 

 

 

함수 안에 내부적으로 실행해야 하는 함수가 많다 보니 양이 많아 한번 코드를 머리속으로 따라가 보는것도 한참 걸린다.

 

하나씩 코드를 따라가 보니, 문제는 sub_rbTree_min에 있다는 것을 확인했다.

 

node_t *sub_rbTree_min(rbtree *t, node_t *n){
  node_t *sub_min_node = n;
  while(sub_min_node->left != t->nil){
    sub_min_node = sub_min_node->left;
  }
  return sub_min_node;
}

 

이게 수정한 sub_rbTree_min이다.

 

위 함수의 역할은 node를 넣으면 그 노드를 루트가 되는 서브 트리에서의 최소 key의 노드를 return하는 함수이다.

 

근데 문제가 발생했던 위 코드를 보면, while문의 조건이 sub_min_node가 nil이 될때까지 내려가도록 되어있었다.

 

그래서 이 함수는 무조건 nil을 return 하도록 되어있던 것이다...ㅠ,.ㅠ 

 

그래서 문제를 해결했더니.. !

 

 

구웃 ~ !

 

Segmentation Fault 때문에 free() 기능도 생각해 내서 구현해 놓은 것은 잘한 것이지만,

애초에 문제는 로직적인 구간에서 발생되니, 꼭 잘 살펴봐야겠다.