내일은 알고리즘

대학교 졸업반이자, 코로나가 처음 시작된 2020년 부터 약 7년 동안 700여개의 문제를 풀었습니다.

취업을 준비하며 미친듯이 문제를 풀때도, 일에 치이고 딴짓에 한눈이 팔려 수개월동안 손도 대지 않던 때도 있었지만...

7년 동안 한 번도 문제를 풀지 않은 해는 없었습니다.

제 첫 제출기록을 찾아봤는데.

무려 C언어로 Hello World 문제를 실패했더라구요? ㅋㅋㅋㅋ

C, C++, Java, Javascript 등을 거쳐 지금은 Python을 주 언어로 사용하고 있는데.

참 추억이기도 하고 씁쓸하기도 하고...

사실 업무적으로나 자기계발로나 일을 한지도 5년째가 되다보니 회의감도 들고 번아웃이 오고 있었는데...

백준을 떠나보내면서 다시 한 번 뛰어볼 마음을 가져봤습니다.

항상 감사했고, 항상 어려웠고, 항상 즐거웠습니다.

Hello world!

Good bye. BOJ

GPT, Gemini, Claud 등 수많은 생성형 AI, LLM이 서비스되고 프로그래밍에 대한 입문이 쉬워지고 있는 게 사실입니다. 

대부분의 LLM들은 저 같은 허접 프로그래머는 물론이고

수십 년 동안 알고리즘과 PS를 즐겨온 세계에서 내로라하는 천재들과 비슷하거나 뛰어넘는 프로그래밍 능력을 뽐내고 있습니다.

GPT가 신드롬을 불러일으키지도 못한 예전부터 주위 사람들은 수도 없이 저에게 말했습니다. 

알고리즘? 코딩테스트? 그런거 다 쓸모 없다. 그런거 없어도 업무 잘한다.

하지만 제 생각은 다릅니다. 

1. 채용자가 할 수 있는 최소한의 검증방법 (Screening)

코딩테스트는 IT 기업들이 수백 수천 명의 지원자들을 걸러낼 수 있는 최소한의 검증방법입니다.

AI, LLM의 발달로 실시간으로 거의 완벽한 번역이 가능해졌습니다.

하지만 여전히 많은 회사들은 채용에서 "최소한의 영어실력"을 요구합니다.

업무에 정말 영어가 필요해서일까요?

복잡한 업무 용어들과 토익, 오픽등의 일상 회화 시험은 전혀 관련이 없습니다.

회사들이 보려는 건 응시자의 영어실력이 아니라 "성실함"과 "준비성"이라고 생각합니다.

한 번 입장과 상황을 바꾸어 생각해 봅시다.

당신은 채용 담당관이고, 스펙이 훌륭한 수천 명의 지원자가 있습니다.

이제 어마어마하게 긴 시간 동안 면접을 봐야 합니다.

그런데, 수개월 전 나간 채용공지에서 요구한 최소한의 어학실력. 

성실하게 학교를 다니고 공부했다면 1~2개월의 벼락치기만으로 어지간하면 습득이 가능한 최소한의 어학자격을 준비하지 않은 지원자가 있다면?

시간을 들여 이력서를 읽고 면접을 볼까요? 아니면 수백 장의 다른 이력서와 함께 쓰레기통에 쳐박을까요.

수백 수천 명의 프로그래머 지망생들이 대학과 교육 프로그램에서 쏟아져 나옵니다.

새로 직원을 뽑으려는 회사들은 어마어마한 시간을 들여 지원자 한 명 한 명을 분석하고 면접보고 검증하거나,

아니면 그냥 코딩테스트를 보게 해서 점수로 기준 미달자들을 걸러내면 됩니다.

2. 내 코딩 실력은 진짜 내 것인가?

LLM 서비스의 발달로 프로그래밍을 아예 모르는 사람들도 아이디어만으로 간단한 어플리케이션의 개발이 가능해졌습니다.

하지만 대부분은 여전히 별 쓸모가 없는 겉보기에만 그럴싸한 버그덩어리일 뿐입니다. 

물론 뛰어난 실력과 통찰을 가지고 엄청난 결과물을 만드는 사람들도 있습니다.

그리고 그런 결과물을 만드려면 LLM을 사용하는 사람도 최소한의 프로그래밍 지식과 코딩 능력을 갖춰야 합니다.

LLM은 물음에 답하고 요청을 수행하지만, 바꿔 말하면 프롬프트를 통해 무언가를 지시해야 결과물을 만듭니다.

두루뭉실하고 멍청한 지시는 엉망인 결과를 만듭니다.

또한 아주 간단하고 사소한 오류를 찾아내지 못해 며칠을 끙끙대며 LLM과 수십번의 질문을 반복할 수도 있습니다.

LLM이 99%의 프로젝트를 완성한다고 해도, 1%의 버그를 찾고 프로젝트의 방향을 지시하는건 자신입니다.

알고리즘과 코딩테스트가 실무에 별로 연관이 없다는 말에 저는 동의합니다. 하지만 완전히 부정할 수도 없습니다.

코딩 테스트를 잘 푸는 개발자가 반드시 좋은 개발자는 아니지만, 

코딩 테스트 문제를 풀며 익히는 자료구조들이, 문제 해결 능력이, 그래프와 아이디어들이 결국엔 좋은 프로그래밍 실력을 만든다고 생각합니다.

심지어 실무와 정말 상관없어 보이는 DP나 그리디마저도 어떤 문제를 맞이했을때 해답이 되진 않을지언정 영감을 주는 뮤즈가 되어줍니다.

3. 나는 특별한가?

위의 내용과 이어서, 코딩테스트를 못 풀어도 훌륭한 개발자들은 많습니다.

실무를 십수년 진행해서 자기 분야와 도메인에 대한 엄청난 지식을 가진 개발자거나, 수십개의 엄청난 논문을 쓴 연구자일 수도 있겠죠.

그런 뛰어난 개발자 분들은 굳이 코딩테스트를 보지 않아도 이미 이름이 알려져 있고, 수많은 실적과 인맥이 있으며 여러 회사에서 러브콜을 보내고 있습니다.

하지만 대부분의 취준생들은 아닙니다.

남들과 비슷한 대학, 비슷한 성적, 비슷한 자격증...

코딩테스트라는 하나의 관문을 포기하는 순간 IT 취업에서 절반 이상의 일자리에 지원을 포기하는것과 마찬가지라고 생각합니다.

4. 난 재밌는데 남들은 재미없다.

대부분의 취준생들은 코딩테스트, PS, 알고리즘 문제 풀이를 재미없어합니다.

지루하고, 쓸모없고, 어렵고...

대부분은 준비를 포기하기도 합니다.

바꿔 말하면 만약 내가 코딩테스트를 즐기고 준비된 지원자라면 남들에게 없는 엄청난 무기를 하나 가지는 겁니다.

저는 취준생 시절에 코딩테스트가 있는 채용전형들이 너무 좋았습니다.

그 중에서도 가장 좋았던건 서류는 비적격자만 걸러지고 99% 통과거나 서류심사가 아예 코딩테스트 이후인 경우였습니다.

주위에서 같이 지원한 수십 명의 지원자들이 다 코딩테스트에서 떨어지면, 누가 봐도 확 줄어든 경쟁률이 보였거든요.

몇 년을 대학을 다녀 스펙을 만들고, 며칠 밤을 새워가며 수천 자의 지원서류를 작성해 놓고서는

코딩테스트를 준비하지 않아서 고작 2시간의 시험 내내 아무 코드도 작성하지 못하고 떨어지는 사람들을 수도 없이 봤습니다.

여러분들은 어떠신가요?

채용 전형에 코딩테스트가 포함되면 입가에 미소가 지어지시나요. 

아니면 짜증을 내시나요?

https://school.programmers.co.kr/learn/courses/30/lessons/250137

문제에서 시키는대로 구현하면 되는 시뮬레이션 문제입니다. 

몬스터의 마지막 공격이 있을때까지 데미지를 계산하며 체력을 회복합니다. 이때 붕대를 x초 감게 되면 추가적으로 체력을 회복하는것을 신경써야 합니다. 구현에는 다음 과정들이 필요합니다.

1. 시간을 늘려가며 체크해 공격이 들어왔다면 데미지 계산, 체력이 0 이하라면 -1을 return

2. 공격이 들어오지 않았다면 붕대를 1초 더 감고 체력을 회복

2-1. 붕대를 x초째 감았다면 체력을 추가 회복, 붕대를 감은 연속 횟수를 0으로 초기화

def solution(bandage, health, attacks):
    h, idx, b, e = health, 0, 0, attacks[-1][0]
    
    for i in range(e + 1):
        if i == attacks[idx][0]:
            h -= attacks[idx][1]
            b = 0
            idx += 1
        else:
            b += 1
            h = min(health, h + bandage[1])
        
            if b == bandage[0]:
                b = 0
                h = min(health, h + bandage[2])
        
        if h <= 0:
            return -1
    
    return h

https://school.programmers.co.kr/learn/courses/30/lessons/135808

간단한 그리디 유형의 문제입니다. 사과를 m개씩 묶어서 팔아야 하는데 m개 중 `가장 낮은 점수 x m`의 가격을 받을 수 있습니다. 간단하게 사과를 내림차순으로 정렬하고 앞에서 부터(점수가 높은 사과부터) m 개씩 끊어가며 판매하면 됩니다. 

예시를 통해 검증을 해보겠습니다. 예시 1번에서 사과의 점수가 [1, 2, 3, 1, 2, 3]이고 4개씩 묶어 팔아야 한다고 합니다. 이를 내림차순으로 정렬하면 [3, 3, 2, 2, 1, 1]이 되고 얻는 가격은 앞에서부터 4개를 선택해 얻은 [3, 3, 2, 2]에서 가장 낮은 점수인 2 x 4 = 8입니다. 

사과 n개가 존재하고 이를 내림차순으로 정렬한 값이 [A1, A2, A3, ...Am, ... An]이라고 해 봅시다. 내림차순으로 정렬했기 때문에 각 사과들의 가격은 A1 >= A2 >= A3 ...>= Am... >= An의 대소를 가집니다. 앞에서부터 m개의 사과를 선택했을 때 얻는 금액은 `Am x m` 입니다. Am보다 가격이 작거나 같은 어떤 사과 Ax (m < x <= n)를 선택하면 얻는 금액은 `Ax x m`이 됩니다. Am >= Ax이므로 m을 곱해봐야 대소관계가 변하지 않음을 알 수 있습니다. 따라서 매 순간마다 가능한 사과들 중에 가격이 큰 m개를 순서대로 고르는것이 가격합을 가장 크게 만드는 방법입니다.

def solution(k, m, score):
    score.sort(key = lambda x : -x)
    
    answer, i = 0, m - 1
    
    while i < len(score):
        answer += score[i] * m
        i += m
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/161989

문제 밑부분에 레벨이 2에서 1로 조정되었다고 적혀있네요. 아마 그리디 문제로 올라왔다가 너무 쉬워서 레벨이 조정된 것 같습니다. 

실제로 풀이도 간단합니다. 벽을 칠해야 하는 부분을 만나면 그 부분을 왼쪽 끝으로 놓고 최대한 칠해줍니다. 이 값을 기억해 뒀다가 다음에 칠해야 하는 부분이 칠한 부분 밖이라면 칠한 횟수를 늘려주고 같은 행동을 반복합니다.

코드도 간단하네요.

def solution(n, m, section):
    answer = 0
    e = 0
    for s in section:
        if s > e:
            answer += 1
            e = s + m - 1
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/161990

간단한 구현문제입니다.

바탕화면의 모든 파일을 한 번에 선택하기 위해서는 좌상단, 우하단의 점들 안에 모든 파일의 좌표가 존재해야합니다. 최소값 좌표와 최댓값 좌표 두개를 미리 준비해놓고 #이 존재하는 좌표마다 각각의 x, y 혹은 r, c에 대해 최소 최대를 갱신해주면 됩니다.

변수를 선언할 때 초기값이 입력사이즈 안에 들어가지 않도록 주의해주세요.

def solution(wallpaper):
    lr, lc, rr, rc = 100, 100, -1, -1
    
    for i in range(len(wallpaper)):
        for j in range(len(wallpaper[0])):
            if wallpaper[i][j] == '#':
                lr = min(lr, i)
                lc = min(lc, j)
                rr = max(rr, i + 1)
                rc = max(rc, j + 1)
    
    return [lr, lc, rr, rc]

https://school.programmers.co.kr/learn/courses/30/lessons/172928

레벨 1 치고 구현 난이도가 약간 있는 시뮬레이션 문제입니다. 이 문제에서 우리가 구현할 기능들을 추려보자면 다음과 같습니다.

1. 산책을 시작하는 좌표를 찾기

2. 입력으로 주어진 방향과 이동 거리를 분석

3. 이동이 가능한지(공원 밖을 나가지 않는지, 이동 경로에 장애물이 있는지) 판단하기

4. 이동이 가능하다면 이동시키기

그대로 구현을 하고 주어진 입력대로 모두 이동한 후에 최종 좌표를 return 하면 됩니다.

def solution(park, routes):
    delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    dset = {"N":0, "S":1, "W":2, "E":3}
    r, c, n, m = 0, 0, len(park), len(park[0])
    
    def cango(r, c, d, w):
        nonlocal n, m
        
        for i in range(w):
            r += delta[d][0]
            c += delta[d][1]
            
            if r < 0 or r >= n or c < 0 or c >= m or park[r][c] == 'X':
                return [-1, -1]
            
        return [r, c]
    
    for i in range(n):
        for j in range(m):
            if park[i][j] == 'S':
                r = i
                c = j
    
    for route in routes:
        d, w = route.split(' ')
        d = dset[d]
        w = int(w)
        
        res = cango(r, c, d, w)
        if res[0] != -1:
            r, c = res[0], res[1]
                
    return [r, c]

https://school.programmers.co.kr/learn/courses/30/lessons/136798

약수를 구하는 아이디어만 떠올리면 쉽게 풀리는 구현 문제입니다.

간단히 1부터 n까지 수가 가지는 약수를 카운트 해주고, 주어진 limit보다 큰 경우 limit로 갱신해서 누적합을 만들어 주면 됩니다. 단, 약수를 구할 때는 시간초과를 고려해야합니다. 

n의 약수를 구할 때 1부터 n까지 모든 자연수 x에 대해 1부터 x/2까지 일일히 나누어 떨어지는치를 체크한다면 이 문제의 n이 10만이기때문에 10만 x 5만 = 50억이라는 어마어마한 연산이 필요합니다.

약수를 나누어 구하는 대신 1부터 n까지 모든 자연수 x에 대해 자신의 배수들을 모두 찾으면 거꾸로 그 배수는 자신의 약수가 몇개인지를 알 수 있습니다. 이 경우엔 10만개의 수에 대해 10만 ÷ x번 연산을 하게 되고 이 값은 대략 1152620이라고 합니다. (해당 연산이 조화급수로 챗 gpt의 도움을 빌렸습니다.) 위에서 필요했던 50억번의 연산에 비해 0.02%에 불과한 매우 작은 연산입니다.

간단히 작성한 코드는 아래와 같습니다. 1 ... n으로 x를 키워가며 x의 배수들마다 1씩 더해주면 그 수들은 x로 나누어 떨어지는 수입니다. 

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i
    
    for i in range(1, number + 1):
        if arr[i] <= limit:
            answer += arr[i]
        else:
            answer += power
            
    return answer

리스트 컴프리헨션을 이용해 코드를 좀 더 줄일 수도 있습니다.

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i

    return sum([arr[i] if arr[i] <= limit else power for i in range(1, number + 1)])