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

4 days ago 7

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(대칭성 제거) 같은 고급 최적화 기법 적용 가능성도 높음