많은 어려운 LeetCode 문제는 쉬운 제약 조건 문제임

(buttondown.com)

4P by GN⁺ 2일전 | ★ favorite | 댓글 1개

LeetCode의 어려운 문제들도 제약 조건 솔버를 사용하면 훨씬 쉽게 풀 수 있음
복잡한 동적 계획법이나 자체 알고리듬 대신 MiniZinc와 같은 제약 조건 솔버를 활용하여 수학적 최적화 문제를 간단하게 해결 가능함
전통적인 프로그래밍 언어는 이런 수학적 최적화 문제를 표현하기 어려움으로 제약 조건 기반 접근법이 강점임
예외 상황이나 추가 제약 조건이 등장해도 제약 조건 솔버에서의 모델 변경이 최소화됨
런타임 복잡성은 직접 짠 최적화된 알고리듬보다 느릴 수 있지만, 유연성과 개발 생산성 면에서 많은 장점이 있음

제약 조건 솔버로 푸는 LeetCode 문제

올바른 도구의 선택

필자가 대학 졸업 후 첫 면접에서 '동전 거스름돈 문제'를 받았음
- 동전 단위가 주어졌을 때, 정해진 금액을 거슬러주기 위해 필요한 최소 동전 개수를 구하는 문제임
- 단순한 탐욕 알고리듬을 사용했지만, 모든 경우에 최적해를 보장하지 못함
- 동적 계획법이 정답이지만 이를 구현하지 못해서 면접에 실패함
하지만 직접 알고리듬을 구현하지 않고 MiniZinc와 같은 제약 조건 솔버를 활용하면 아주 쉽게 해결할 수 있음
- 예시 코드:
```
int: total;
array[int] of int: values = [10, 9, 1];
array[index_set(values)] of var 0..: coins;

constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
solve minimize sum(coins);
```
- 온라인에서 직접 MiniZinc 예시 실행 가능
- 솔버가 점진적으로 최적해를 찾아줌

다양한 최적화/만족 문제

LeetCode 등에서 흔하게 나오는 수학적 최적화 문제(목적 함수 극대화/극소화 및 여러 제약 조건 포함)는
프로그래밍 언어로 풀 때 저수준 구현 때문에 어렵지만, 제약 조건 솔버에는 적합함
예를 들어, 아래 성격의 다양한 문제들이 이에 해당함

예시 1: 최대 주식 차익 문제

'리스트로 주어진 주식 가격 데이터에서, 한 번 사서 그보다 나중에 팔아 얻을 수 있는 최대 이익을 구하라'
- 전통적으로 O(n²) 브루트포스 또는 O(n) 최적 알고리듬 필요
- MiniZinc에서는 아래와 같이 간단한 제약 조건 문제로 정의 가능
```
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
var int: buy;
var int: sell;
var int: profit = prices[sell] - prices[buy];

constraint sell > buy;
constraint profit > 0;
solve maximize profit;
```

예시 2: 특정 수의 덧셈/뺄셈으로 0 만들기 (만족 문제)

'리스트에서 세 수를 더하거나 빼서 0을 만들 수 있는가?'

최적 값이 아닌 만족 가능한 해만 찾으면 됨

제약 조건 솔버에서 다음과 같이 표현

include "globals.mzn";
array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array[index_set(numbers)] of var {0, -1, 1}: choices;

constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
constraint count(choices, -1) + count(choices, 1) = 3;
solve satisfy;

예시 3: 히스토그램에서 최대 직사각형 넓이

'각 막대의 높이가 주어진 히스토그램에서, 만들 수 있는 가장 큰 직사각형의 넓이를 구하라'

전통적으로 복잡한 알고리듬과 다수의 상태 관리 필요

제약 조건만으로 간결하게 해법 서술

array[int] of int: numbers = [2,1,5,6,2,3];

var 1..length(numbers): x; 
var 1..length(numbers): dx;
var 1..: y;

constraint x + dx <= length(numbers);
constraint forall (i in x..(x+dx)) (y <= numbers[i]);

var int: area = (dx+1)*y;
solve maximize area;

output ["(\(x)->\(x+dx))*\(y) = \(area)"]

제약 조건 솔버 접근이 더 나은가?

면접 현장에서 시간 복잡도 등 질문에 약점이 있음
- 제약 조건 솔버는 실행 시간 예측이 힘들며, 맞춤형 최적 알고리듬보다 보통 느림
- 하지만 잘못 구현한 저품질 알고리듬보다는 좋으며, 대부분의 프로그래머가 매번 최적 해법을 직접 짜기는 쉽지 않음

실제 강점은 새로운 제약 조건 추가에 대한 유연성임

예를 들어, 주식 예시에서 한 번이 아니라 여러 번 사고팔도록 변경할 때 알고리듬 복잡도가 급증

MiniZinc의 제약 조건 모델에서는 소폭의 코드 변경만으로 훨씬 복잡한 요구사항 수용 가능

include "globals.mzn";
int: max_sales = 3;
int: max_hold = 2;
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array [1..max_sales] of var int: buy;
array [1..max_sales] of var int: sell;
array [index_set(prices)] of var 0..max_hold: stocks_held;
var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);

constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
constraint profit > 0;

constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
constraint alldifferent(buy ++ sell);
solve maximize profit;

output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];

온라인의 제약 조건 문제 예시는 Sudoku 등 퍼즐 중심이지만, 실제 비즈니스 로직이나 최적화 요구가 있는 문제에 더 흥미롭고 실용적으로 쓸 수 있음
- 예를 들어, symmetry breaking(대칭성 제거) 같은 고급 최적화 기법 적용 가능성도 높음

마무리 및 참고

이 글은 저자의 주간 뉴스레터로, 소프트웨어 역사, 형식 기법, 새로운 기술, 소프트웨어 엔지니어링 이론을 다룸
관심 있으면 구독 또는 저자의 메인 웹사이트 참고 가능
저자의 신간 "Logic for Programmers" 도 출간 중임

▲

GN⁺ 2일전 [-]

Hacker News 의견

Leetcode 유형의 면접 질문에서 가장 큰 문제점은 추가 설명을 요청할 수 없는 점임, 내 사고방식이 일반적인 것과 달라서 Leetcode는 정답을 외우는 쪽에 의존하는 것 같음, 맥락이 충분한 문제는 현실적인 이해를 할 수 있어서 괜찮지만 대부분은 설명이 부족해 문제를 제대로 파악하지 못함, 그래서 요즘은 Leetcode나 AI 자동화 면접 단계는 아예 거부함, 과제나 1:1, 화면 공유 인터뷰는 괜찮음, Leetcode 사이트에 제대로 된 해설과 정답이 있다면 독학도 훨씬 쉽겠지만 실제로는 너무 어려움, 단순히 실력의 문제가 아니라 내 사고 방식과 문제 유형의 궁합이 맞지 않음, 질문도 못 하는 상태에서 객관식 문제만 계속 푸는 건 실패하게끔 짜인 시스템 같음, 특히 사전 면접용 AI/Leetcode형 문제를 대상으로 얘기하는 중임, 실제 사람이 있는 면접에서 질문이 오가는 환경은 충분히 좋게 생각함
- LC(Leetcode) 면접은 마치 훈련된 100m 달리기 속도를 테스트하는 것과 비슷함, 실제 업무는 여러 번 멈추고 돌아가는 긴 마라톤 같음, 그래도 지금은 SMEGMA 같은 대기업에서 높은 연봉을 얻으려면 이런 게임을 해야 함, 예를 들어 나는 2D 게임 엔진을 직접 만들었지만, LC 하드 문제 여러 개를 백플립까지 해내야 통과하는 LC 면접은 못 할 것 같음, 그걸 이미 받아들였음 내가 만든 엔진
- 솔루션 외우기로 되는 게 전부는 아님, 외워도 추가 질문에서 막힐 수 있음, 하지만 외운 상태에서 추가 질문도 잘 풀면 Leetcode 스타일 문제에 문제 없다고 생각함, 문제 해결력은 패턴 매칭 능력이고 패턴을 많이 알수록 문제 해결력이 높아짐, 이제는 GPT가 문제도 풀고 해설도 해 줘서 이런 능력이 더 쉽게 익힐 수 있음, 지금부터라도 익히는 게 낫다고 봄
- 정말 공감함, 나도 최근 인터뷰에서 과제는 최고 점수를 받고 엔지니어들과 CEO도 좋게 봤지만, CTO가 느닷없이 라이브 코딩 면접을 시켜서 결국 떨어졌음, 11주간 면접 본 게 헛수고가 됐음, 이 바보 같은 과정이 아직도 있다는 게 답답함, 내가 했던 데모/과제는 여기 monumental 링크와 결과물, GitHub 코드
- 명확한 질문을 할 수 없는 게 실제로 검증하려는 능력 아니냐는 생각임, 후보자가 문제 해결할 때 어떤 방식으로 접근하는지 보는 것, 만약 사람들이 단정적으로만 접근하게 하면 모든 소프트웨어가 오히려 복잡해지고 엉망이 될 것임, 진짜 어려운 건 코드 줄을 쓰는 게 아니라 문제를 푸는 과정임
- 내가 인터뷰했던 곳은 LC 문제 한두 개 정도를 주는데도 설명을 요청하면 바로 실시간 대화와 코딩으로 진행했음, 이렇게 하면 단점 하나는 실시간 라이브 코딩의 심리적 부담이 커짐
이런 인터뷰 문제를 받으면, 제약 조건 솔버를 '쓰는 것'이 아니라 제한된 문제에 맞는 제약 조건 솔버를 '직접 짜는 것'을 원하는 것으로 느껴짐
- 맞음, 그래서 이런 식의 면접 접근법이 근본적으로 어설프다고 생각함, 실제 엔지니어링 상황에서는 커피 마시고 논문도 읽고 도서관도 보고, 산책도 하며 고민하고, 이미 있는 도구(제약 조건 솔버나 LLM)를 참고해서 문제를 100% 풀 수 있음, 그런데 면접 상황에서는 0%도 못 풀 것 같음, 이런 면접을 하는 곳에 입사하겠다는 생각조차 안 해봤음
- 정말 그렇다고 봄, NP 문제 대부분이 제약 문제로 변환 가능함, 실제로 제약 조건 솔버가 정답일지 아닐지는 적용 영역에 따라 매우 다름, 그리고 면접 상황에서는 거의 정답이 아님, 이런 솔버는 간단한 다이나믹 프로그래밍보다 아주 느릴 때가 많음
- 어떤 회사 면접에서는 이게 사실일 수 있지만 그렇지 않은 곳도 많음, 일반적으로 LC를 면접에 사용하는 것은 한 가지 이유(비효율적 채용 프로세스 때문)로만 쓰이는 경우가 많았음, 참여자조차도 체계 개편이 필요함을 알지만 파워가 없거나 너무 분산되어 있어서 못 바꾸는 경우임, 큰 회사에서는 HR이 '표준화'를 위해 같은 질문을 다양한 팀에 돌리기도 하고, 작은 회사는 자체적으로 문제 준비할 시간이 없어 인터넷에서 긁어 옴, 이럴 때는 기술 면접관조차 LC 인터뷰에 비판적이어서 실질적으로 튀는 후보를 찾아내려고 애씀, 이런 환경에서는 제약 조건 솔버에 관심 또는 지식이 있다는 것만 보여도 꽤 좋은 점수를 받곤 함
- 누군가 LC 하드 문제를 제약 조건 솔버로 풀었는데 그 사람을 채용하지 않는다면 그건 면접관 본인이 멍청한 것임, 제약 조건 솔버가 뭔지, 문제를 정의해서 쓸 줄 아는 사람 자체가 아주 드물음, 나도 3학년 때 썼는데 제약식 쓰는 것만 해도 머리가 아플 정도로 복잡한 작업이었음
- 이 부분은 맞기도 틀리기도 함, 내가 인터뷰에서 이런 질문을 해본 적 있는데, 만약 지원자가 제약 조건 솔버를 떠올리면 좋은 점수를 줬음, 실제 엔지니어링에서 제약 조건 솔버는 과소평가되어 있으면서 제대로 답을 빨리 낼 줄 아는지 보여주는 지표임, 물론 이후엔 진짜 코딩 역량을 파악하기 위한 후속 화이트보드 질문을 하긴 할 거임, 그러나 답변으로 제약 조건 솔버를 제시하는 것 자체는 나쁘지 않다고 판단함
멋진 인사이트지만, 현실 면접에는 잘 맞지 않는다고 생각함, 이러한 문제의 핵심은 지원자에게 '머리 쓰기' 능력을 검증하려는 것임, 그냥 제약식으로 푸는 건 경험과 지식 수준만 보여줄 뿐, "머리를 썼는지"는 드러나지 않음
- 면접관들은 Leetcode 'Top Interview 150'의 "Array String" 문제를 자주 내는 경향이 있음, 나 같은 백엔드 Python 개발자 입장에서는 해당 문제들이 평소 업무와는 거리가 멀다고 느낌, 대부분 in-place array 연산 알고리즘을 요구하는데 이는 보통 C나 Rust같은 퍼포먼스 중심 언어에서만 필요함, 오히려 "Hashmap" 유형 문제는 언어에 맞는 도구 활용을 보여주는 데 더 유용함, 또한 난이도 조절이 안 되는 문제도 많아서 "쉬움" 등급의 문제(예: Majority Element)가 실제로는 역사적 알고리즘(Boyer–Moore)이 요구되는 수준임, "쉬움"으로 보기 어려운 점이 있음
- 최근 Meta에서 본 마지막 라운드는 오로지 그들만의 특정 문제를 얼마나 반복해서 암기했는지 확인하는 과정임, 그래서 교과서 답과 다르게 대답하면 오히려 당황해함, "영리함" 자체는 그다지 중요하지 않은 것 같은 느낌임
- 바텀업 DP 알고리즘은 어느 정도 머리를 써야 하지만, 대부분의 문제는 탑다운 방식(재귀+메모이제이션)으로 풀 수 있음, 예를 들어 코인 교환 문제는 A* 탐색으로 더 잘 풀 수 있음, 그러나 현실에서는 대부분의 프로그래머가 이런 알고리즘을 정말 쓸 일이 거의 없음, 진짜 중요한 건 실수로 시간복잡도 O(n^2)짜리 코드를 짜는 걸 알아차리는 것임, accidentallyquadratic.tumblr.com 보면 유명한 프로젝트의 실력자들도 이런 실수를 자주 함, 그러니 테스트에서 알고리즘을 만드는 능력이 실제로 일하면서 알고리즘 실수를 잡는 능력과는 별개임
- 나는 면접에서 문제해결 능력을 검증할 때 사고과정, 소통방식, 문제 분해를 중시함, 난이도 조절이 가능한 질문을 준비해 모든 지원자가 자신의 역량을 드러낼 기회를 갖는 게 훨씬 중요함, 딱 떠오른 답을 바로 외치거나, 한참 막히는 건 사실상 면접관 입장에서 금방 파악할 수 있는 부분이 거의 없음, 그래서 문제해결형 면접 질문은 아주 유용할 수 있지만, 현실에선 잘 쓰이지 않는 게 아쉬움
- 이런 문제들은 진짜로 '영리함'이 아닌, 12가지 정도의 정형화된 패턴을 얼마나 외웠는지 테스트하는 거임, 거의 모든 지원자들이 본인의 창의적 문제해결이 아니라 준비해온 암기력에 따라 합격 여부가 갈림, LeetCode 문제는 너무 게이미피케이션되어서 준비 의지만 확인하는 수단이 된 느낌임
대부분의 면접은 '만약 당뇨 환자가 직접 집에서 인슐린을 합성하지 못한다면, 인생게임에서 반칙'이라고 전제하고 문제를 내는 것 같음, 내 아내가 혈당이 올라가면 인슐린을 맞듯, 제약 조건 문제라면 솔버를 쓰는 게 맞음, 회사가 제약 조건 솔버 소프트웨어를 만드는 곳이 아니라면, 굳이 '이런 소프트웨어가 존재하지 않는다'고 전제하고 다시 처음부터 만들라고 요구하는 이유가 뭔지 모르겠음
- 핵심은 위기 때 인슐린을 합성하는 능력을 테스트하는 게 아니라, 일주일 내에 교재를 외우고 전화면접에서 잘 읊을 수 있는지를 평가하는 사전 적성 테스트임
- 제약 조건 솔버로 효율적으로 문제를 푸는 방법을 찾을 수 있다면, for문 두 개 정도와 보조 재귀함수도 쉽게 만들어서 장난감 문제는 다 풀 수 있음
- (의미 있는 내용 없음)
- 코딩테스트를 옹호하자면, 대부분 간단한 DP 문제도 못 푸는 사람은 실제 업무에서도 실력이 부족한 경우가 많았음, 물론 예외는 있겠지만 내 경험상 그래왔음
제약 프로그래밍 언어 얘기가 나오면 항상 Håkan Kjellerstrand를 언급해야 함, MiniZinc 포함한 수많은 예제와 문제들이 모여있는 멋진 사이트를 운영 중임 hakank minizinc
- 그리고 그는 좋은 웹사이트를 만든 것뿐 아니라 실제로 엄청 친절한 사람임
정말 오래 전, 대학 컴퓨터공학 과정에서 제약 조건 솔버를 배우지 못했던 풋내기였을 때, 스포츠 클럽 일정 짜기 앱을 만들어 달라는 친구의 부탁을 받으며 이 문제를 만났음, 처음엔 쉬워 보였지만 실제로 시도하다가 내가 엄청난 문제에 부딪힌 걸 깨닫지 못했음, 나중에서야 내 오만함에 대한 좋은 교훈이었고, 그 경험 덕분에 일정/기한/기대치 논의할 때 큰 도움이 됨
- 초보적인 질문일 수 있지만, 제약 조건 솔버 대신 '선형 최적화'로 더 쉽게 풀 수 있지 않을까 궁금함, 직접 쓴 경험으로, 선형 최적화는 규칙 간 충돌을 가중치로 처리해 최소한의 '부작용'이 생기는 방향으로 해를 찾을 수 있다는 점이 장점임
- 25년 전 고등학교 시절, 막 TI-Basic과 VB6를 배우기 시작한 때, 햄버거가게에서 아르바이트하며 매니저가 매주 직원 스케줄 짜는 게 어렵다고 하소연하는 걸 듣고 "나 컴퓨터 좀 아는데 스케줄링 프로그램 만들어드릴게요!" 했음, 곧 스케줄러 짜는 게 얼마나 어려운 일인지 깨닫고 바로 포기했음
"이런 문제를 면접에 내면, 면접자가 '이 알고리즘의 런타임 복잡도는?'이라고 물으면 대책이 없다는 게 저자의 주장임", 즉, 제약 조건 솔버도 충분히 빠르게 풀지 못하면 Leetcode 하드 문제의 해답은 아님, 런타임 요구 조건이 널널하면 간단한 방법도 되겠지만, 효율적인 해법을 찾는 게 전체 도전의 큰 부분임
- 실제 현장에서는 언제나 '가장 효율적인 해법'보다 '빠르게 새로운 요구에 대응하는 솔루션 고안'이 더 많이 요구됨, 그래서 현실과 동떨어진 효율성 기준의 면접이 의미 있나 의문임(일하는 역할마다 다를 수 있음), 가장 효율적인 해법이 진짜 실무 능력을 반영하지 않을 수 있다는 저자의 시각에 동의함, Leetcode 비판의 한 맥락도 이런 점임, 같은 문제라도 '새로운 요구에 얼마나 유연하게 대처할 수 있냐' 관점에서 보는 것이 더 객관적임
제약 조건 솔버? 좋은 아이디어고 들어본 적 있음, 하지만 면접에선 그냥 Python으로 직접 구현해보면서 생각의 흐름을 보고 싶어하는 게 실제임, (인터뷰에서 제약 조건 솔버를 쓴다고 설득하는 게 거의 불가능하다고 느낌)
- 실제로 이런 얘기를 면접관에게 해봤는지, 아니면 그냥 예상일 뿐인지 궁금함
- import z3
DP(다이나믹 프로그래밍)로 푼 뒤 "이제 제약 조건 솔버로도 해볼게요"라고 하면 바로 채용임
- +1
제약 조건 솔버의 실제 강점은 '새로운 요구사항'에 얼마나 쉽게 대응할 수 있냐는 점임, 나도 Google에서 데이터센터 최적화 하면서 이런 일반화된 솔버가 요구 변경에 맞게 유연하게 동작하는 혜택을 크게 경험했음

답변달기