백준 17298번 오큰수: C언어 풀이

백준 17298 오큰수문제의 C언어 해설입니다.
내림차순 스택을 활용한 문제 풀이 방법과 이를 최적화하는 과정을 설명합니다.
최종 코드로 파이썬 버전을 추가하였습니다.

기본 접근: 내림차순 스택 구현

내림차순 스택으로 오큰수 찾기

스택에 수열의 원소를 하나씩 저장한다.
스택은 항상 내림차순으로 정렬되어 있다고 가정한다.

내림차순이 깨지는 순간을 살펴보자. 8, 5, 3, 2 다음 7이 나온 상황이다.
5, 3, 2의 오큰수는 7이다. 오큰수를 알아냈으니 스택에서 그냥 없애고 7을 넣어준다.
스택에는 8, 7이 남게 되고 내림차순이 유지된다.

인덱스를 저장해서 순서 처리하기

문제는 순서다.

위 예시를 다시 보자. 8, 5, 3, 2 에서 5, 3, 2의 오큰수가 7임을 알아냈다.
한편 8의 오큰수는 아직 모른다. 즉 수열의 순서와 오큰수를 알아낸 순서에 차이가 있다.

출력은 수열의 순서대로 오큰수를 출력해야한다.
이를 해결하기 위해 수열의 원소와 함께 순서를 같이 스택에 넣어주도록 한다.

1차 코드

#include <stdio.h>
#include <stdlib.h>

#define EMPTY -1

struct element
{
    int number;
    int position;
};

int main(void)
{
    int series_size;
    scanf("%d", &series_size);

    struct element *stack = malloc(sizeof(struct element) * series_size);
    int top = EMPTY;
    int *nge_array = malloc(sizeof(int) * series_size);

    for (int i = 0; i < series_size; i++)
    {
        int number;
        scanf("%d", &number);
        struct element element= {number, i};

        // Pop until NGE is found
        while (top != EMPTY && element.number > stack[top].number)
        {
            nge_array[stack[top].position] = element.number;
            top--;
        }
        stack[++top] = element;
    }

    // those remained in the stack have NGE of -1
    while (top != EMPTY)
    {
        nge_array[stack[top].position] = -1;
        top --;
    }

    // Print 
    for (int i = 0; i < series_size; i++)
    {
         printf("%d ", nge_array[i]);
    }
    free(stack);
    free(nge_array);
}

성능 최적화

반복문 쪼개기로 입출력 최적화

문제를 해결하고, 다른 사람들 코드를 읽어보다 흥미로운 점을 발견했다.

백준 사이트에서 맞힌 사람 랭킹은 처리시간 순으로 순위가 나온다.
입출력이 병목인 경우가 많아서일까, 복잡한 코드로 입출력을 최적화한 풀이가 보통 많이 보인다.
근데 이번에는 거의 비슷하게 푼 것 같은데도 처리 시간이 짧은 코드가 꽤나 있었다.

그 중 가장 충격적이었던 발견

for (int i = 0; i < series_size; i++)
{
    scanf("%d", &number[i]);
}

for (int i = 0; i < series_size; i++)
{
   // 스택 관련 코드 while 
}

입력을 받는 부분과 스택을 조작하는 부분을 따로 둔 코드이다.

당연히 이러면 한번 할 순회 과정을 두 번 해서 느려지는거 아닌가? 하고
혹시 몰라서 나도 반복문을 두 개로 쪼개 봤는데...

빨라졌다.

궁금해서 여기저기 찾아보다 보니 이런 자료를 발견했다.
Loop Fission (2)

컴파일러 최적화를 위해 지역성이 뛰어난 코드와 그렇지 않은 코드를 분리해주는 기법이라는 것 같다.
입력을 받는 scanf 부분 반복문을 따로 분리해주면 값을 읽을 때 사용하는 버퍼를 다음 값을 읽을 때도 빠르게 사용할 수 있는 반면,
scanf 뒤에 복잡한 연산이 있으면 컴퓨터가 그거 계산하느라 사용한 버퍼를 갖다 버리기 때문에 느려질 수 있고,
보통 IO 관련한 작업이 속도가 더 느리기 때문에 따로 분리해주면 빨라질 수 있다...
라고 이해했다.

구조체 분리를 통한 메모리 지역성 개선

앞선 Loop Fission 내용을 알아보다 찾은 사이트에서 또 유용한 내용을 발견했다.
Separate Arrays instead of an Array-of-Structs

요약하자면, 쓸데없이 배열에 구조체를 넣어두면 배열 안에 각 요소들이 띄엄띄엄 저장되기 때문에
배열 순회 시에 요소를 전부 사용하는 게 아니면 메모리 지역성이 떨어져서 손해라는 의미이다.

문제 사황에서도 index를 매번 사용하는 건 아니기 때문에 배열을 따로 두어보기로 했다.

또 처음에 제출할 때는 배열 크기를 동적으로 정의했는데,
이번에 최적화를 하는 김에 배열 크기를 정적으로 정의해보기로 했다.

그리고 segfault를 만났다.
보통 segfault는 런타임에서 입력값을 뭐라도 넣어야 나기 마련이었는데 뭐 하나 입력하기도 전에 에러가 났다.

뭐지 싶어서 처음으로 CS50 수업 때 들은 Valgrind를 사용해봤다.

Stack overflow in thread #1: can't grow stack to 0x1ffe801000

Process terminating with default action of signal 11 (SIGSEGV)
Access not within mapped region at address 0x1FFE801F00
Stack overflow in thread #1: can't grow stack to 0x1ffe801000
at 0x1091A0: main 
If you believe this happened as a result of a stack
overflow in your program's main thread (unlikely but
possible), you can try to increase the size of the
main thread stack using the --main-stacksize= flag.
The main thread stack size used in this run was 8388608.

main에서 너무 많은 메모리를 써버려서 스택 오버플로우가 났다구 한다.

이상했다. 다른 사람들도 똑같이 했던 것 같은데 왜 나한테만 이럴까?
치열한 검색 결과 다음의 훌륭한 글을 발견하였다.
C언어 메모리 세그먼트

정리하면, 메인 함수 말고 전역으로 메인 함수 밖에서 선언하면 BSS세그먼트로 런타임에서 메모리를 잡아준다는 것 같다.

역순으로 순회하며 오큰수 찾기

사실 굳이 배열이 3개나 필요한가 하는 생각이 또 들었다.

구조체라는 아이디어에 갇혀 미처 생각 못했지만, series 배열이 이미 존재해서 결과물 출력용 배열이 필요가 없다.
또한 이미 입력을 미리 다 받아놓은 배열이 존재하니 배열을 역으로 오른쪽부터 순회해서 오큰수를 결정하는 것도 가능하다.

후자가 재밌어 보이니 후자로 다시 코드를 짜보았다.

최종 구현

C언어 최종 구현 코드

#include <stdio.h>

#define MAX_SIZE 1000000
#define EMPTY 0

int series[MAX_SIZE];
int stack[MAX_SIZE];
int top = EMPTY;

int main()
{
    int series_size;
    scanf("%d", &series_size);

    for (int i = 0; i < series_size; i++)
    {
        scanf("%d", &series[i]);
    }

    // Dummy value to optimize empty check
    stack[EMPTY] = MAX_SIZE + 1;

    // Loop from right to left
    for (int i = series_size - 1; i >= 0; i--)
    {
        // Pop until NGE is found 
        while (series[i] >= stack[top])
        {
            top--;
        }

        // If there is no NGE set to -1
        int nge = (top == EMPTY) ? -1 : stack[top];

        // Push 
        stack[++top] = series[i];

        // map NGE inplace
        series[i] = nge;
    }

    // Print calculated NGE result 
    for (int i = 0; i < series_size; i++)
    {
         printf("%d ", series[i]);
    }
}

Python 코드

import sys

MAX_NUM = 1_000_000
size, *series = map(int, sys.stdin.buffer.read().split())

stack = [MAX_NUM + 1]
for i, num in reversed(list(enumerate(series))):
    while stack[-1] <= num:
        stack.pop()
    nge = stack[-1] if len(stack) > 1 else -1
    series[i] = nge
    stack.append(num)

print(' '.join(map(str, series)))

후기

이것 저것 배우는건 참 많았는데 학기도 시작해버린 마당에 이 속도로 언제 큐로 넘아갈 수 있을런지..