완전 탐색은 무식하게 모든 경우를 확인하는 방법이 아니다

알고리즘을 처음 배울 때 완전 탐색은 가능한 모든 경우를 하나씩 확인하는 방법이라고 배운다.

세 개의 쿠폰 중 가장 큰 할인 금액을 찾는다면 모든 쿠폰을 확인할 수 있다.

function findBestCoupon(coupons) {
  let bestCoupon = null;

  for (const coupon of coupons) {
    if (
      bestCoupon === null ||
      coupon.discountAmount >
        bestCoupon.discountAmount
    ) {
      bestCoupon = coupon;
    }
  }

  return bestCoupon;
}

이 코드는 쿠폰을 처음부터 끝까지 확인하면서 지금까지 발견한 가장 큰 할인 쿠폰을 기억한다.

가능한 후보를 빠짐없이 확인한다는 완전 탐색의 기본 개념을 이해하기에는 충분한 예제다.

완전 탐색은 구현이 단순하고 모든 후보를 확인하기 때문에 정답을 놓치지 않는다는 장점이 있다.

하지만 실제 쿠폰 서비스에서 “가장 좋은 쿠폰”을 찾는 문제는 하나의 쿠폰만 비교하는 것으로 끝나지 않을 수 있다.

• 여러 쿠폰을 함께 사용할 수 있는가?
• 최대 몇 개까지 적용할 수 있는가?
• 같은 종류의 쿠폰을 중복해서 사용할 수 있는가?
• 특정 상품에만 적용되는 쿠폰이 있는가?
• 정액 할인과 비율 할인을 어떤 순서로 적용하는가?
• 배송비 쿠폰과 상품 할인 쿠폰을 함께 사용할 수 있는가?
• 할인 금액이 같은 조합이 여러 개라면 무엇을 선택하는가?
• 사용자가 가진 쿠폰은 최대 몇 개인가?
• 모든 조합을 확인해도 결제 화면의 응답 시간 안에 끝나는가?
• 더 빠른 방법으로 바꿨을 때도 같은 결과를 만든다고 어떻게 확인하는가?

가능한 경우를 모두 확인한다는 설명은 틀리지 않다. 그러나 실제 서비스에서는 무엇을 하나의 경우로 볼 것인지, 모든 경우가 몇 개인지, 어떤 경우를 확인하지 않아도 되는지까지 판단해야 한다.

실제 서비스에서 완전 탐색은 생각 없이 모든 경우를 실행하는 방법이 아니라, 가능한 선택의 전체 범위를 명확히 정의하고 정확한 기준점을 만든 뒤 근거가 있는 조건으로 탐색 범위를 줄여가는 출발점이다.

모든 경우를 확인하려면 먼저 무엇이 하나의 경우인지 정해야 한다

크리스가 다음 세 쿠폰을 가지고 있다고 생각해보자.

const coupons = [
  {
    id: "coupon_a",
    title: "Welcome",
    discountAmount: 1000,
  },
  {
    id: "coupon_b",
    title: "Birthday",
    discountAmount: 2000,
  },
  {
    id: "coupon_c",
    title: "Dinner Date",
    discountAmount: 3000,
  },
];

쿠폰을 하나만 사용할 수 있다면 가능한 선택은 비교적 단순하다.

• 아무 쿠폰도 사용하지 않는다.
• coupon_a를 사용한다.
• coupon_b를 사용한다.
• coupon_c를 사용한다.

하지만 여러 쿠폰을 함께 사용할 수 있다면 선택의 범위가 달라진다.

• 아무것도 선택하지 않는다.
• a만 선택한다.
• b만 선택한다.
• c만 선택한다.
• a와 b를 선택한다.
• a와 c를 선택한다.
• b와 c를 선택한다.
• a, b, c를 모두 선택한다.

쿠폰이 세 개일 때는 8가지 조합이 생긴다.

각 쿠폰마다 선택하거나 선택하지 않는 두 가지 결정이 있으므로 쿠폰이 n개라면 최대 2ⁿ개의 조합이 생긴다.

쿠폰 수	가능한 조합 수
3	8
10	1,024
20	1,048,576
30	1,073,741,824
50	1,125,899,906,842,624

완전 탐색이 가능한지는 반복문이 몇 개 있는지만으로 판단할 수 없다.

입력 크기와 하나의 후보를 평가하는 비용, 요청당 허용 시간까지 함께 봐야 한다.

가장 단순한 완전 탐색은 정확성의 기준을 만든다

쿠폰 조합을 찾는 가장 직접적인 방법은 각 쿠폰을 선택하는 경우와 선택하지 않는 경우를 모두 확인하는 것이다.

function findBestCombination(coupons, order) {
  let best = {
    couponIds: [],
    discountAmount: 0,
  };

  function search(index, selected) {
    if (index === coupons.length) {
      const discountAmount =
        calculateCombinedDiscount(
          selected,
          order
        );

      if (
        discountAmount >
        best.discountAmount
      ) {
        best = {
          couponIds: selected.map(
            (coupon) => coupon.id
          ),
          discountAmount,
        };
      }

      return;
    }

    search(index + 1, selected);

    selected.push(coupons[index]);
    search(index + 1, selected);
    selected.pop();
  }

  search(0, []);

  return best;
}

각 쿠폰에서는 두 가지 선택을 한다.

1. 현재 쿠폰을 선택하지 않고 다음 쿠폰으로 이동한다.
2. 현재 쿠폰을 선택한 뒤 다음 쿠폰으로 이동한다.

마지막 쿠폰까지 결정하면 선택된 조합의 실제 할인 금액을 계산하고, 지금까지의 최선보다 크면 결과를 갱신한다.

이 구현은 쿠폰 수가 많을 때 느리다. 그렇다고 처음부터 가치가 없는 코드는 아니다.

가능한 조합을 빠짐없이 확인하기 때문에 입력이 작다면 신뢰할 수 있는 기준 결과를 만든다.

이 기준은 이후에 더 빠른 방법을 설계할 때 중요해진다.

최적화된 알고리즘이 정말 같은 답을 만드는지 확인하려면 먼저 느리더라도 명확하게 옳은 기준 알고리즘이 필요하다.

완전 탐색이 느리다는 말만으로는 설계 판단을 할 수 없다

2ⁿ이라는 증가 속도를 보면 완전 탐색은 항상 피해야 할 것처럼 느껴질 수 있다.

하지만 실제로 처리해야 하는 쿠폰 수가 최대 8개라면 가능한 조합은 256개뿐이다.

각 조합의 할인 금액을 계산하는 비용이 작고 요청량도 낮다면 완전 탐색이 충분히 적절할 수 있다.

반대로 사용자가 최대 100개의 쿠폰을 보유할 수 있다면 모든 조합을 확인할 수 없다.

따라서 먼저 다음 조건을 확인해야 한다.

제약	확인할 내용
입력 크기	한 사용자가 비교할 쿠폰은 최대 몇 개인가
조합 규칙	쿠폰을 최대 몇 개까지 함께 사용할 수 있는가
평가 비용	조합 하나의 할인 금액을 계산하는 데 어떤 작업이 필요한가
실행 빈도	결제 화면을 열 때마다 실행하는가
응답 시간	사용자는 얼마나 기다릴 수 있는가
데이터 위치	쿠폰과 주문 데이터가 이미 메모리에 있는가
변경 빈도	쿠폰 정책과 장바구니가 얼마나 자주 바뀌는가
정확성 요구	가장 좋은 조합이 반드시 필요한가, 충분히 좋은 조합도 허용되는가

완전 탐색을 사용할 수 있는지는 알고리즘 이름이 아니라 이 제약 조건으로 판단해야 한다.

모든 데이터를 탐색 후보로 넣을 필요는 없다

사용자가 가진 모든 쿠폰을 곧바로 조합에 넣는 코드를 생각해보자.

const bestCombination =
  findBestCombination(userCoupons, order);

userCoupons에는 이미 사용한 쿠폰, 만료된 쿠폰과 현재 주문에 적용할 수 없는 쿠폰도 포함될 수 있다.

이 데이터까지 조합에 넣으면 정답이 될 수 없는 후보를 반복해서 확인한다.

탐색을 시작하기 전에 기본 조건으로 후보를 줄일 수 있다.

const eligibleCoupons = userCoupons.filter(
  (coupon) =>
    coupon.status === "ACTIVE" &&
    coupon.remainingUses > 0 &&
    serverNow < coupon.expiresAt &&
    isApplicableToOrder(coupon, order)
);

이 코드는 활성 상태이고 남은 횟수가 있으며, 만료되지 않았고 현재 주문에 적용할 수 있는 쿠폰만 남긴다.

쿠폰이 20개에서 8개로 줄어들면 가능한 모든 조합은 약 100만 개에서 256개로 줄어든다.

다만 이 필터링에 사용하는 데이터의 출처도 중요하다.

const userCoupons =
  await couponRepository.findEligibleByUser({
    userId: currentUser.id,
    orderId,
    now: serverNow,
  });

쿠폰 상태, 소유자와 남은 사용 횟수는 클라이언트가 보낸 값을 신뢰하지 않고 서버와 데이터베이스의 최신 데이터를 사용해야 한다.

화면에 표시된 쿠폰 목록은 사용자가 마지막으로 조회한 복사본이다. 최종 후보를 정하는 Source of Truth는 서버가 조회한 최신 쿠폰 상태다.

완전 탐색의 비용은 탐색 함수 안에서만 줄이는 것이 아니다. 탐색에 들어오기 전 어떤 데이터를 후보로 가져올지 결정하는 순간부터 줄일 수 있다.

서비스 규칙은 탐색 공간을 줄이는 근거가 된다

쿠폰 서비스의 정책이 다음과 같다고 생각해보자.

한 주문에는 쿠폰을 최대 3개까지 적용할 수 있다.

그렇다면 4개 이상의 쿠폰을 선택한 조합은 확인할 필요가 없다.

function findBestCombination(coupons, order) {
  let best = {
    couponIds: [],
    discountAmount: 0,
  };

  function search(index, selected) {
    if (
      selected.length === 3 ||
      index === coupons.length
    ) {
      const discountAmount =
        calculateCombinedDiscount(
          selected,
          order
        );

      if (
        discountAmount >
        best.discountAmount
      ) {
        best = {
          couponIds: selected.map(
            (coupon) => coupon.id
          ),
          discountAmount,
        };
      }

      return;
    }

    search(index + 1, selected);

    const coupon = coupons[index];

    if (canStackWithSelected(coupon, selected)) {
      selected.push(coupon);
      search(index + 1, selected);
      selected.pop();
    }
  }

  search(0, []);

  return best;
}

이 코드는 다음 두 경우에 탐색을 멈춘다.

• 이미 쿠폰을 3개 선택했다.
• 모든 쿠폰에 대한 결정을 끝냈다.

또한 현재 선택된 쿠폰들과 함께 사용할 수 있는 경우에만 새로운 쿠폰을 추가한다.

예를 들어 배송비 쿠폰을 하나만 사용할 수 있다면 두 번째 배송비 쿠폰을 선택하는 분기는 만들 필요가 없다.

이것이 가지치기다.

가지치기는 단순히 실행 시간을 줄이기 위해 일부 경우를 건너뛰는 일이 아니다. 건너뛴 경우가 정답이 될 수 없다는 근거가 있을 때만 탐색을 중단하는 판단이다.

빠르게 만들기 전에 제거해도 되는 이유를 설명해야 한다

정액 할인 쿠폰의 할인 금액이 큰 순서로 정렬하고 앞의 세 개만 선택할 수도 있다.

const selectedCoupons = [...coupons]
  .sort(
    (first, second) =>
      second.discountAmount -
      first.discountAmount
  )
  .slice(0, 3);

코드는 짧고 빠르다.

모든 쿠폰이 서로 함께 사용 가능하고, 할인 금액이 주문 상태와 관계없이 고정되어 있다면 올바를 수 있다.

하지만 다음과 같은 정책이 있다면 결과가 달라질 수 있다.

• 일부 쿠폰은 함께 사용할 수 없다.
• 비율 쿠폰은 적용 순서에 따라 할인 금액이 달라진다.
• 특정 상품 쿠폰은 일부 금액에만 적용된다.
• 배송비 쿠폰은 상품 할인 금액과 직접 비교할 수 없다.
• 쿠폰을 적용하면 최소 주문 금액 조건이 달라질 수 있다.
• 최대 할인 한도가 조합 전체에 적용된다.

이 상황에서는 개별 할인 금액이 가장 큰 쿠폰 세 개가 전체적으로 가장 큰 할인을 보장하지 않는다.

빠른 선택 방법을 사용하려면 다음과 같은 근거가 필요하다.

• 각 쿠폰의 효과가 다른 쿠폰의 선택과 독립적인가?
• 현재의 가장 좋은 선택이 이후 선택의 가능성을 줄이지 않는가?
• 적용 순서가 결과를 바꾸지 않는가?
• 개별적으로 좋은 선택을 모으면 전체적으로도 최선인가?

이 조건을 설명할 수 없다면 단순 정렬은 빠르지만 틀린 결과를 만들 수 있다.

완전 탐색은 여기에서 비교 기준이 된다.

작은 데이터로 모든 조합을 확인한 결과와 빠른 선택 방법의 결과를 비교하면 어떤 조건에서 두 방법이 달라지는지 발견할 수 있다.

이미 최선이 될 수 없는 경로는 더 확인하지 않아도 된다

후보를 줄였지만 여전히 조합이 많다면 현재 경로가 최선이 될 가능성이 있는지 계산할 수 있다.

예를 들어 지금까지 선택한 쿠폰의 할인 금액이 3,000원이고, 남은 쿠폰에서 얻을 수 있는 최대 추가 할인이 2,000원이라고 생각해보자.

현재까지 발견한 최선의 할인 금액이 7,000원이라면 이 경로는 최대 5,000원까지밖에 만들 수 없다.

따라서 더 깊이 확인해도 최선의 결과를 바꿀 수 없다.

const maximumPossibleDiscount =
  currentDiscount +
  estimateRemainingMaximum(
    coupons,
    index,
    remainingSlots
  );

if (
  maximumPossibleDiscount <=
  best.discountAmount
) {
  return;
}

이 코드는 현재 경로에서 만들 수 있는 최대 할인 금액이 이미 발견한 최선보다 크지 않으면 탐색을 멈춘다.

중요한 것은 estimateRemainingMaximum이 실제 가능한 할인보다 작게 계산되어서는 안 된다는 점이다.

상한을 너무 낮게 계산하면 실제 정답이 있는 경로를 잘못 제거할 수 있다. 그러면 알고리즘은 빨라지지만 정확성을 잃는다.

가지치기의 핵심은 많이 제거하는 것이 아니다.

정답이 포함되지 않았다고 확실하게 설명할 수 있는 경로만 제거하는 것이다.

같은 상태를 반복해서 계산하고 있는지 확인해야 한다

쿠폰의 적용 순서에 따라 같은 상태에 여러 번 도달할 수도 있다.

예를 들어 coupon_a를 먼저 선택하고 coupon_b를 선택한 경우와, coupon_b를 먼저 선택하고 coupon_a를 선택한 경우가 실제로 같은 조합이라면 둘을 따로 확인할 필요가 없다.

조합을 만들 때 항상 원래 인덱스보다 뒤에 있는 쿠폰만 선택하면 순서만 다른 중복을 피할 수 있다.

function search(startIndex, selected) {
  evaluate(selected);

  for (
    let index = startIndex;
    index < coupons.length;
    index += 1
  ) {
    const coupon = coupons[index];

    if (!canStackWithSelected(coupon, selected)) {
      continue;
    }

    selected.push(coupon);
    search(index + 1, selected);
    selected.pop();
  }
}

다음 탐색을 index + 1에서 시작하므로 이미 확인한 쿠폰을 다시 선택하지 않는다.

a → b는 확인하지만 b → a는 별도의 조합으로 만들지 않는다.

이 코드는 쿠폰의 적용 순서가 할인 결과에 영향을 주지 않는다는 정책을 전제로 한다.

만약 비율 할인과 정액 할인의 적용 순서에 따라 결과가 달라진다면 순서를 제거해서는 안 된다.

중복 제거 역시 데이터의 모양만 보고 결정할 수 없다. 서비스에서 두 상태를 실제로 같은 것으로 볼 수 있는지 먼저 확인해야 한다.

완전 탐색은 최적화된 알고리즘을 검증하는 도구가 된다

빠른 알고리즘을 만들었을 때 몇 개의 예제만으로 정확성을 확인하기는 어렵다.

작은 입력에서는 완전 탐색 결과와 비교할 수 있다.

const expected = findBestByExhaustiveSearch(
  coupons,
  order
);

const actual = findBestOptimized(
  coupons,
  order
);

expect(actual.discountAmount).toBe(
  expected.discountAmount
);

완전 탐색 구현은 느리지만 가능한 모든 조합을 확인한다.

최적화된 구현이 같은 입력에서 같은 결과를 반환한다면 정확성을 확인하는 강한 기준이 된다.

여러 작은 입력을 자동으로 만들어 비교할 수도 있다.

for (let index = 0; index < 1000; index += 1) {
  const coupons = createRandomCoupons({
    maxCount: 8,
  });

  const expected =
    findBestByExhaustiveSearch(
      coupons,
      order
    );

  const actual = findBestOptimized(
    coupons,
    order
  );

  expect(actual.discountAmount).toBe(
    expected.discountAmount
  );
}

이 코드는 쿠폰이 최대 8개인 여러 입력을 만들어 두 알고리즘의 결과를 비교한다.

모든 가능한 서비스 데이터를 증명하는 것은 아니지만 개발자가 직접 작성한 몇 개의 예제보다 다양한 조합을 확인할 수 있다.

완전 탐색은 배포할 최종 구현이 아니더라도 테스트를 위한 정답 생성기로 사용할 수 있다.

빠른 알고리즘을 신뢰하려면 비교할 수 있는 단순하고 명확한 기준이 필요하다.

탐색 결과가 맞아도 최종 사용은 다시 검증해야 한다

크리스의 결제 화면에서 가장 좋은 쿠폰 조합을 찾았다고 생각해보자.

const recommendation =
  findBestCombination(
    eligibleCoupons,
    order
  );

이 결과는 계산 시점의 쿠폰과 주문 상태를 기준으로 만든 추천이다.

하지만 크리스가 결제를 확정하는 사이에 쿠폰이 만료되거나 다른 요청에서 사용될 수 있다. 장바구니 상품 가격이나 수량이 변경될 수도 있다.

따라서 추천 결과를 그대로 최종 상태에 반영해서는 안 된다.

const result =
  await couponRepository.redeemCombination({
    couponIds: recommendation.couponIds,
    userId: currentUser.id,
    orderId: order.id,
    redeemedAt: serverNow,
  });

저장소는 최신 상태를 기준으로 다음 조건을 다시 확인해야 한다.

• 모든 쿠폰이 현재 사용자의 것인가?
• 아직 활성 상태인가?
• 남은 사용 횟수가 있는가?
• 아직 만료되지 않았는가?
• 현재 주문에도 적용 가능한가?
• 조합 규칙을 여전히 만족하는가?

함께 사용해야 하는 쿠폰들의 차감과 주문 할인 반영은 하나의 트랜잭션에서 처리해야 한다.

탐색 알고리즘은 최선의 후보를 계산한다. 그러나 공유된 서비스 상태를 안전하게 변경하는 책임까지 자동으로 해결하지는 않는다.

계산 결과와 최종 상태 변경의 책임을 구분해야 한다.

모든 경우를 데이터베이스에서 가져와 서버에서 확인할 필요는 없다

완전 탐색의 대상이 애플리케이션 메모리에 있는 작은 목록이라면 직접 순회해도 된다.

하지만 전체 쿠폰 테이블을 서버로 가져온 뒤 사용자의 후보를 찾는 것은 적절하지 않다.

const allCoupons =
  await couponRepository.findAll();

const userCoupons = allCoupons.filter(
  (coupon) =>
    coupon.recipientId === currentUser.id
);

한 사용자의 쿠폰을 찾기 위해 서비스 전체의 쿠폰을 전송하고 메모리에 저장한다.

먼저 데이터베이스가 검색 조건으로 후보를 줄여야 한다.

SELECT
  id,
  type,
  discount_value,
  stack_group,
  expires_at
FROM coupons
WHERE recipient_id = $1
  AND status = 'ACTIVE'
  AND remaining_uses > 0
  AND expires_at > $2;

이 쿼리는 소유자, 상태, 남은 횟수와 만료 시각을 기준으로 탐색 후보를 제한한다.

그다음 애플리케이션은 현재 주문의 상품 구성과 쿠폰 조합 규칙처럼 복잡한 판단을 수행할 수 있다.

책임	적절한 위치
사용자 소유 쿠폰 조회	데이터베이스 조건 검색
활성 상태와 남은 횟수 필터링	데이터베이스
요청 입력 형식 검증	API 경계
상품별 적용 가능 여부	서비스 또는 도메인 로직
쿠폰 조합 탐색	서비스 로직
최종 상태 재검증	데이터베이스와 서비스 로직
쿠폰 차감과 주문 반영	트랜잭션
추천 결과 표시	UI 상태

완전 탐색을 최적화한다는 것은 재귀 함수만 수정하는 일이 아니다.

데이터가 이동하는 전체 흐름에서 어느 단계가 후보를 줄일 수 있는지 찾는 일이다.

완전 탐색을 선택하기 전에 물어봐야 할 질문

실제 서비스에서 가능한 모든 경우를 확인하려 할 때 다음 질문을 점검할 수 있다.

1. 무엇을 하나의 후보 또는 선택으로 보는가?
2. 선택할 수 있는 후보는 최대 몇 개인가?
3. 각 후보에는 선택과 제외 외에 다른 결정이 있는가?
4. 선택 순서에 따라 결과가 달라지는가?
5. 가능한 전체 경우의 수는 어떻게 증가하는가?
6. 하나의 경우를 평가하는 데 어떤 계산과 조회가 필요한가?
7. 전체 탐색을 요청마다 실행하는가, 한 번만 실행하는가?
8. 결과를 만들어야 하는 제한 시간은 얼마인가?
9. 입력 크기가 작다면 완전 탐색이 가장 단순하고 안전한 선택인가?
10. 탐색 전에 제외할 수 있는 만료, 권한과 상태 조건이 있는가?
11. 후보를 줄이는 데 사용할 데이터의 Source of Truth는 어디에 있는가?
12. 최대 선택 개수처럼 탐색 깊이를 제한하는 정책이 있는가?
13. 서로 함께 사용할 수 없는 선택을 미리 제거할 수 있는가?
14. 순서만 다르고 결과가 같은 중복 상태가 있는가?
15. 현재 경로가 최선이 될 수 없음을 증명할 상한이나 하한이 있는가?
16. 가지치기가 실제 정답을 제거하지 않는다고 설명할 수 있는가?
17. 개별적으로 좋은 선택이 전체적으로도 최선이라는 근거가 있는가?
18. 근거 없이 빠른 선택 방법으로 바꾸고 있지는 않은가?
19. 작은 입력에서 완전 탐색을 정답 기준으로 사용할 수 있는가?
20. 최적화된 결과를 완전 탐색 결과와 비교했는가?
21. 탐색 후 실제 상태가 바뀌기 전에 최신 조건을 다시 검증하는가?
22. 동시에 요청이 들어와도 선택한 쿠폰이 한 번만 사용되는가?
23. 현재 병목은 조합 계산인가, 데이터 조회와 전송인가?
24. 서비스의 제약이 바뀌면 언제 다른 알고리즘이 필요한가?

이 질문에 답하면 완전 탐색을 그대로 사용할지, 후보를 먼저 줄일지, 가지치기를 추가할지, 전혀 다른 해결 원리를 찾아야 할지 판단할 수 있다.

완전 탐색은 정답을 아는 가장 단순한 출발점이다

완전 탐색은 가능한 경우를 모두 확인하므로 입력이 커질수록 비용이 빠르게 증가할 수 있다.

그렇다고 무조건 피해야 하는 낮은 수준의 방법은 아니다.

입력 크기가 작다면 가장 이해하기 쉽고 정확한 해결책일 수 있다. 더 빠른 방법이 필요하더라도 완전 탐색은 문제의 전체 선택 공간을 이해하게 해준다. 또한 최적화된 알고리즘의 결과를 비교할 수 있는 기준을 제공한다.

실제 개선 과정은 다음과 같이 진행할 수 있다.

1. 가능한 선택과 정답의 기준을 명확히 정의한다.
2. 작은 입력에서 모든 경우를 확인하는 기준 구현을 만든다.
3. 전체 경우의 수와 평가 비용을 계산한다.
4. 탐색 전에 유효하지 않은 후보를 제거한다.
5. 서비스 규칙으로 불가능한 선택을 만들지 않는다.
6. 중복된 상태를 다시 확인하지 않는다.
7. 최선이 될 수 없는 경로만 근거를 가지고 중단한다.
8. 최적화된 결과를 기준 구현과 비교한다.
9. 실제 운영 규모에서 처리 시간과 자원을 측정한다.
10. 최종 상태 변경 전에는 최신 데이터를 다시 검증한다.

완전 탐색은 무식하게 모든 경우를 확인하는 방법이 아니다. 정답이 존재할 수 있는 전체 범위를 드러내고, 정확성의 기준을 만든 뒤 정답이 될 수 없는 경우를 근거 있게 제거하는 문제 해결의 출발점이다.

처음부터 가장 빠른 해결책을 떠올리지 못해도 괜찮다.

먼저 확실하게 맞는 방법을 만들고, 어디에서 비용이 증가하는지 확인하며, 제거해도 되는 경우의 이유를 하나씩 찾는 편이 안전하다. 이 과정에서 문제의 구조와 서비스의 실제 규칙도 더 분명해진다.

다음 글에서는 문제 분해가 단순히 큰 함수를 여러 작은 함수로 나누는 일이 아니라, 복잡한 문제를 독립적으로 판단할 수 있는 작은 결정들로 바꾸는 방법인 이유를 살펴본다.