알고리즘, FE 실무에 적용하기

📖 개요

코딩 테스트를 위해 공부한 알고리즘 지식들은 개발 실무에서 사용할 일이 없을까?

개발 영역, 개발자의 역량, 개발 환경마다 다를 것이다.

 

이에 본인 얘기를 하자면 웹 플랫폼 서비스의 FE 개발자이며 주로 사용자에게 보여지는 화면을 개발한다.

보통 화면 개발이라 함은

• 사용자 인터페이스, 인터렉션 개발
• 서버 API 요청/응답 처리

일 것이다.

 

방대한 데이터를 직접 조회하는 경우는 없고, 어느정도 가공되어 응답된 데이터를 서버에서 받아서 사용하다보니

데이터를 효율적으로 탐색하고 처리하려는 고민보다는 사용자 인터페이스와 사용자 경험 최적화에 대한 고민을 주로 했었다.

 

최근에는 평소보다 데이터의 효과적인 탐색 및 처리에 대한 알고리즘적인 접근을 요구하는 상황이 발생했고

이를 정리하여 기록해두고자 한다.

 

🥸 문제

이슈는 기존 코드를 리팩토링하는 과정에서 있었다.

회사 코드와 데이터 구조를 그대로 공개할 수 없기 때문에 최대한 추상화하여 문제를 정의해 보자면,

// 구매하려는 상품들과 각 상품별 적용가능한 쿠폰 배열이 주어졌을 때, 
// 아래 조건들을 만족하는 총 최대 할인 금액을 계산한다.

// 같은 쿠폰은 같은 id를 가진다.
// 쿠폰은 금액 내림차순으로 정렬되어 있다.
// 각 상품은 하나의 쿠폰만 적용 가능하다.
// 쿠폰은 재고가 있어야 적용 가능하다.
// 상품의 최대 개수는 20이다. (orderItems.length <= 20)

// 상품 타입
type OrderItem = {
  coupons: {
    id: number
    price: number // 할인 금액
    remain: number // 잔여 개수
  }[]
}

// 아래 orderItems 배열이 주어졌을 때, id:1, id:2 이 각각 적용되어 3000 이 응답되어야 한다.
orderItems = [
  {coupons: [{id:1, price: 2000, remain: 1}]},
  {coupons: 
    [
      {id:1, price: 2000, remain: 1},
      {id:2, price: 1000, remain: 2}
    ]
  }
]

 

정도가 될 것이다.

 

Greedy

기존 코드는 이를 그리디(Greedy) 한 방식으로 계산하고 있음을 발견했다.

간단하게 코드로 옮겨보자면 아래와 같은 방식이다.

// 쿠폰의 사용 가능 여부를 추적하는 객체
let couponUsage = {};

// 총 할인 금액을 계산
let totalDiscount = 0;

// 각 상품별로 최대 할인 적용
orderItems.forEach(item => {
  let maxDiscount = 0;
  let appliedCouponId = null;

  item.coupons.forEach(coupon => {
    // 해당 쿠폰이 아직 사용 가능하고, 최대 할인 금액보다 큰 경우
    if (couponUsage[coupon.id] > 0 && coupon.price > maxDiscount) {
      maxDiscount = coupon.price;
      appliedCouponId = coupon.id;
    }
  });

  // 쿠폰 적용
  if (appliedCouponId !== null) {
    totalDiscount += maxDiscount;
    couponUsage[appliedCouponId]--; // 사용된 쿠폰의 재고 감소
  }
});

 

 

orderItems가 위의 예시인 경우 코드를 실행시켜보면 totalDiscount에 3000이 할당될 것이다.

orderItems = [
  {coupons: [{id:1, price: 2000, remain: 1}]},
  {coupons: 
    [
      {id:1, price: 2000, remain: 1},
      {id:2, price: 1000, remain: 2}
    ]
  }
]

 

하지만 문제는 아래와 같이 orderItems 원소의 순서가 바뀌게 된다면 다른 값이 할당된다는 것이다. (id:1 만 적용되어 2000 할당)

orderItems = [
  {coupons: 
    [
      {id:1, price: 2000, remain: 1},
      {id:2, price: 1000, remain: 2}
    ]
  },
  {coupons: [{id:1, price: 2000, remain: 1}]}
]

 

최대 할인 금액은 orderItems 원소의 순서와 상관없이 일정해야 한다.

해당 문제를 계속 그리디하게 접근하자면, orderItems를 특정 조건으로 정렬한 뒤 최대 할인 금액을 계산하는 방법이 있을 것이다.

 

하지만 경험상 그리디하게 접근하는 방식은 한계가 있다. 이후에 새로운 쿠폰 사용 규칙이 추가되었을 때 확장성에 취약하다.

그리고 경험상 그리디하게 접근하여 최적의 합을 낼 수 없을 때 brute force 방식으로 접근하면 도움이 된다.

 

Brute Force (recursively)

따라서 주어진 orderItems 의 적용 가능한 모든 쿠폰 할인 금액을 재귀적으로 계산해서 비교해보고자 했다.

const orderItems = [
  {coupons: [{id: 1, price: 2000, remain: 1}, {id: 2, price: 1000, remain: 2}]},
  {coupons: [{id: 1, price: 2000, remain: 1}]}
];

// 쿠폰 사용 상태를 관리하는 객체
let couponUsage = {};

function getMaxDiscount(orderItems, index = 0, usedCoupons = {}, currentDiscount = 0) {
  if (index >= orderItems.length) {
    // 모든 상품에 대한 쿠폰 적용을 시도한 경우, 현재까지의 할인 금액을 반환
    return currentDiscount;
  }

  let maxDiscount = currentDiscount; // 현재까지의 최대 할인 금액을 초기값으로 설정

  // 현재 상품에 적용 가능한 모든 쿠폰에 대해 반복
  for (let coupon of orderItems[index].coupons) {
    const couponId = coupon.id;
    if (!usedCoupons[couponId] || usedCoupons[couponId] < coupon.remain) {
      // 쿠폰을 사용할 수 있는 경우
      const newUsedCoupons = {...usedCoupons};
      newUsedCoupons[couponId] = (newUsedCoupons[couponId] || 0) + 1;

      // 현재 쿠폰을 적용하고 다음 상품으로 넘어가 최대 할인 금액을 계산
      const newDiscount = getMaxDiscount(orderItems, index + 1, newUsedCoupons, currentDiscount + coupon.price);
      maxDiscount = Math.max(maxDiscount, newDiscount);
    }
  }

  // 현재 상품에 어떤 쿠폰도 적용하지 않는 경우도 고려
  const noCouponDiscount = getMaxDiscount(orderItems, index + 1, usedCoupons, currentDiscount);
  maxDiscount = Math.max(maxDiscount, noCouponDiscount);

  return maxDiscount;
}

const totalMaxDiscount = getMaxDiscount(orderItems);
console.log(totalMaxDiscount); // 3000

 

이제 어떤 순서의 orderItems가 넘어와도 적용 가능한 모든 쿠폰 할인 금액을 계산하기 때문에 항상 최적의 해를 낼 수 있게 되었다.

 

...과연 이제 더 이상 문제가 없을까? 🤔

 

코딩 테스트를 공부하며 항상 경험하는 것이지만, 다른 케이스는 다 pass 하는데 항상 시간 복잡도에서 실패하는 경우가 있다.

그리고 보통 brute force 방식으로 문제를 해결했을 때 이런 경우가 발생한다.

 

실제로 총 주문할 상품의 개수는 20개까지 가능했고 (orderItems.length <= 20)

각 상품에 쿠폰이 2개씩만 있다고 가정해도 2^20 번 순환을 하게 된다.

이를 jest로 테스트 코드를 작성하여 테스트 해봤을 때 굉장히 긴 시간동안 실행이 되었고, (macbook pro m3, ram 36gb 5min 이상)

JS 는 싱글 스레드 언어이기 때문에 위 함수가 완료될 때까지 어플리케이션이 멈춰있을 것이다. 😱

 

이는 절대 허용 불가 수치이며 이를 해결할 수 있는 방법을 모색해야했다.

 

Backtracking

백트래킹은 브루트 포스(Brute Force) 탐색을 기반으로 하되, 해가 될 가능성이 없는 경우 그 경로를 조기에 포기(Pruning)하고 다른 경로를 시도하는 "가지치기" 기법을 사용하여 효율성을 높이는 방식이다.

 

orderItem을 재귀적으로 순회하면서, 앞으로 남은 orderItem들의 '가능한 최대의 쿠폰 할인 금액' 합을 계산한다.

만약 '현재 쿠폰 할인 금액 (currentDiscount)'  + '가능한 최대의 쿠폰 할인 (possibleMaxDiscount)' 이

기존 '최대 할인 금액 (maxDiscount)' 보다 낮다면, 해당 경로는 더 이상 탐색할 필요가 없다.

 

다음은 backtracking 방식을 추가한 코드이다.

const getMaxDiscount = (orderItems) => {
  let maxDiscount = 0 // 최대 할인액을 저장하는 변수
  const couponStocks = {} // 각 쿠폰의 재고를 관리하는 객체

  // 각 orderItem의 최대 할인액을 저장
  const maxDiscountPerOrderItems = orderItems.map(orderItem => orderItem.coupons[0].price)
  const getPossibleMaxDiscountOfRestOrderItems = (currentIndex: number) => {
    return maxDiscountPerOrderItems.slice(currentIndex).reduce((acc, cur) => acc + cur, 0)
  }

  // 백트래킹 함수 정의
  function backtrack(currentIndex: number, currentDiscount: number) {
    // 모든 orderItem 를 처리한 경우, 최대 할인액을 업데이트
    if (currentIndex === orderItems.length) {
      maxDiscount = Math.max(maxDiscount, currentDiscount)
      return
    }

    // 현재 할인 금액과 나머지 orderItems 의 최대 할인 금액의 합이 기존 최대 할인 금액보다 작은 경우, 탐색 중단
    if (currentDiscount + getPossibleMaxDiscountOfRestOrderItems(currentIndex) <= maxDiscount) {
      return
    }

    // 현재 property 의 모든 쿠폰을 순회
    for (const coupon of orderItems[currentIndex].coupons) {

      // 쿠폰의 재고가 있는 경우만 처리
      if (coupon.remain <= 0) continue

      if (!couponStocks[coupon.id] || couponStocks[coupon.id] < coupon.remain) {
        // 쿠폰 적용: 재고 감소 및 할인액 증가
        couponStocks[coupon.id] = (couponStocks[coupon.id] || 0) + 1
        backtrack(currentIndex + 1, currentDiscount + coupon.price)

        // 백트래킹: 쿠폰 적용 취소
        couponStocks[coupon.id] -= 1
      }
    }

    // 현재 property 에서 쿠폰을 적용하지 않는 경우도 탐색
    backtrack(currentIndex + 1, currentDiscount)
  }

  // 백트래킹 시작
  backtrack(0, 0)

  return maxDiscount
}

 

쿠폰 배열들은 이미 가격 내림차순으로 정렬 되어있기 때문에 대부분의 최적인 최대할인 금액들이 먼저 결정이 되어 많은 경로를 '가지치기' 할 수 있을 것으로 예상된다.

😎 마치며

실제 운영되고 있는 코드와 상품, 쿠폰 타입 정의는 훨씬 더 복잡하다.

운영 코드가 그리디하게 작성되어 있다고 했지만, 그리디하게 해결하기 위해 굉장히 많은 비지니스 로직이 구현되어 있다.

첫 개발 이후 많은 기능과 정책들이 추가된 것으로 보이고 이를 기존 코드에서 해결하다보니 복잡도가 올라가고 가독성과 유지보수성이 떨어지게 되었다.

 

이를 해결하기 위해 기존 코드를 최대한 추상화하는 과정에서, 문제를 굉장히 단순화할 수 있었다.

또한, 이 과정을 통해 기존 코드에 포함되어 있던 일부 불필요한 비즈니스 로직을 발견하고 제거함으로써,

최적의 탐색 방법을 찾아낼 수 있었다. ( 더 좋은 방법이 있을 수도...? )

 

알고리즘 지식을 활용해 실제 운영 문제를 해결한 이번 경험은 매우 소중했으며,

이를 통해 얻은 통찰력을 바탕으로 앞으로 다양한 도전들을 성공적으로 극복해나갈 수 있을 것이다.