C 언어 - stdio.h 만 가지고 백준 문제 풀어본 결과

제목 : stdio.h 만 가지고 백준 문제 풀어본 결과

---

코드 결과를 빠르게 보고 싶다면, 밑의 텍스트를 클릭하세요

코드로 바로 이동하기

다양한 라이브러리가 존재하는데, 굳이 힘들게 푸는 이유는?

이러한 힘든 도전을 하는 이유는, "C 와 최소한의 Lib 로 알고리즘 풀어보기 도전" 썼던 글 에 상세히 적어놓았다.

요약하자면, Node.js 엔진 기반의 JS 의 성능적 한계점을 느끼고, 최적화를 수행하고 구현하면서,

최적화 과정이 저 수준의 언어로 제작하는 것 보다 훨씬 더 어렵다는 것을 느꼈다.

이럴 거면 애초에 최적화 타겟 언어로 프로그램을 제작하는 것이 더 낫다는 판단을 했다.

그리고, 특히 특정 도메인의 프로그램을 제작하기 위해 다양한 라이브러리의 역할도 알지 못한 채,

쉽게 가져와서 사용하기만 해버리는 단순한 방법론적 프로그래밍에 회의감이 들었다.

특히, 특정 프레임워크를 선택하고 공부 할 때,

이것을 구현하기 위해, 저 메서드, 클래스를 간단히 가져와서 쓴다, 라는 관점으로 볼 때는

빠른 구현을 위해 프레임워크를 도입하는 것이 좋다고 생각한다.

그러나, 프레임워크 자체가 하나의 또다른 언어 수준으로 공부가 필요 해 지는 시기가 온다.

그 이유는, 프레임워크에서 가져온 어려운 방법론이 어떻게 작동하는지 모르고, 이를 외우기 때문이라고 생각한다.

처음에는 나도 공식문서를 따라서 구현하며 만든 컴포넌트, 혹은 WAS(백엔드) 프로그램이 간단히 제작되는 것을 보고 좋아했는데,

구조적으로 개편하거나, 최적화를 진행하는 순간, 나는 알려주는 것 말고 아무것도 아는 것이 없었다는 것을 알게 된다.

이러한 회의감은 React, NestJS, Express, TypeORM, Spring, Next.js 등등 수많은 공식문서를 배우며 느끼게 되었다.

결국 나의 학습 방법이 틀렸다는 것을 인지하고, 모르는 것이 생겼을 때, 이 의문이 미래의 학습에 얼마나 도움이 되는지를 생각한다.

예를 들어, 현재 내가 가상화 컨테이너에 대해 알고 싶어 조사하며 글을 작성하고 싶다고 한다면,

이는 작성할 수 있다. 실질적인 온라인 배포 및 클라이언트 유치를 위해 꼭 필요한 과정이기 때문이다.

그러나, K8S(Kubernetes) 가 뭔지 궁금하다고 지금 당장 공부하지 않을 것이다.

첫 번째로 지금 공부하고 있는 도메인과 조금 떨어져 있을 뿐 더러,

아직 컨테이너 오케스트레이션과, 도커, 가상화 기술에 대해 제대로 알고 있지 않기 때문이다.

이러한 성찰을 바탕으로, "나는 어떻게 알고리즘을 공부해야 하는가?" 에 대해 혼란스러워 했다.

언뜻 나는 백엔드에 가까우니 Spring 을 할 것 같으니, 알고리즘을 Java 로 공부했다.

그러나, 지금 나의 행보는 Spring 에 가깝지 않으며, 오히려 웹 서버 개발과,

그에 반대되는 저 수준의 언어를 이용하여 직접 메모리 관리하는 것에 좀 더 가까웠다.

따라서, 역사가 매우 깊으며, 대부분의 언어가 형식을 참조하거나, 이를 아직도 활용중인

C 언어를 사용하여 알고리즘을 풀기로 했다.

이는 여러 전략이 있는데,

• 웹 개발 공부를 진행하며, 웹 모듈(.wasm) 으로 최적화 전략을 생각할 수 있음
• 필요 할 시, 범용성 높은 c++ 로 전환이 가능함
• 메모리 직접 관리로 GC 의 중요성 깨닫기
• 클래스가 존재하지 않으므로, struct (구조) 를 이용한 추상화 및 구현 전략 채택하여 Golang 고려
• 현재 사용중인 에디터가 Zed 라는 Rust 로 제작된 에디터인데, 부족한 마크다운 프리뷰를 고치고 싶음
  • Rust 의 메모리 빌림을 더 정확하게 이해하기 위해서 메모리 관리를 직접 해 보는 것이 중요하다 생각(개인적)
• 포인터에 대한 직감 발달을 위함

Java 입출력 전략을 C 로 가져오기

입력 문자열에 대한 토큰화 진행하기

Java 에는 입력 문자열에 대해 토큰화를 수행하는 StringTokenizer 라는 클래스가 존재한다.

생성자와 함께 인수로 토큰화를 수행 할 문자열 을 넣어주면,

생성된 객체를 통해 토큰을 하나씩 꺼내 사용 할 수 있다.

그러나, C 에서는 scanf("%d", &받을 숫자) 와 같은 메서드를 통해 하나씩 꺼내 사용하고 있었다.

나중에 입력의 토큰 수가 동적으로 변할 문제들을 고려하여, tokenizer 라는 나만의 메서드를 만들었다.

입력된 문자 배열 char* 를 toeknizer 에 보내주면,

char** 형태로 반환되는데, 이는 "각 문자 배열의 시작 주소를 가진" , "주소 배열" 이다.

마지막 주소에는 NULL 이 들어가 있기 때문에, 확실하게 끝을 인지할 수 있다.

숫자 문자열을 정수로 변환하기

보통 scanf("%d", ...) 를 통해서 이미 정수 변수로 할당 받으면 상관하지 않아도 될 부분이기도 하다.

그러나, 나는 이 부분도 parseInt 라는 메서드로 제작했다.

먼저, 간단하게 수 0 을 가진 변수를 만들어 놓고,

숫자 문자 배열의 마지막이 올 때 까지, 변수를 x10 하고, 현재 숫자 문자를 실제 수로 변환하여 더한다.

이에 대한 예시는 맨 밑의 코드를 참조하길 바란다.

숫자 문자를 수로 변환하기

이건 매우 쉬운데, 먼저 알아야 할 것은, 문자 배열의 순서는 '0' --> '9' 순으로 간다는 것이다.

따라서, char - '0' 으로 계산하면, 바로 현재 수 문자의 정수가 추출된다.

빈 공간을 감지하기

위에서 tokenizer 라는 토큰 문자열 주소 배열을 반환하기 위해서 사용되는 기능인데,

빈 공간을 감지한다면, 이는 넘거거나, 이제 토큰화를 시작해야 한다는 의미이다.

이 때, 물론 C 라이브러리로 해결 할 수 있지만, 나는 조금 간단히 생각했다.

char 값으로 32 = ' '(스페이스) 이며, 9 ~ 13 까지가 줄넘김, 탭 등등을 의미한다.

이러한 값을 인지하는 isBlank 함수를 만들었다.

Java 에서 C 를 사용하니 느껴지는 제약들

메모리를 직접 관리해야 한다.

Java 에서는, JVM 에서 Garbage Collector(쓰레기 수집기) 와 상호작용하면서,

곧 폐기처분 될 확률이 높은 Eden 영역, 오래 살아남는 메모리 영역 Old 영역을 분리하여 관리한다.

그러나, C 에서는 그런거 없다. calloc, malloc, 혹은 realloc 으로 동적 메모리 확장한

모든 메모리들은 stdlib.c 헤더의 free 메서드를 이용하여 직접 메모리 해제를 해 주어야 한다.

직접 문제를 풀기 위해 다양한 기능을 만들면서 느꼈던 것인데, 요즘 왜 Zig 나 Rust 가 뜨는지 이해가 되었다.

둘 다 메모리 안정성을 기반에 두고 만든 저 수준의 언어

클래스가 없다.

내가 이전에 Java 로 백준을 풀 때는, 특정 도메인의 유틸 기능들을 모아놓은 클래스를 직접 제작하여 문제를 해결했다.

HashMap, HashSet, Tree, Queue, Stack 등등을 직접 구현하며 자료구조에 대한 이해도를 높였다.

그러나, C 에서는 C++ 과 달리, 클래스가 존재하지 않는다. 대신, struct 가 존재한다.

예를 들어, 우리가 특정 클래스를 만든다면, 클래스가 가질 고유의 "변수" 와 "객체" 를 선언하고,

이 클래스를 위해 사용될 메서드를 내부에서 직접 작성했다.

그러나, struct 는, 구조 가 가질 고유의 "변수" 와 "객체" 까지는 선언이 가능하나,

생성자와 소멸자를 외부에서 만들어야 하며, 이 구조(struct) 는 메서드를 추상화로 선언한다.

그리고, 외부에서 추상화 된 메서드를 직접 구현하는 형식이다.

이에 대해 굉장히 잘 작성 해 놓은 분이 계셔서, 글을 공유한다.

https://blog.naver.com/ruvendix/220980152324

포인터와 메모리 주소에 대한 개념을 숙지하고 있어야 한다.

Java 에서는 배열과 객체에 대한 정보를 JVM 이 관리하여,

우리가 직접 시스템 수준의 메모리를 건드리지 않고, JVM 이 생성 및 소멸시켜 관리했다.

이 과정에서, JVM 은 객체와 배열의 정보를 내부에 메타데이터로 저장했다.

역시나, C 는 그런것이 없다.

따라서, 우리는 객체를 생성하거나, 배열을 생성 할 때, 이 객체 혹은 배열에 대한 사이즈를 명확히 작성해야 한다.

그런데 이건, 쉽게 sizeof(<원시데이터>), sizeof(<struct 이름>)

주소의 끝을 인식할 다양한 방법을 알고 있어야 한다.

내가 백준 문제를 풀면서, 문자 배열을 순회할 때, for 을 거의 사용하지 않고, 대부분 while 로 작성했다.

이는 문자 ('\0') 가 문자 배열의 "끝" 을 알리기 때문이다.

그리고, 객체 혹은 배열의 시작 주소를 가진 포인터 배열은 NULL 로 표현이 가능하다.

그러나, 만약에 수 배열이 온다면, 이야기가 달라진다.

숫자 배열은 END 값을 0 으로 가진다. 따라서, 우리는 길이에 대한 메타데이터를 직접 생성하여 관리해야 한다.

이 경우, for 문을 사용하여 해결했다.

모든 함수와 객체, 변수에 대한 정보는 추상화 시켜 미리 작성해야 한다.

이것도 C, C++ 이 서로 다른 경향인데,

C 는 위쪽에서 작성된 코드가 아래의 구조 혹은 메서드를 호출 할 때, 무엇인지 알지 못한다.

이는 컴파일러가 위에서부터 아래로 읽기 때문이라서, 파일의 맨 위 쪽에 미리 추상화를 시켜놓아야 한다.

이러한 제약은 생각 외로, 이 문제를 풀기 위해 어떤 기능이 필요할지 세밀하게 생각하게 해 주는 계기가 되었다.

C 로 푼 문제 :

https://www.acmicpc.net/problem/1008

결과 :

/**
시간 제한    메모리 제한    제출    정답    맞힌 사람    정답 비율
2 초    128 MB    872353    296109    244527    34.468%
문제
두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력
첫째 줄에 A/B를 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-9 이하이면 정답이다.

예제 입력 1
1 3
예제 출력 1
0.33333333333333333333333333333333
10-9 이하의 오차를 허용한다는 말은 꼭 소수 9번째 자리까지만 출력하라는 뜻이 아니다.

예제 입력 2
4 5
예제 출력 2
0.8
 */

#include<stdio.h>

extern void* malloc(size_t);
extern void free(void*);
extern void* realloc(void*, size_t);

int parseInt(const char* str); // 주어진 문자열을 정수로 만든다. - 입력 파싱
char* doubleToString(double target); // 결과로 출력해야 하는 double 타입을 문자열로 만든다.

char** tokenizer(const char* str); // 입력으로 주어진 한 줄 입력을 토큰으로 만들어 주소값 배열을 반환한다.
int chToInt(char ch); // 단순한 숫자 문자 하나를 정수로 바꿔 전달한다.
_Bool isBlank(char ch); // 현재 문자가 빈 칸에 해당하는 문자인지 알려준다.


int main () {
    char chList[255];

    char* str = fgets(chList, sizeof(chList), stdin);

    char** tokens = tokenizer(str);
    char** tokensPtr = (char**)tokens;

    double baseNum = (double)parseInt(*tokensPtr);
    tokensPtr++;

    while(*tokensPtr) {
        baseNum /= (double)parseInt(*tokensPtr);
        free(*tokensPtr);
        tokensPtr++;
    }
    free(*tokens);

    char* result = doubleToString(baseNum);

    fputs(result, stdout);

    // 결과 출력으로 사용한 문자열 풀어주기
    free(result);

    // free 작업
}

int parseInt(const char* str) {
    int result = 0;
    short sign = 1;

    char* strPtr = (char*)str;

    // 음수 문자가 올 경우, 이를 따로 처리 및 저장.
    if(*strPtr == '-') {
        sign = -1;
        strPtr++;
    }

    // 숫자 문자 앞에서부터 파싱하여 넣는다.
    while(*strPtr) {
        // 이미 계산된 수는 이번 수를 넣기 위해 공간을 창출한다.
        result *= 10;

        int currNum = chToInt(*strPtr);

        // 빈 공간에 수 넣기
        result += currNum;

        // 다음 문자로 이동
        strPtr++;
    }

    return result * (int)sign;
}



char* doubleToString(double target) {
    int sign = 1;

    if(target < 0) {
        sign = -1; target *= -1;
    }

    // 소수부를 무시한 값으로 정수 값을 추출
    int intPart = (int)target;

    // 정수부를 다시 소수부로 만들어서 정수만 빼고, 소수부만 남기기
    double doublePart = target - (double)intPart;


    // 정수 문자가 들어갈 사이즈
    int intSize = 0;
    // 정수 길이를 구하기 위한 임시 정수
    int tempInt = intPart;

    // 정수 길이를 구하기
    while(tempInt != 0) {
        tempInt /= 10;
        intSize++;
    }

    char* intStr = (char*)malloc(sizeof(char) * intSize + 1);
    intStr[intSize] = '\0';

    // 생성된 문자 배열의 마지막부터 시작하여 수를 넣는다.
    for(int i = intSize - 1; i >= 0; i--) {
        // 항상 첫 번째 자리수를 추출한다.
        int number = intPart % 10;
        // 추출한 자리수의 문자는 '0' 을 더해주면 된다.
        intStr[i] = (char)(number + '0');
        // 그리고, 모든 자리수를 하나씩 이동한다.
        intPart /= 10;
    }

    // 문제에서는 9 자리까지 맞으면 된다고 하니, 10 자리까지 정확도를 올림.
    const int MAX_SIZE = 10;

    char* doubleStr = (char*)malloc(sizeof(char) * MAX_SIZE + 1);
    doubleStr[MAX_SIZE] = '\0';


    int currDeep = 0;

    // 10 개를 넣을 예정.
    while(currDeep < MAX_SIZE) {
        // 지속적으로 각 소수부를 위로 한 칸씩 올림
        doublePart *= 10;

        // 정수가 된 소수부를 추출
        int extractNum = (int)doublePart;

        doublePart -= extractNum;

        // 이를 가지고 문자열로 형성
        doubleStr[currDeep++] = (char)(extractNum + '0');
    }

    // 정수 문자열, 소수 문자열이 전부 완료 된 상황.

    // 만약에, 정수가 애초에 0 이라서 제대로 할당이 되지 못했을 경우 (".33333" 으로 나옴)
    if(intSize == 0) {
        // 0 을 위한 공간으로 재할당
        intStr = (char*)realloc(intStr, 2);
        intStr[0] = '0';
        intStr[1] = '\0';
        // 0 이 들어갔으므로.
        intSize = 1;
    }

    // .(점) 을 넣을 공간까지 고려한 사이즈. and 마이너스 일 경우 대비
    int totalStrSize = intSize + MAX_SIZE + (sign == 1 ? 0 : 1);

    char* resultStr = (char*)malloc(sizeof(char) * totalStrSize + 1);
    resultStr[totalStrSize] = '\0';

    // 반환할 결과 문자 배열 인덱스 순회용
    int resultIdx = 0;

    // 만약 음수라면, 맨 앞에 '-' 를 붙여 음수임을 알린다.
    if(sign == -1) {
        resultStr[resultIdx] = '-';
        resultIdx++;
    }

    // 정수 문자열 순회 포인터 가져오기
    char* intStrPtr = (char*)intStr;
    char* doubleStrPtr = (char*)doubleStr;

    // 정수 문자열을 이용하여 순회
    while(*intStrPtr) {
        char ch = *intStrPtr;
        resultStr[resultIdx++] = ch;
        intStrPtr++;
    }
    // 정수 끝났으면 '.' 넣어서 소수부 준비하기
    resultStr[resultIdx++] = '.';

    // 소수 문자열을 이용하여 순회
    while(*doubleStrPtr) {
        char ch = *doubleStrPtr;
        resultStr[resultIdx++] = ch;
        doubleStrPtr++;
    }

    // 사용이 끝난 문자 배열 할당은 풀어주기
    free(intStr);
    free(doubleStr);

    return resultStr;
}

/**
 * @Param : 토큰화 할 입력 문자 배열
 *  - 앞뒤 빈칸 인식하여 파싱
 * @Return : 토큰 문자 배열의 주소들을 가지고 있는 배열 반환
 *  - 각 토큰의 시작 주소를 배열로 가지고 있음
 */
char** tokenizer(const char* str) {
    int size = 5;
    int currSize = 0;

    // 문자 순회용
    char* strPtr = (char*)str;

    // 현재 마지막에 NULL 처리를 하지 않고, 이 메서드의 마지막에 NULL 처리 한다.
    char** tokens = (char**) malloc(sizeof(char*) * size + 1);

    // 토큰 주소 순회용 포인터
    char** tokensPtr = (char**)tokens;

    int tknStartIdx = 0;
    int currIdx = 0;

    // 입력 문자 마지막까지 진행
    while(*strPtr) {
        // 현재 문자 추출
        char ch = *strPtr;

        // 바로 다음 입력 문자 인덱스로 이동
        strPtr++;

        // 만약 현재 문자가 빈칸에 해당한다면.
        if(isBlank(ch) == 1) {
            // 아직 토큰 시작점도 정해지지 않았다 ==> 토큰 시작 인덱스와 현재 탐색 인덱스가 동일.
            // 따라서, 둘 다 올리고 건너뛴다.
            if(tknStartIdx == currIdx) {
                tknStartIdx++; currIdx++;
                continue;
            }

            // 토큰 시작 위치와 탐색 위치 간의 차이를 계산.
            int tokenSize = currIdx - tknStartIdx;
            // 그 크기만큼 배열을 동적 생성
            char* newToken = (char*) malloc(sizeof(char) * tokenSize + 1);
            // 마지막에 미리 END 알림
            newToken[tokenSize] = '\0';

            // 새로 생성된 토큰 순회용
            char* newTknPtr = newToken;

            // 토큰 시작 인덱스와 현재 탐색 인덱스가 동일하지 않을 때 까지 진행 : 토큰 시작 인덱스가 하나씩 오름
            while(currIdx != tknStartIdx) {
                // 문자열의 토큰 시작 인덱스를 이동시키며, 생성된 토큰에 넣을 거임
                char ch = str[tknStartIdx];
                // 새로 생성된 토큰 인덱스에 문자 삽입
                *newTknPtr = ch;

                newTknPtr++; tknStartIdx++;
            }

            // 새로 만들어진 토큰을 토큰 배열에 넣기
            *tokensPtr = newToken;
            // 토큰 주소 배열 이동하고, 현재 토큰 주소 배열 엘리먼트 개수 표시 증가
            tokensPtr++; currSize++;

            // 토큰화를 끝냈으니, 다음 탐색 인덱스로 이동
            currIdx++;

            // 다시 토큰 시작 인덱스와 탐색 인덱스를 동일시 한다 - 토큰화가 끝났으므로
            tknStartIdx = currIdx;

            // 만약에, 현재 토큰 주소 배열이 꽉 찼다면, 2 배로 길이를 늘려서 다시 할당한다.
            if(currSize == size) {
                // 2 배로 길이를 늘린 토큰 주소 배열 할당
                tokens = (char**)realloc(tokens, sizeof(char*) * (size * 2) + 1);
                // tokensPtr 은 이전 주소를 가르키므로, 곧 토큰을 넣어야 하는 주소로 다시 할당 해 준다.

                size *= 2;

                tokensPtr = (char**) tokens[currSize];
            }
        } else { // 빈 칸이 아니라면, 탐색 인덱스는 진행한다.
            currIdx++;
        }
    }

    // 1 개의 토큰만 존재하거나, 문자열 마지막에 정확히 마지막 토큰이 존재한다면, 실행된다.
    if(tknStartIdx != currIdx) {
        int newTknSize = currIdx - tknStartIdx;
        char* lastToken = (char*)malloc(sizeof(char) * newTknSize + 1);
        lastToken[newTknSize] = '\0';

        // 순회용Ptr
        char* lastTokenPtr = lastToken;

        while(currIdx != tknStartIdx) {
            char ch = *strPtr;
            *lastTokenPtr = ch;
            lastTokenPtr++; strPtr++;
        }

        *tokensPtr = lastToken;
        tokensPtr++;
    }

    *tokensPtr = NULL;

    return tokens;
}

/**
 * @Param : 숫자 문자만을 타겟으로 한다.
 *  - 만약 숫자 문자가 아니라면, -1 을 반환한다.
 * @Return : 0 ~ 9 or -1
 */
int chToInt(char ch) {
    if(ch >= '0' && ch <= '9') {
        return ch - '0';
    } else {
        return -1;
    }
}

/**
 * @Param : 빈 칸에 해당하는 문자인지 확인하려는 문자
 *  - 빈 칸, 혹은 끝('\0') 이면, 1 (True) 반환
 * @Return : 1 or 0 (True or False)
 */
_Bool isBlank(char ch) {
    if(ch == 32) {
        return 1;
    } else if(ch >= 9 && ch <= 13) {
        return 1;
    } else {
        return 0;
    }
}