[코드트리 후기] 완전탐색 알고리즘 극복기

평소 알고리즘 문제를 풀면서 유독 기복이 심하거나 손이 잘 안 가는 파트가 하나씩 있기 마련이다.
나에게는 완전탐색(Brute Force)과 백트래킹(Backtracking)이 바로 그런 고질적인 약점 파트였다.
작년부터 자주 마주쳤던 문제인데 매번 조건 하나씩 빼먹어서 막히곤 했었는데, 이번 기회에 제대로 뿌리 뽑고 가야겠다는 생각이 들어 코드트리로 다시 학습을 했다.

갭체크 진단을 활용한 내 약점 찾기

지난 코드트리 후기에서 했던 나의 현위치를 객체화하여 보여주는 갭체크를 활용하여 나의 약점을 다시 확인했다.

완전탐색에서 매번 좌절한다. 이놈의 간헐적 문제해결능력...

진단결과를 볼때마다 나의 약점과 마주해서 부끄러움을 느낀다.
지난 진단결과를 보면 내 고질적인 약점이었던 완전탐색2와 Backtracking 파트 능력이 부족하다는 점을 정확하게 짚어냈다.

단순히 "어려운 문제를 못 푼다"가 아니라 문제의 모든 가능한 경우를 꼼꼼하게 탐색하는 기본 원리조차 확실하게 잡혀있지 않다는 뼈아픈 분석을 받았다.
기초 개념이 미흡하다 보니 이를 응용해야 하는 완전탐색나 DP 같은 고급 알고리즘으로 넘어갈 때 계속해서 과부하가 걸렸던 것이다. (그래서 요즘 알고리즘 문제 푸는 것에 흥미를 잃어가는 것이었구나!)
문제를 많이 푸는 것보다 모든 경우를 체계적으로 고려하는 사고 방식을 먼저 길러야 한다는 피드백을 얻을 수 있었다.

코드트리를 통한 약점 극복

그동안 백O이나 프OOOO스 같은 타 서비스를 이용할 때는 내가 직접 문제를 골라 풀어야 하거나, 유형별로 정렬되어 있어도 난이도의 격차가 커서 학습 흐름이 끊기는 경우가 많았다. 반면 코드트리는 계단식 성장을 하기에 최적화되어 있었다.

단원별로 개념 및 기본(Warmup) - 연습문제(Challenge) - 실전(Test) 구조를 가지고 있어 무작정 어려운 문제에 부딪히기 전에 개념을 단단히 다져 말그대로 Step by Step으로 성장할 수 있어 좋았다.

특히 약점이었던 완전탐색 파트를 이 루틴대로 차근차근 밟아가다 보니, 문제를 바라보는 풀이 감각이 깨어남을 느꼈다.
이전에는 문제를 보면 구체적인 구현 방법부터 허둥지둥 떠올리느라 예외 케이스를 놓치기 일쑤였는데, 이제는 문제를 구조화하고 모든 경우의 수를 어떻게 체계적으로 쪼개어 탐색할 것인가를 먼저 설계하는 습관이 붙기 시작했다. (Naive -> Specific)

1년 전에는 풀었는데, 다시 풀려니 힘들었던 '상해버린 치즈' 문제

갭체크를 토대로 내가 약한 완전탐색2 파트에서 가장 어려운 문제(Hard)를 일부러 골라 문제를 풀었다.
물체 단위로 완전탐색 파트의 '상해버린 치즈' (Hard 난이도) 문제. (정답률 35%?!?!?!)

저작권 문제 예방차원에서 모자이크~

N명의 사람이 M개의 치즈를 먹은 기록과 아픈 기록이 주어질 때, '상했을 가능성이 있는 치즈'를 찾아내고, 그 치즈를 먹어서 약이 필요한 환자의 '최대 수'를 구해야 한다. 단, 상한 치즈를 먹으면 1초가 지나야 아프기 시작하므로 아픈 시점보다 최소 1초 전에 먹은 치즈만 용의 선상에 오른다.
분명 1년 전에 풀었는데, 다시 풀려고 하니 계속 막혔다. 한번 풀었다고 해서 그냥 넘기는 것이 아니라, 완전히 구조를 이해하고 머리 속으로 응용까지 해야함을 절실히 느꼈다.

나의 코드 (Node.js)

const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split('\n');

// n: 사람 수, m: 치즈 수, d: 섭취기록, s: 질병기록
const [n, m, d, s] = input[0].split(' ').map(Number);

const info1 = [];
for (let i = 1; i <= d; i++) {
    const [p, cheese, t] = input[i].split(' ').map(Number);
    info1.push({ p, cheese, t });
}

const info2 = [];
for (let i = d + 1; i <= d + s; i++) {
    const [p, t] = input[i].split(' ').map(Number);
    info2.push({ p, t });
}

// 1~n번의 사람, 100초의 시간, 각 시간마다 먹은 치즈들을 기록할 3중 배열 선언!
let person = new Array(n+1).fill(0).map( () => Array(101).fill(0).map( () => Array(m+1).fill(0)) );

for(let i=0; i<d; i++) { // 각 사람이 언제 무슨 치즈를 먹었는지 입력
    const [p, cheese, t] = [info1[i].p, info1[i].cheese, info1[i].t];
    let cnt = 0;
    while(1) {
        if(person[p][t][cnt] === 0) {
            person[p][t][cnt] = cheese; 
            break;
        } else cnt++;
    }
}

let susArr = new Array(m+1).fill(0);
for(let i=0; i<s; i++) { // 아픈 사람이 아픈 시점 직전(t-1)까지 먹은 치즈 모두 카운트
    const [p, t] = [info2[i].p, info2[i].t];
    for(let j=1; j<t; j++) {
        for(let k=0; k<person[p][j].length; k++) { 
            susArr[person[p][j][k]] += 1;
        }
    }
}

// 의심되는 치즈 (아픈 사람이 모두 먹은 치즈의 최대 빈도 구하기)
let max = 0;
for(let i=1; i<susArr.length; i++) {
    max = Math.max(max, susArr[i]);
}

let suspect = new Set(); // 상한 것으로 의심되는 치즈 모음
for(let i=1; i<susArr.length; i++) {
    if(susArr[i] === max)
        susapct.add(i);
}

let needPill = 0; // 약이 필요한 환자 수 계산
for(let i=1; i<=n; i++) {
    let personSet = new Set(); // 이제는 언제 먹었느냐보다 "무엇을 먹었느냐"가 중요하므로 Set 활용!
    for(let j=0; j<101; j++) {
        for(let k=0; k<=m; k++)
            personSet.add(person[i][j][k]);
    }
    personSet.delete(0); // 빈 값(0) 제외

    for (const num of suspect) {
        if(personSet.has(num)) {
            needPill++;
            break; // 의심 치즈를 하나라도 먹었다면 약이 필요하므로 바로 break!
        }
    }
}

console.log(needPill);

문제풀이 과정에서 내가 가졌던 고민, 그리고 해결

이 문제를 풀면서 가장 고민했던 부분은 '시간과 사람, 그리고 치즈라는 3가지 조건을 어떻게 꼬이지 않게 관리할 것인가'였다.

내가 선택한 방법은 3중 배열 활용이였다.([사람][시간][치즈])
각 시점마다 어떤 사람이 무슨 치즈를 먹었는지를 직관적으로 기록해두니, 조건 비교가 훨씬 수월해졌다.

 

특히 이 풀이의 핵심 반전 포인트는 후반부 로직에 있다.
처음에는 '언제 먹었는지'라는 타임라인이 중요했지만, 마지막에 약이 필요한 사람을 판별할 때는 '시간과 상관없이 상한 의심 치즈를 한 번이라도 먹었는가'가 핵심이 된다.
이때 3중 배열을 다시 풀어서 중복을 없애기 위해 Set을 적극적으로 활용했다. 시간 축을 과감히 압축하고 personSet.has(num)로 치즈 존재 여부만 빠르게 체크하도록 구현했더니 흐름이 명확해졌고, 드디어 Pass를 받아낼 수 있었다.

 

문제를 해결한 뒤 코드트리에서 제공한 해설을 확인해 보았는데, 내가 구현한 3중 배열 방식 외에도 더 직관적이거나 효율적으로 완전탐색 범위를 제한하는 팁들을 배울 수 있었다.
그리고, 토론 탭에서 다른 유저들이 구현한 다양한 시각의 코드와 피드백을 비교해 보는 과정 역시 내 시야를 한층 넓혀주는 좋은 계기가 되었다.

단순 문제풀이로는 약점을 보완할 수 없다

매번 피해 가고 싶었던 완전탐색이었지만, 코드트리 덕분에 두려움을 지우고 탄탄한 기초 체력을 기를 수 있었다.
나의 약점을 적나라하게 분석해주는 갭체크부터 알고리즘을 완전히 정복하게 해주는 개념-기본문제-심화문제 순의 단계적 문제구성까지, 코딩테스트를 준비하는 나에게 정말 필요한 나침반 같은 학습사이트이다.
앞으로 남은 고난도 알고리즘 유형들도 코드트리와 함께 정복해 나갈 예정이다!

 

3년 만에 돌아온, 코드트리 청약 통장 챌린지 | 코드트리

[↑↑↑ 지금 바로, 코드트리 들어가서 알고리즘 부셔보자 ↑↑↑]

추천코드 : SZ6RTY