답수실Log | 220327 | Core dumped??

 

요즘 정신이 없다. 언젠가부터 턱에 무언가가 나기 시작하더니 이제 눈에 보일 정도로 튀어나오기 시작했다.

비대칭이 심하게 보일 정도로 턱에 혹 같은 것이 자라고 있음 ㅠ...

 

아무래도 공부하랴 취준하랴 바쁜데 매번 거울볼 때마다 거슬리는 저 턱 때문에 스트레스도 이만저만이 아니다 ㅠㅠ 그래서 겨우 대학병원을 예약하고 CT촬영까지 했다. 원래 계획대로라면 내일(28일 월) CT 결과를 보며 턱에 자라는 저게 뭔지 진료를 받아야 하는데...

 

하필 이번주부터 코로나 확진 ㅠㅠㅠㅠ 다음주 목요일까제 자가격리를 해야 하기 때문에 진료를 미룰 수밖에 없었는데 5월까지 예약이 밀려버렸다 스트뤠쓰.....!

 

코로나 때문에 어차피 갇혀있을거 알고리즘 연습부터 하자는 마인드로 두통과 몸살을 장착한 체로 문제를 풀었다.

 

오늘 풀었던 문제는 프로그래머스(큰 수 만들기)

코딩테스트 연습 - 큰 수 만들기

 

 

내가 풀었던 코드는 다음과 같았다.

const combinations = (arr, num) => {
    const result = [];

    if (num === 1) return arr.map(v => [v]);

    arr.forEach((fixed, index, origin) => {
        const rest = origin.slice(index+1);
        const reCombinations = combinations(rest, num-1);
        const attached = reCombinations.map(combi => [fixed, ...combi]);

        result.push(...attached);
    });

    return result;
}

const pickMax = (arr) => {
    let result = arr.map(num => num.join(""));
    return Math.max(...result);
}

function solution(number, k) {
    const numArr = combinations([...number], number.length - k);
    const max = pickMax(numArr);

    return String(max);
}

 

주어진 수 number의 길이에서 k를 뺀 요소를 조합으로 돌려서 가장 큰 수를 반환하여 해결하는 방식이었다. 결과는

 

런타임 에러와 aborted(core dumped) ...

 

여러 테스트케이스를 돌려봤을 때, 내 코드는 정상적으로 작동했지만,

solution("657476173782111262898568268434341", 11)

같이 연산이 커지는 케이스를 돌리니 

RangeError: Maximum call stack size exceeded

콜스택이 가득 차는 에러가 뜬다. 즉 지금 내 코드는 시간 복잡도나 공간 복잡도 측면에서 봤을 때 매우 비효율적이라는 것이고, 성능구데기 코드라는 것이다.

 

그래서 더 간단하게 스택을 활용하여 문제를 풀었다.

function solution(number, k) {
    let stack = [];

    for (const num of number) {
        
        while (k > 0 && stack[stack.length-1] < num) {
            stack.pop();
            k--;
        }

        stack.push(num);
    }

    stack.splice(stack.length-k, k);    // k가 남았다는 말은 뒤의 숫자가 앞의 숫자보다 작다는 의미

    return stack.join("");
}

 

결과:

 

통과된 테스트들만 비교해봐도 두 번째 해결 방법이 훨씬 빠르다.

 

첫 번째로 해결한 방식은 모든 경우의 수를 찾는 완전탐색 방식이고 조합하는 함수인 combinations()를 재귀로 돌리면서 연산의 수가 매우 방대하게 커지게 되므로 비효율적이었고, 그래서 저런 런타임에러라던가 core dumped 같은 에러가 나왔던 것이다.

 

 

그래서, core dumped가 뭔디요???

 

core dump?

위키백과 - 코어 덤프

코어 덤프 - 위키백과, 우리 모두의 백과사전

 

코어 덤프(core dump)는 일반적으로 프로그램이 비상적으로 종료될 때 생성되는, 메모리 상태가 기록된 데이터들이다. 많은 OS들은 프로그램에 치명적인 오류가 발생하면 자동으로 코어 덤프를 실행시킨다고 한다. 즉, 첫 번째로 작성했던 코드의 경우 콜스택의 범위를 넘칠만큼 많은 양의 명령어들이 쌓이다보니 엔진의 과부하로 프로그램이 종료되었다! 라고 볼 수 있을 것 같다.(더 정확한 개념에 대해서 알고 계신 분 계시면 친절한 피드백 감사하겠습니다!!)

 

Anyway... 알고리즘에 더 많은 시간을 투자하고, 그 밀도를 지금보다는 두 배로 진하게 하여 알고리즘 실력을 빨리 향상시키도록 노력해야겠다. 그러면서 프로젝트도 마무리하고, TS도 언넝 공부하고!!!