정보 이론 심층 해설과 동전 교환 문제 풀이

기술을 공부할 때 많은 사람들은 ‘수학적 기초’와 ‘알고리즘 문제 풀이’를 서로 평행한 두 영역처럼 받아들인다. 정보 이론을 배울 때는 개념이 지나치게 추상적이고 공식이 이론 중심으로 느껴지고, 동적 계획법 문제를 풀 때는 상태 전이식과 코드 템플릿만 붙잡은 채 패턴만 외우면 된다고 생각하기 쉽다. PixelBank 학습 트랙을 바탕으로 한 이 글의 가치도 바로 이 간격을 줄이려는 데 있다. 한편으로는 정보 이론의 핵심 질문, 즉 정보는 어떻게 측정되는지, 불확실성은 어떻게 다뤄야 하는지, 제약이 있을 때 어떻게 더 효율적으로 표현할 수 있는지를 다시 짚고, 다른 한편으로는 대표적인 알고리즘 문제인 동전 교환을 통해 이론적 사고가 실제 알고리즘 설계를 얼마나 또렷하게 만들어 주는지 보여준다. 단순히 두 주제를 억지로 이어 붙이는 것이 아니라, 추상적인 사고 틀이 문제 해결의 구조를 어떻게 비추는지를 설명하는 방식이다.

정보 이론이 중요한 이유는 통신, 압축, 부호화, 머신러닝 같은 분야에서 오래된 역사를 갖고 있기 때문만은 아니다. 더 본질적으로는 복잡한 문제를 다루는 기본 시각을 제공하기 때문이다. 가능한 경우의 수가 많을 때, 우리는 어떤 방식으로 정보를 가장 간결하고 안정적이며 비용 효율적으로 조직할 수 있을까? 샤논의 엔트로피를 이야기하든, 더 넓은 의미의 불확실성 측정을 이야기하든, 결국 질문은 같다. 어떤 시스템이 여러 상태를 가질 수 있을 때 그것을 충분히 설명하려면 얼마나 많은 정보가 필요한가, 그리고 그 과정에서 불필요하게 같은 설명을 반복하지 않으려면 어떻게 해야 하는가 하는 점이다.

이 시각을 알고리즘 문제에 옮겨 오면, 많은 고전 문제가 훨씬 자연스럽게 이해된다. 알고리즘은 단순히 입력을 출력으로 바꾸는 절차가 아니라 정보 처리 과정이기도 하다. 좋은 알고리즘은 가능한 한 중복 계산을 줄이고, 이미 얻은 정보를 보존하며, 이후의 결정을 기존 결과 위에 세워 전체 풀이 비용을 낮춘다. 동적 계획법은 이런 사고의 가장 전형적인 형태다. 같은 부분 문제가 반복해서 등장한다면 매번 처음부터 다시 계산할 이유가 없고, 큰 문제의 최적해가 작은 문제들의 최적해를 이용해 구성될 수 있다면 그 문제에는 재사용 가능한 구조가 있다는 뜻이다.

동전 교환 문제가 고전으로 자리 잡은 것도 바로 이 생각을 입문 수준에서 잘 보여 주기 때문이다. 보통 문제는 이렇다. 여러 종류의 동전 단위와 목표 금액이 주어졌을 때, 그 금액을 만들기 위해 필요한 동전의 최소 개수를 구하라. 만약 만들 수 없다면 불가능하다는 표시를 반환하라. 처음 보면 단순한 조합 문제처럼 보이기 때문에 많은 초심자들은 먼저 탐욕법을 떠올린다. 즉, 매 단계마다 가장 큰 동전을 우선 선택해 목표값에 빠르게 다가가려는 방식이다. 하지만 동전 단위 구성이 조금만 복잡해져도 이런 직관은 쉽게 실패한다. 이유는 간단하다. 부분적으로 가장 좋아 보이는 선택이 전체적으로도 최선이라는 보장은 없기 때문이다.

바로 이 지점에서 정보 이론적 시각이 개입할 수 있다. 동전 교환에서 진짜 중요한 것은 특정 단계에서 어떤 동전을 골랐느냐만이 아니다. 현재 남아 있는 금액 상태에서 우리가 이미 알고 있는 정보가 무엇이고, 다음 결정을 위해 추가로 필요한 정보가 무엇인지를 파악하는 일이 더 중요하다. 각 금액을 하나의 상태로 본다면, 목표 금액을 푸는 과정은 더 작은 금액 상태에 담긴 정보를 계속 활용해 더 큰 금액 상태의 정보를 구성해 가는 과정이 된다. 여기서 정보란 추상적인 구호가 아니다. 금액 i를 만드는 데 필요한 최소 동전 수, 그 금액이 도달 가능한지 여부, 가능하다면 어떤 이전 상태에서 전이되었는지 같은 아주 구체적인 내용이다.

이 관점에서 보면 동적 계획법은 외워야 하는 템플릿이 아니라 문제의 정보 구조를 압축해서 표현한 방식이다. 만약 이 문제를 완전 탐색으로 풀면 중복 경로가 대량으로 발생한다. 서로 다른 선택 순서나 조합을 따라가더라도 결국 같은 잔여 금액 상태가 계속 다시 등장하기 때문이다. 목표 금액이 충분히 크면 여러 재귀 분기가 결국 똑같이 ‘남은 금액 7’이나 ‘남은 금액 11’ 같은 중간 상태로 수렴하는 일이 흔하다. 그런데 그런 상태를 만날 때마다 매번 다시 계산한다면, 시스템은 사실상 동일한 정보를 반복 처리하는 셈이 되고 효율은 빠르게 나빠질 수밖에 없다.

동적 계획법이 하는 일은 바로 이런 중복 정보를 하나로 모으는 것이다. 보통 dp라는 배열을 두고 dp[i]를 금액 i를 만드는 데 필요한 최소 동전 수라고 정의한다. 초기 조건은 보통 dp[0] = 0인데, 금액 0은 동전이 하나도 필요 없기 때문이다. 나머지 금액들에 대해서는 일단 도달 불가능하다고 가정하거나 충분히 큰 초기값을 둔다. 그런 다음 각 금액에 대해 모든 동전 단위를 시도해 본다. 현재 금액 i에서 어떤 동전 c를 뺄 수 있고, dp[i - c]가 이미 도달 가능한 상태라면 dp[i]는 dp[i - c] + 1로 갱신될 수 있다. 마지막에 dp[target]이 곧 정답이 된다.

겉으로 보기에는 이것이 흔한 상태 전이 공식처럼 보이지만, 그 뒤에는 매우 분명한 정보 처리 논리가 있다. 첫째, dp[i]는 가능한 모든 조합을 통째로 저장하지 않는다. 오직 ‘최적 결과’만 압축해서 보존한다. 즉 알고리즘은 최종 목표에 필요 없는 세부사항을 의도적으로 버리고, 의사결정에 필요한 최소한의 정보만 남긴다. 둘째, 각 갱신은 더 작은 상태 안에 이미 충분히 신뢰할 만한 정보가 농축돼 있다는 전제를 바탕으로 한다. 그래서 그 상태가 만들어진 전체 과정을 다시 펼쳐 볼 필요가 없다. 필요한 정보는 남기고 중복되는 세부사항은 버린다는 이런 사고는 정보 이론이 말하는 효율적 표현의 정신과 매우 가깝다.

동전 교환 문제는 상태 설계의 중요성을 가르쳐 주는 좋은 사례이기도 하다. 많은 초보자들이 동적 계획법을 어려워하는 이유는 코드를 못 쓰기 때문이 아니라, 도대체 상태를 어떻게 정의해야 하는지 감이 오지 않기 때문이다. 정보 이론식 사고는 여기에 하나의 판단 기준을 준다. 좋은 상태란 이후의 결정을 위해 필요한 정보를 충분히 담으면서도 과도하게 중복되지 않아야 한다. 이 문제에서는 각 동전을 몇 개씩 썼는지 모두 기록할 필요도 없고, 가능한 모든 조합을 보존할 필요도 없다. 현재 금액을 만드는 최적 비용이 얼마인지만 알면 된다. 이는 미래의 결정이 과거 경로의 구체적인 순서에 의존하는 것이 아니라 현재 금액에 대한 최적값에만 의존한다는 뜻이다. 다시 말해, 과거의 정보는 작지만 여전히 유효한 하나의 표현으로 압축될 수 있다.

훌륭한 알고리즘 설계가 공통적으로 갖는 특징도 바로 이런 적절한 정보 경계를 찾는 데 있다. 상태가 너무 단순하면 필요한 정보가 부족해 다음 결정을 내릴 수 없고, 상태가 너무 풍부하면 정보 중복이 커져 복잡도가 통제 불가능해진다. 알고리즘을 배울 때 진짜 실력 차이를 만드는 것은 특정 문제를 본 적이 있느냐가 아니라, 새로운 문제에서 어떤 정보는 반드시 남겨야 하고 어떤 정보는 버릴 수 있는지를 식별하는 능력이다. 그런 의미에서 정보 이론은 문제 풀이와 동떨어진 순수 이론이 아니다. 오히려 내 모델링이 충분히 압축적이고 표현이 경제적인지를 재는 가장 밑바탕의 자와 같은 역할을 한다.

동전 교환은 또 하나의 중요한 훈련 포인트를 보여 준다. 바로 최적성과 도달 가능성은 서로 다른 층위의 정보라는 점이다. 많은 사람들은 동적 계획법을 작성할 때 ‘이 금액을 만들 수 있는가’와 ‘만들 수 있다면 최소 몇 개가 필요한가’를 한꺼번에 섞어 생각하다가 혼란을 겪는다. 하지만 실제로는 먼저 도달 가능성을 구분하고, 그 위에서 최적성을 비교하는 편이 더 안정적이다. 도달 불가능한 상태는 빈칸이 아니라 그 자체로 하나의 정보다. ‘해답이 없음’과 ‘해답은 있지만 최적은 아님’을 명확히 구분해야 전이식이 흔들리지 않는다. 이는 정보 처리 전반에서도 비슷하다. 어떤 시스템이 미지의 상태, 값의 부재, 오류, 사용 가능하지만 덜 좋은 상태를 구별하지 못하면 이후 처리 과정이 쉽게 뒤엉킨다.

교육적 관점에서 정보 이론과 동전 교환을 함께 놓는 데에는 더 현실적인 의미도 있다. 오늘날 많은 학습 자료는 ‘문제를 풀 수 있는가’를 강조하지만, 왜 그런 방법이 타당한지까지 충분히 설명하지는 않는다. 그 결과 독자는 몇 가지 대표 문제의 템플릿을 빠르게 익힐 수는 있어도, 형태가 조금만 변하면 쉽게 흔들린다. 예를 들어 조합의 개수를 구하는 문제, 단순히 도달 가능 여부만 따지는 문제, 정확히 채웠을 때의 최대 가치를 구하는 문제, 동전 수량이 제한된 문제 등으로 바뀌면 기존 기억만으로는 대응이 어렵다. 반면 먼저 정보 조직의 관점을 세우면 이런 문제들 사이의 공통 구조가 더 잘 보인다. 결국 이들 모두는 상태 압축, 반복 부분 문제 제거, 제약 조건 표현, 목표 함수 최적화라는 축을 중심으로 움직이기 때문이다.

PixelBank 같은 학습 경로가 주목할 만한 이유도 여기에 있다. 기초 수학을 장식용 선행 지식으로 다루지 않고, 문제 구조를 더 빨리 알아보게 해 주는 도구로 취급한다는 점이다. 특히 독학하는 사람들에게 이런 접근은 중요하다. 많은 이들이 부족한 것은 문제 풀이량이 아니라 흩어진 지식을 연결해 주는 틀이다. 이론과 실전이 연결되기 시작하면 학습 효율은 크게 올라갈 수 있다. 더 이상 ‘동전 교환은 동적 계획법으로 푼다’는 문장을 외우는 데 그치지 않고, 왜 완전 탐색이 정보 중복을 낳는지, 왜 탐욕적 선택이 국소 최적에 갇힐 수 있는지, 왜 상태 전이가 사실상 압축된 지식 표를 점진적으로 확장하는 과정인지를 이해하게 된다.

더 큰 산업적 맥락에서 보더라도 이런 글은 기술 교육 서사가 변하고 있음을 보여 준다. 과거에는 기초 이론이 학술적 경로의 일부로 여겨지고, 알고리즘 문제는 취업 준비 도구처럼 취급되는 경우가 많았다. 그러나 지금은 점점 더 많은 플랫폼이 둘 사이의 왕복 관계를 강조한다. 이유는 분명하다. 소프트웨어 개발, 데이터 과학, 머신러닝 엔지니어링, 나아가 AI 응용 개발에서 진짜 경쟁력이 있는 사람은 문제 답안을 가장 빨리 암기한 사람이 아니라, 낯선 문제 속 구조를 빠르게 파악하고 적절한 상태를 추상화하며 복잡도를 낮출 수 있는 사람이다. 정보 이론은 불확실성과 표현 효율에 대한 감각을 길러 주고, 알고리즘 훈련은 그 감각을 실행 가능한 절차로 바꾸는 힘을 길러 준다. 둘이 결합될 때 비로소 현대 기술 업무의 실제 요구에 더 가까워진다.

물론 이런 연결의 한계도 함께 봐야 한다. 정보 이론과 동전 교환 사이에 엄밀한 일대일 대응이 있는 것은 아니다. 엔트로피나 부호화를 이해했다고 해서 모든 동적 계획법 문제를 자동으로 풀 수 있게 되는 것은 아니다. 더 타당한 해석은 이렇다. 정보 이론은 정보가 어떻게 조직되고 재사용되는지를 보는 상위 관점을 제공하고, 구체적인 문제 풀이에는 여전히 탄탄한 모델링 훈련, 경계 조건 검토, 복잡도 분석이 필요하다. 즉 이론이 기술을 직접 대체하는 것은 아니지만, 기술이 단순 암기에 머물지 않도록 해 준다.

실제 학습 경로 속에서 보면 이런 글은 특히 두 부류의 독자에게 유용하다. 첫째는 알고리즘을 막 시작했고 문제 풀이 자체에 부담을 느끼는 사람들이다. 이들은 종종 코드의 세부사항에 압도되어 동적 계획법을 일종의 마법처럼 느낀다. 정보 이론의 시각으로 접근하면 동적 계획법이 결국 정보를 저장하고, 활용하고, 중복 처리를 피하는 방식이라는 점을 이해하기 쉬워진다. 둘째는 이미 많은 문제를 풀었지만, 응용력과 전이 능력이 부족하다고 느끼는 사람들이다. 이들에게는 이런 학제적 설명이 문제 유형 템플릿에 대한 의존에서 벗어나 더 깊은 구조적 이해를 형성하는 데 도움을 준다.

이 사고를 더 확장하면 다른 고전 문제들도 같은 틀 안에서 다룰 수 있다. 배낭 문제는 자원 제약 아래에서 어떤 정보를 남겨야 하는지 생각하게 하고, 편집 거리는 두 시퀀스의 차이를 최소 비용으로 부호화하는 문제처럼 볼 수 있다. 최단 경로 문제는 국소 상태가 어떻게 전역 최적해에 점차 접근하는지를 보여 준다. 심지어 머신러닝에서도 특성 선택, 모델 압축, 손실 최적화는 어느 정도 정보 효율성과 연결해 해석할 수 있다. 이런 학습 경로는 문제 목록을 많이 외우는 것보다 장기적인 가치가 크다. 개별 문제를 넘어서 재사용 가능한 이해 능력을 길러 주기 때문이다.

종합하면, 이 글이 주목할 만한 이유는 희귀한 알고리즘 문제를 제시해서가 아니다. 오히려 이론과 실전을 갈라놓지 않는 더 성숙한 기술 글쓰기 방식을 보여 주기 때문이다. 추상 개념은 구체적 문제를 통해 현실에 닿고, 구체적 문제는 다시 이론의 설명력을 검증하는 역할을 한다. 기술 콘텐츠 독자에게 이런 글의 가치는 바로 여기에 있다. 단지 한 문제의 해법을 배우는 것이 아니라, 더 견고한 사고 프레임을 얻게 되는 것이다. 왜 동전 교환 문제가 동적 계획법으로 풀리는지를 이해한다는 것은, 단순히 정답 하나를 아는 것을 넘어 앞으로 더 복잡한 문제를 마주했을 때 정보, 상태, 제약, 최적성의 관계를 다시 붙잡을 수 있는 힘을 얻는다는 뜻이다.