[WIL - week5] 컴퓨팅 사고로의 전환 (DP, 그리디)

이지섭·2026년 4월 2일
크래프톤 정글

크래프톤 정글 SW/AI랩 12기

목록 보기
5/10
post-thumbnail

핵심 역량 목표

목표: basic 문제와 난이도 하 문제의 풀이를 이해하고 내 것으로 만들기.

  • 협업: 동료 학습을 통해서 개념을 내 것으로 만들고 이해할 수 있다.
  • 태도: 다른 사람에게 설명할 수 있을 정도의 수준으로 공부하기 위해서 주도적으로 학습한다.

학습 포인트

  • 동료 학습(파인만 학습법): 내가 배우고 이해한 내용을 동료에게 설명하고 이해시킴으로써 내가 정말 이해한 것이 맞는지 확인한다.

구체적인 목표 및 접근 방법

  • 목표를 정량화하여 분할해 놓는 것은 의미가 없다고 생각하여 내가 해결할 문제들의 범위만 설정했다.
    - basic 4문제(그리디 2문제, DP 2문제), 난이도 하 4문제(그리디 2문제, DP 2문제)

문제와 해결 과정

금요일

  • 피보나치 수열 설명: https://velog.io/@soldbone/TIL-week5-피보나치-수열-w-Dynamic-Programming
    피보나치 수열의 기본적인 재귀 구현부터 단순 재귀 구현의 문제점 분석, DP를 통한 문제 해결, 이외의 피보나치 수열 알고리즘 개선법 등을 정리하였다. 팀원들에게는 해당 내용을 기반으로 화이트보드에서 끊지 않고 한번에 설명했다. 확실히 블로그에 정리해놓는 것이 공부에 많은 도움이 된다는 것을 느꼈다. 물론, 시간이 많이 걸리는 일이기 때문에 매번 이런 식으로 정리를 하지는 못하겠지만 정리할 수 있는 만큼만이라도 해두면 좋을 것 같다는 생각을 했다. 사실 가장 중요한 것은 정리하면서 내가 스스로 이해를 하는 과정인 것 같다. 동료 학습의 맥락과도 일맥상통한다.

토요일

다음의 문제들을 풀었다. 생각보다 그렇게 어렵지 않아서 빠르게 풀고 넘어갔다. 이때부터 약간 동료 학습이 느슨해져서 아쉬웠다. 어쨌거나 문제를 푼 것과 설명한 것 사이의 시간 간격은 있었지만 푼 문제들은 모두 화이트보드에서 다른 팀원들에게 설명했다. 동시에, 여전히 팀원 간의 소통에 있어서 내가 너무 소극적이라는 것을 느꼈다. 다들 왜 서로 설명을 안 해주는지, 내가 설명해주면 들을 생각이 있는지 먼저 나서서 소통을 하려고 했어야 한다.

일요일

토요일 저녁에 교육생끼리 약속이 잡혀서 자리한 뒤 늦게 하루를 마쳤다. 일요일에 오전 11시 30분쯤 일어나서 씻고 준비했는데 다같이 모여서 밥먹기로 한 시간에 늦어서 약간 계획이 틀어졌다. 이게 딱히 문제는 아니었다. 간식을 사러 갈 생각이었기 때문이다.

지금까지 같은 교육장의 한 동료가 간식을 많이 돌렸었는데 나도 버터떡을 사서 교육생들에게 나눠줄 겸, 다른 동료에게 두쫀쿠 사주기로 한 것 사러 갈 겸 밖으로 나갔어야 했다.

덕분에 미뤄뒀던 러닝을 할 핑계도 생겨 오랜만에 뛰었고, 버터떡도 다들 맛있게 먹어주었고, 두쫀쿠 받은 동료도 좋아해줘서 만족스러웠다. 부정적인 감정이 아예 들지 않았다면 거짓말이겠지만 그냥 넘어갈 만한 수준이었고 나름 행복한 하루였다. 어차피 이번 주에는 많은 문제를 푸는 것이 목표가 아니었다. 단지, 수면 시간을 확보하지 못한 것 정도만 조금 아쉽다. 이외에는 스트레스 관리를 위해 필요한 하루였다고 생각한다.

커밋 기록상에는 아무것도 없지만 화이트보드에 백지부터 쓰는 방식으로 복습하면서 팀원들에게 설명할 준비를 했다.

월요일

다음 문제들을 풀었다.

basic 문제인 회의실 배정의 경우 내가 직접 풀이를 생각해서 풀지 못해 아쉬웠다. 주석으로 이미 필요한 내용이 다 적혀 있었다. 백지 복습 시에도 접근 방법을 처음부터 찾고 있다고 가정하고 스스로 떠올려야 하는데 이걸 하기가 굉장히 어려웠다.
이외에 동전0 문제의 경우에는 basic의 거스름돈 문제와 동일해서 큰 어려움 없이 풀었다.

가장 큰 보람을 느꼈던 순간은 코어타임을 하면서 Climbing Stairs, House Robber 문제를 모두 풀었을 때이다. 두 문제 모두 30분 안에 해결하였고 코드를 짜는데 막힘이 없었다. 물론, 문제 자체가 점화식을 쉽게 찾을 수 있는 형태이기도 했다. 특히, Climbing Stairs 문제의 경우에는 basic의 계단 오르기 문제와 완전히 동일했기 때문에 쉽게 풀 수 있었다.

그러나 생각해보면 나는 이전 알고리즘 주차에서는 정렬을 배워도 코어 타임 시간에 스스로 작성할 수 없었다. 그런데 이번에는 동료 학습을 목적으로 했기 때문에 문제와 문제에 대한 접근 방식, 문제를 코드로 해결하기 위해 구현하는 과정을 내 것으로 만들 수 있었다. 그렇기 때문에 Climbing Stairs 문제도 풀 수 있었다고 생각한다.

가장 뿌듯한 부분은 어려울 것이라고 생각했던 House Robber를 나의 힘만으로 쉽게 풀어냈다는 것이었다. 경우의 수를 나눠 점화식을 도출하는 과정 자체를 혼자서 해냈다는 것이 매우 뿌듯했다. 코드 구현은 점화식을 피보나치 수에서 했던 것처럼 DP 패턴으로 그대로 옮기기만 하면 됐기 때문에 어렵지 않았다.

'동료 학습(파인만 학습법)이 확실히 효과가 있는 건가?'하는 생각이 들었던 하루였다.

# https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=top-interview-150
"""
심지어 if문을 사용하지 않는 Solution 코드를 먼저 구현했다.
"""
class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        n = len(nums)
        dp = [0] * (n + 1)
        dp[1] = nums[0]
        for i in range(2, n + 1):
            dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])

        return dp[n]

class Solution2:
    def rob(self, nums: List[int]) -> int:
        # dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        n = len(nums)
        if n == 1:
            return nums[0]

        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(dp[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])

        return dp[n-1]

화요일

다음 문제를 풀었다.

정글을 진행하면서 지금까지 전공 시간에 배운 기억이 있는 문제들을 회피해 왔다. N-Queen, 외판원 순회, 배낭 등이 그 대표적인 예시이다. 주변 동료들이 아무렇지 않게 그러한 문제들에 도전하는 것을 보면서 생각을 고쳐 먹게 되었다. '전공 시간에도 어려웠는데 지금 난 못해, 나중에 정글 끝나고 다시 보자.' 이런 말도 안 되는 생각들에서 벗어나서 일단 한번 해보기로 했다.

화요일이 되기 전까지 어쨌든 자기 효능감과 성취감이 조금 쌓인 상태였기 때문에 가장 풀고 싶은 3가지 문제(점프, 배낭, LCS) 중 배낭에 도전해 보기로 하였다. 문제를 풀기 시작한 것은 월요일 저녁이었다.

풀기에 앞서 AI에게 힌트만 받고 계속해서 본인의 힘으로 풀어보는 공부 방식에 대해 동료 분께 들었다. 다른 분께서 그렇게 하고 있고 본인에게는 매우 좋았다고 한다. 몰입이 풀릴 때까지(너무 쉽거나, 너무 어려워서 집중이 되지 않을 때까지) 혼자 힘으로 풀고 몰입이 풀리면 AI에게 힌트를 받고 다시 혼자 힘으로 푸는 것을 계속 반복하는 방법이었다. 나도 이 방법으로 접근했다.

나는 이 문제의 dp 점화식을 도출할 때 애초에 2차원 배열을 활용하는 방식을 생각해낼 수가 없었다. 그래서 1차원 배열로 dp를 정의해서 풀었다. 물론 이 문제를 풀기 이전부터 배낭 문제를 1차원 배열로 풀 수 있다는 정보를 들었기 때문에 온전히 내 아이디어라고 할 수는 없다. 시간이 부족하여 하지 못했는데 원래 정석적인 2차원 배열 풀이는 어떻게 되는지 알아봐도 좋을 것 같다.

이후에는 dp 점화식은 도출했지만 중복이 들어가는 경우를 어떻게 막을 수 있을지 모르겠어서 AI의 도움을 받고 풀어냈다. 굉장히 뿌듯했다. 기록하다보니 이번 주는 기존에 가지고 있던 '문제를 많이 풀어야 한다는 강박'에서 벗어나서 나 스스로에게 휴식을 주고 공부도 제대로 할 수 있었던 한 주였다.

"""
이 코드는 "1차원 배열로 풀 수 있다"라고 알려 주신 동료분의 풀이를 그대로 가져와 최적화한 버전이다.
"""
N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0] * (K + 1)

for weight, value in items:
    for w in range(K, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)
print(dp[K])

수요 코딩회

정글에 들어와서 가장 재밌고 뿌듯한 순간이었다. 정글에 들어오길 잘했다고 느꼈다.

이번 수요 코딩회 주제는 '미니 리액트 만들기'였다. 지난 주차 수요 코딩회에 구현한 vDOM, diff 알고리즘, patch 위에 Component, State, Hook을 구현하면 되는 바이브코딩 프로젝트였다.

처음 회의를 할 때 어떻게 이 수요 코딩회에 어떻게 임할 것인지 토의를 했다. 우리 조에서 나온 의견은 사실 구현은 중요하지 않다는 것이었다. 결국 수요 코딩회를 하더라도 우리의 목적은 주어진 주제에 대해서 우리의 것으로 만들고 이해를 하는 것이다. 그런데 코드 레벨에서의 이해 없이 개념만 공부하거나 기능 단위로 분업해서 git branch를 만들어 작업하고 병합하는 단순한 협업 방식은 의미가 없다고 봤다.

그래서 우리는 이번 수요 코딩회의 목표를 '차근차근 진행하되 진행한 부분에 대해서는 코드 레벨에서 이해하고 넘어가는 것. 그리고 100%가 아니라 70%를 해내는 것을 목표로 하는 것.'으로 설정했다.

AI도 하나의 컴퓨터에서만 계속 사용했다. 우리가 한 일이라고는 AI가 생성한 코드를 하나의 화면으로 3명이 함께 보면서 코드가 어떻게 동작하는지 이해하고 실시간으로 토론하는 일이었다. 어떻게 보면 페어 프로그래밍 방식과 닮아 있다고 볼 수도 있다. 조금 더 정확히 말하면 단체로 하는 코드 리뷰에 가깝긴 했다.

이 과정에서 지금까지 코드 분석을 하지 않은 수요 코딩회에 비해 엄청나게 많은 효능감과 성취감을 느꼈다. 코드 한 줄 한 줄의 동작을 이해할 때나, 각각의 부분들이 어떻게 유기적으로 연결되어서 쓰이는지 이해할 때마다 많은 성취감을 느꼈다.

그래서 지난 주차에 했어야 했던 virtual DOM, diff 알고리즘, patch부터 다시 진행했다. 이 과정까지가 정말 재밌는 부분이었다. 이후 저녁을 먹고 돌아오니 state 이후 부분부터는 어려워지기 시작했다. 다들 말수가 적어지고 분위기가 가라앉기 시작했다. 하지만 팀원들은 끝까지 포기하지 않고 함께 이해하려고 노력해줬다. 감사하게도, 덕분에 끝까지 잘 마칠 수 있었다.

인상 깊었던 일도 있었다. 한 팀원분은 이미 React를 사용해보셔서 본인이 알고 있는 동작 방식과 내가 코드를 보며 실시간으로 이해한 내용이 일치되지 않는 경우가 종종 있었다. 그럴 때마다 본인의 의견만 고집하는 것이 아니라, React에 대해 잘 모르는 내 의견도 들어보고 결국 내 의견이 맞다고 인정해주시는 모습을 보면서 많이 배웠다. 그건 사실 굉장히 어려운 일이라는 걸 알고 있기 때문이다. 만약 내가 그 상황이었다면 절대로 그렇게 쉽게 인정하지 못했을 거고 내가 잘못 알고 있었던 이유가 있다는 듯이 변명하기에 급급했을 거다. 결국 나의 성격과 인성, 소통방식이 그 팀원분만큼 성숙해지려면 많이 보고 배워야겠다는 생각을 했다.

한 명의 개발자이기 이전에, 한 명의 사람으로서도 아직 부족하다는 걸 느낀 순간이었다.

핵심 역량 목표 달성률 평가

(척도: 매우 불만족, 불만족, 보통, 만족, 매우 만족)
만족도 평가: 매우 만족

목표: basic 문제와 난이도 하 문제의 풀이를 이해하고 내 것으로 만들기.

  • 협업: 동료 학습을 통해서 개념을 내 것으로 만들고 이해할 수 있다.
  • 태도: 다른 사람에게 설명할 수 있을 정도의 수준으로 공부하기 위해서 주도적으로 학습한다.

느낀 점 요약

  • 확실히 블로그에 정리해 놓는 것이 공부에 많은 도움이 된다.
  • 사실 가장 중요한 것은 정리하면서 내가 스스로 이해를 하는 과정이다.
  • 팀원들이 내가 생각한 것과 다르게 행동하면 내가 먼저 소통하려고 해야 한다.
  • 스트레스 관리를 위한 하루도 가끔 필요하다.
  • 동료 학습을 목적으로 했기 때문에 처음보는 문제도 스스로 풀 수 있었던 것 같다.
  • 동료들이 아무렇지 않게 도전하는 것을 보면서 일단 한번 해보기로 했다. 일단 한번 해보는 것은 도움이 된다.
  • '문제를 많이 풀어야 한다는 강박'에서 벗어나면 부정적인 감정을 줄일 수 있고 공부도 제대로 할 수 있다.
  • 수요 코딩회에서 코드의 동작 방식을 이해할 때 단계별로 접근하여 유기적인 구조를 분석하는 것은 큰 성취감과 자기 효능감을 준다.
  • 나의 성격과 인성, 소통방식이 성숙해지려면 많이 보고 배워야겠다.

풀지 못한 문제

시도해볼 것(TRY)

동료 학습 혹은 블로그 정리 등의 수단을 통해 '내가 스스로 이해를 하는 시간'을 만들자.

소통이 필요한 경우에 망설이지 말자.

그냥 해보자. 용기가 필요하다면 기꺼이 도전하는 주변 동료들을 보자.

강박을 버리자. 정말 중요한 것은 내가 얻어가는 것, 이해하는 것이 있는지이다.

상황이 허락하는 한, 수요 코딩회처럼 복잡한 시스템의 코드를 여러 명의 사람이 토론하며 단계별로 이해하는 과정을 가져 보자.

개인적인 짧은 회고

개인적으로 좀 양가적인 감정이 드는 일주일이었다. 다행히도 부정적인 감정은 많이 가라 앉았다. 고민이 있었던 부분은 다음이다.

  • 내가 충분히 난이도 중 문제까지 풀 수 있음에도 다른 동료분들 핑계로 과제 양을 적게 목표한 것은 아닌가?
  • 동료 학습이라고는 하지만 처음으로 풀었던 피보나치 수열 문제를 제외하면 실질적인 동료 학습은 없었다. 어떤 수준으로 동료 학습을 해야 하는가?

두 가지 모두 합당한 고민이었다.
첫번째 고민과 관련해서는 그래서 월요일 저녁부터 평범한 배낭 문제 하나를 진득히 잡고 풀기 시작했던 것이었다.

그리고 두 번째 고민과 관련해서는 내가 또다른 강박을 가진 것은 아닌지 돌아보았다. 첫 기준이 피보나치 수열을 정리했던 블로그 글이다 보니 강박을 가졌던 것이 맞는 것 같다.

사실 basic 문제가 지나가면 그 이후부터는 자신의 문제 접근 방식과 코드를 화이트보드에서 설명할 수 있는 수준이면 충분한 것이었다. DP, 그리디 알고리즘은 이론이 단순한 편이기 때문이다. 이후는 문제를 다양하게 풀면서 알아가야 한다.

이번 주차는 지난 5주 중에 가장 만족했다고 말할 수 있는 주차였다.

그리고 정글에 들어와서 얻을 수 있는 것을 다시 생각해보았다. 밤에 산책을 하면서 혼자 생각을 많이 했다. 지금으로서는 일단 사람들을 얻는 것이 정글에서 내가 얻을 수 있는 것 중 하나라고 생각이 들었다.

재밌고 든든한 형들이 생겼고, 친해지고 싶은 친구가 생겼고, 아껴주고 싶은 동생이 생겼다. 이것만으로도 충분히 복을 받은 것이 아닌가 하는 생각이 들었다. 적어도 지금으로서, 정글 안에서는 인간 관계는 이미 얻었고 행복하다.

일단 하나를 찾았으니 또 내가 얻을 수 있는 것은 무엇일지 고민해봐야겠다.


profile
이지섭
이지섭입니다.
이전 포스트

[WIL - week4] 컴퓨팅 사고로의 전환 (알고리즘; 그래프, DFS/BFS)

다음 포스트

[WIL - week6] 탐험 준비(C언어 - 자료구조)

0개의 댓글