Algorithms - 가중치 랜덤 알고리즘(랜덤 쿠폰 뽑기)

배경

커머스 플랫폼 개발에서 랜덤 쿠폰 지급 이벤트는 빈번히 요구되는 기능이다. 이러한 이벤트에서는 일반적으로 할인율이 낮은 쿠폰일수록 당첨 확률이 높고, 할인율이 높은 쿠폰일수록 당첨 확률이 낮다. 이를 구현하기 위해 각 쿠폰에 가중치를 부여하고, 랜덤하게 쿠폰을 발행하는 가중치 랜덤 알고리즘(Weighted Random Algorithm)이 사용된다. 이번 포스트에서는 이 알고리즘을 알아보고 실제 구현, 테스트까지 진행해보자. 

 

가중치 랜덤 알고리즘(Weighted Random Algorithm)

가중치 랜덤 알고리즘은 각 요소에 가중치를 할당해서 선택 확률을 조절하여 선택하는 알고리즘이다.

가중치가 높을수록 선택될 확률이 높고 가중치가 낮을수록 선택될 확률이 낮다.

 

사용 사례

메이플스토리 아이템 강화에 성공해서 기뻐하는 모습 (출처: 유튜브 팡이요)

• 게임 개발: 디아블로 시리즈를 참 좋아했는데, '폐지 줍기 게임'으로 유명하다. 이 게임의 매력은 더 강력한 아이템을 얻기 위해 끊임없이 몬스터를 사냥하고 아이템을 수집하는 데 있다. 하지만 대부분 쓰레기 아이템들만 드랍되고 강력한 아이템은 정말 운이 좋아야 볼 수 있었다. 한국 게임에서는 대표적으로 메이플 스토리의 아이템 강화가 있다. 강화 단계가 높아질수록 강화에 성공할 확률이 낮아지고 최악의 상황에서는 아이템이 파괴될 수 있다. 이러한 아이템 드랍 시스템이나 강화 시스템을 구현하는 데 가중치 랜덤 알고리즘이 효과적으로 활용될 수 있다. 이런 확률을 잘 조절해서 게임의 재미와 밸런스를 동시에 유지할 수 있다.(간만에 게임 이야기를 하다보니 말이 길어졌다ㅋㅋ)
• 로드 밸런싱: 여러 서버로 들어오는 요청을 분배할 때 사용될 수 있다. 각 서버의 성능, 용량, 부하 상태에 따라 요청을 분배할 수 있다. 예를 들어, 특정 서버의 CPU 사용률이 급격히 증가하면 해당 서버로의 요청 분배 가중치를 낮추고, 다른 서버의 가중치를 높여서 시스템을 안정적으로 운영할 수 있다.
• 추천 시스템: 음악, 영화, 상품 추천 등 널리 사용된다. 예를 들어, 넷플릭스에서 사용자가 최근 시청한 컨텐츠와 유사한 장르의 영화에 높은 가중치를 주어 추천할 확률을 높인다. 또는, 크리스마스와 같은 특정 시즌에 맞는 컨텐츠에도 일시적으로 가중치를 높여 추천에 반영할 수 있다.
• 온라인 광고 시스템: 광고비, 클릭률, 전환율, 사용자의 관심사와 광고 내용 연관성 등 다양한 요소를 종합적으로 계산하여 가중치를 할당하고, 이를 기반으로 알고리즘이 실시간으로 표시할 광고를 선택할 수 있다.
• 랜덤 쿠폰 이벤트: 할인율이 다른 쿠폰들에 가중치를 다르게 주어 가중치에 따라서 랜덤하게 발행할 수 있다. 

 

구현

구현은 생각보다 간단하다. 알고리즘 흐름은 다음과 같다.

 

흐름

1. 가중치를 기준으로 내림차순 정렬
2. 각 요소의 가중치 총합(Total Weight)을 계산한다.
3. 0부터 Total Weight 사이의 난수(rnd)를 생성한다.
4. 난수(rnd)가 0보다 작거나 같은 값이 될 때까지 각 요소의 가중치를 난수에 누적 차감시킨다.
5. 난수(rnd)가 0보다 작거나 같은 값이 되면 해당 요소를 선택한다.

출처: https://eli.thegreenplace.net/2010/01/22/weighted-random-generation-in-python

 

이제 위에 정리한 흐름대로 코드로 구현해보자. 예시 코드는 Java로 구현했다.

Coupon 클래스는 쿠폰명(title), 가중치(weight)를 속성으로 가지고 있다.

public Coupon getWeightRandomCoupon(List<Coupon> couponList) {
    // 가중치를 기준으로 내림차순 정렬
    couponList.sort(Comparator.comparing(Coupon::getWeight).reversed());
    
    // 1 ~ TotalWeight 사이의 랜덤값
    int totalWeight = couponList.stream().mapToInt(Coupon::getWeight).sum();
    double random = Math.ceil(Math.random() * totalWeight);
    
    /**
     * random에 가중치를 누적 차감하며 루프
     * random 값이 0보다 작거나 같으면 해당 쿠폰 발행
     */
    for (Coupon coupon : couponList) {
        random -= coupon.getWeight();
        if (random <= 0) {
            return coupon;
        }
    }
    return null;
}

 

1억개의 랜덤 쿠폰을 발행해서 실제 가중치대로 쿠폰이 발행되는지 테스트해보았다.

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        List<Coupon> couponList = Arrays.asList(
            new Coupon("1만원 쿠폰", 50),
            new Coupon("2만원 쿠폰", 30),
            new Coupon("5만원 쿠폰", 19),
            new Coupon("100만원 쿠폰", 1)
            );

        // 랜덤 쿠폰 테스트 (1억회 반복)
        Map<Coupon, Integer> couponCount = new HashMap<>();
        int count = 100000000;
        for (int i = 0; i < count; i++) {
            // 쿠폰이 등장할 때마다 해당 쿠폰 등장 횟수 +1
            Coupon randomCoupon = main.getWeightRandomCoupon(couponList);
            couponCount.put(randomCoupon, 1 + couponCount.getOrDefault(randomCoupon, 0));
        }
        
        // 쿠폰 등장 확률 출력
        for (Entry<Coupon, Integer> e : couponCount.entrySet()) {
            System.out.printf("%s 등장 확률: %d%%\n", e.getKey().getTitle(), Math.round(((double) e.getValue() / (double) count) * 100));
        }
    }

    public Coupon getWeightRandomCoupon(List<Coupon> couponList) {
        // 가중치를 기준으로 내림차순 정렬
        couponList.sort(Comparator.comparing(Coupon::getWeight).reversed());
        
        // 1 ~ TotalWeight 사이의 랜덤값
        int totalWeight = couponList.stream().mapToInt(Coupon::getWeight).sum();
        double random = Math.ceil(Math.random() * totalWeight);

        /**
         * random에 가중치를 누적 차감하며 루프
         * random 값이 0보다 작거나 같으면 해당 쿠폰 발행
         */
        for (Coupon coupon : couponList) {
            random -= coupon.getWeight();
            if (random <= 0) {
                return coupon;
            }
        }
        return null;
    }

    @Getter
    @ToString
    @AllArgsConstructor
    static class Coupon {
        private String title;	// 쿠폰명
        private int weight;     // 가중치
    }
}

가중치에 맞게 쿠폰이 등장했다

위 예시를 통해 부여된 가중치에 따라 쿠폰이 등장한 것을 확인할 수 있다. 하지만 실제 업무 환경에서는 이보다 훨씬 복잡한 요구사항이 존재할 수 있기 때문에 구현 과정이 더욱 복잡해질 수 있다. 또한 더 효율적으로 동작하는 다양한 가중치 랜덤 알고리즘들이 있다. 이에 대해 더 자세히 알고 싶다면, 아래 참조 링크들을 확인하길 바란다. 

 

참조

https://dev.to/jacktt/understanding-the-weighted-random-algorithm-581p

Understanding the Weighted Random Algorithm

https://blog.naver.com/occidere/222024179048

가중치 랜덤 알고리즘 - 누적확률값 방식

https://eli.thegreenplace.net/2010/01/22/weighted-random-generation-in-python

Weighted random generation in Python - Eli Bendersky's website

https://blog.bruce-hill.com/a-faster-weighted-random-choice

A Faster Weighted Random Choice