🏸배드민턴 대진표 매칭 알고리즘 상세 문서

📋 목차

개요
지원하는 경기 방식
매칭 알고리즘 종류
용병 시스템
매칭 품질 보장 시스템
매칭 생성 프로세스
성능 최적화
품질 검증 지표
향후 개선 계획

📋개요

이 문서는 배드민턴 동호회 대진표 작성 시스템에서 구현된 매칭 알고리즘들을 상세히 설명합니다. 시스템은 다양한 매칭 방식을 지원하여 공정하고 균형잡힌 경기를 생성합니다.

🎯지원하는 경기 방식

1. 자체대회 (현재 구현됨)

모든 선수가 설정된 게임 수만큼 경기 참여
4가지 매칭 알고리즘 지원
용병 시스템을 통한 선수 수 조정

2. 청백전 (향후 구현 예정)

팀 대항전 방식
현재는 준비 중 상태

🔧매칭 알고리즘 종류

1. 랜덤 매칭 (Random Matching)

개념: 완전 무작위로 선수들을 매칭하는 방식

알고리즘 흐름:

1. 경기가 필요한 선수들을 필터링 2. Fisher-Yates 셔플 알고리즘으로 선수 순서 무작위화 3. 4명씩 그룹을 만들어 매치 생성 4. 중복 페어링 최소화를 위한 검증

특징:

가장 단순하고 빠른 방식
예측 불가능한 매칭으로 재미 요소 증가
실력 차이가 클 수 있음

selectPlayersForRandomMatch(availablePlayers, usedPairings) {
    const shuffled = MatchingUtils.shuffleArray(availablePlayers);
    
    for (let i = 0; i < shuffled.length - 3; i++) {
        const candidates = shuffled.slice(i, i + 4);
        if (this.isValidPairing(candidates, usedPairings)) {
            return candidates;
        }
    }
    
    return shuffled.slice(0, 4);
}

2. 비슷한 급수 매칭 (Grade-Based Matching) - 🎯 출전 간격 고려 알고리즘

개념: 소수 급수 우선 처리 + 선수 출전 간격 및 연속 출전 방지를 종합적으로 고려하는 지능형 매칭 알고리즘

💡 핵심 아이디어:

"소수 급수일수록 먼저 처리해야 같은 급수 매칭 기회를 잃지 않는다!"

문제: 많은 선수 급수부터 처리 → 적은 선수 급수는 나중에 혼합 매칭
해결: 적은 선수 급수부터 처리 → 모든 급수가 공평한 매칭 기회

🎯 소수 급수 우선 알고리즘:

1단계: 급수별 선수 수 분석 및 정렬 모든 급수를 선수 수 기준으로 오름차순 정렬 → D급 2명 → C급 3명 → A급 6명 → B급 8명 2단계: 소수 급수부터 순차 처리 D급 2명: 4명 미만으로 같은 급수 매칭 불가 (대기) C급 3명: 4명 미만으로 같은 급수 매칭 불가 (대기) A급 6명: A급 매치 1개 생성 (4명), A급 2명 남음 B급 8명: B급 매치 2개 생성 (8명 완전 소진) 3단계: 남은 선수들로 혼합 매칭 D급 2명 + C급 3명 + A급 2명 → 혼합 매치 생성

📊 기존 방식과의 비교:

시나리오	기존 (다수 우선)	개선 (소수 우선)	개선 효과
A급 8명, B급 6명, C급 2명	A급 완전소진 → C급 혼합매칭	C급 먼저 고려 → A급 처리	C급 보호
A급 12명, B급 4명, C급 4명	A급 우선 → B,C급 나중	B,C급 먼저 → A급 나중	B,C급 완전매칭
각 급수 4명씩	��서대로 처리	모든 급수 동등 처리	100% 같은급수

🎯 알고리즘의 장점:

공정성: 모든 급수가 동등한 매칭 기회
단순성: 복잡한 전략 선택 없이 일관된 처리
효율성: 소수 급수 보호로 전체 매칭 품질 향상
예측 가능성: 항상 동일한 방식으로 처리

// 실제 처리 예시
// 19명 참가: A급 8명, B급 7명, C급 3명, D급 1명

📊 급수별 현황: {
  D급: {count: 1, completeMatches: 0, remainder: 1},
  C급: {count: 3, completeMatches: 0, remainder: 3}, 
  B급: {count: 7, completeMatches: 1, remainder: 3},
  A급: {count: 8, completeMatches: 2, remainder: 0}
}

🎯 소수 급수 우선 전략으로 같은 급수 매칭 생성
  급수별 선수 현황 (소수 순):
    D급: 1명 (완전매치 0개, 나머지 1명)
    C급: 3명 (완전매치 0개, 나머지 3명)  
    B급: 7명 (완전매치 1개, 나머지 3명)
    A급: 8명 (완전매치 2개, 나머지 0명)

  D급: 1명 (4명 미만으로 같은 급수 매칭 불가)
  C급: 3명 (4명 미만으로 같은 급수 매칭 불가)
  B급 7명으로 소수 우선 매칭 시작
    ✅ B급 매치 1: [김철수(B급), 이영희(B급), 박민수(B급), 최지영(B급)]
  A급 8명으로 소수 우선 매칭 시작  
    ✅ A급 매치 1: [정수현(A급), 강민지(A급), 윤서준(A급), 한예린(A급)]
    ✅ A급 매치 2: [송민호(A급), 김다은(A급), 이준석(A급), 박서연(A급)]

🎯 2단계: 혼합 급수 매칭 시작
  매치 4: [류승민(B급), 차은지(B급), 신예은(C급), 홍길동(C급)] - 보통 (2등급 차이)

결과: 총 4개 매치 중 3개가 같은 급수 매치 (75%)

3. 비슷한 실력 매칭 (Real Skill-Based Matching)

개념: 실제 실력(skill 필드)을 기준으로 비슷한 실력의 선수들끼리 매칭

급수와 실력의 차이:

급수(grade): 등록 시 설정한 공식 급수
실력(skill): 실제 경기력을 반영한 조정 가능한 실력

알고리즘 흐름:

1. 선수들을 실력별로 그룹화 (skill 필드 우선 사용) 2. 같은 실력 그룹 내에서 우선 매칭 3. 부족한 경우 인접 실력 그룹과 매칭 4. 중복 페어링 최소화 검증

특징:

실제 실력을 더 정확히 반영
급수와 실력이 다른 선수들 고려
더 세밀한 밸런스 조정 가능

realSkillBasedMatching(players, tournament) {
    console.log('비슷한 실력 매칭 시작');
    
    // 실력별로 선수들을 그룹화
    const skillGroups = this.groupPlayersBySkill(players);
    
    // 실력이 비슷한 선수들끼리 우선 매칭
    return this.createSkillBasedMatches(skillGroups, tournament);
}

4. 랜덤 밸런스 매칭 (Balanced Random Matching)

개념: 무작위 선택 후 팀 실력을 균형있게 조정하는 방식

팀 밸런스 계산:

// 팀 실력 계산
calculateTeamStrength(team) {
    return team.reduce((total, player) => {
        if (player.isMercenary) return total + 2.5; // 용병은 평균 실력
        return total + this.getSkillScore(player.skill);
    }, 0);
}

// 밸런스 차이 계산
calculateBalanceDifference(team1, team2) {
    const strength1 = this.calculateTeamStrength(team1);
    const strength2 = this.calculateTeamStrength(team2);
    return Math.abs(strength1 - strength2);
}

밸런스 조정 알고리즘:

1. 초기 4명을 2팀으로 나눔 2. 최대 100회 반복하여 최적 조합 탐색 3. 각 반복에서 두 팀 간 선수 교환 시도 4. 실력 차이가 줄어들면 해당 조합 채택 5. 최종적으로 가장 균형잡힌 팀 구성 반환

특징:

무작위성과 균형성을 동시에 추구
각 경기가 박진감 있게 진행
가장 복잡하지만 가장 공정한 방식

4. 커스텀 매칭 (Custom Matching)

개념: 사용자가 직접 매칭을 설정하는 방식

특징:

완전한 사용자 제어
특별한 이벤트나 시나리오에 적합
현재는 기본 랜덤 매칭으로 동작

🛡️ 경기수 보장 시스템:

💯 "모든 선수가 최소 경기수를 반드시 보장받는다!"

1단계: 용병 자리를 경기수 부족 선수로 우선 교체
2단계: 추가 라운드 생성으로 부족한 경기수 보충
3단계: 최종 검증으로 모든 선수 경기수 확인
우선순위: 경기수가 가장 부족한 선수부터 우선 배정

🔄 용병 교체 시스템:

용병 → 일반선수 교체 우선순위 1. 경기수 부족이 가장 심한 선수 우선 2. 같은 부족 수준이면 휴식 간격이 긴 선수 우선 3. 모든 용병 자리를 경기수 부족 선수로 교체 추가 라운드 생성 4명 이상: 정상 매치 구성 4명 미만: 용병으로 매치 구성하여 경기수 보장

✅ 완전한 통합 알고리즘의 장점:

경기수 100% 보장: 모든 선수가 최소 경기수 달성
선수 피로도 최소화: 적절한 휴식으로 컨디션 유지
공정한 출전 기회: 모든 선수가 균등한 간격으로 출전
급수 매칭 품질: 소수 급수 보호 + 같은 급수 매칭
관전 재미: 연속 출전 방지로 관전자도 휴식

// 경기수 보장 시스템 실행 예시
🎯 경기수 보장 시스템 시작
⚠️ 경기수 부족 선수 3명 발견:
  김철수(A급): 2/3게임 (1게임 부족)
  이영희(B급): 1/3게임 (2게임 부족)  
  박민수(C급): 2/3게임 (1게임 부족)

🔄 용병 → 경기수 부족 선수 교체 시작
  매치 match_3: 용병 → 이영희(B급) 교체
  매치 match_5: 용병 → 김철수(A급) 교체
✅ 용병 교체 완료: 2명 교체

➕ 추가 매치 생성 시작
  추가매치 선수 선택: 경기수 부족 우선
    박민수(C급): 1게임부족, 3간격
    용병: 보충용
  R6 추가매치 1: [박민수(C급), 용병, 용병, 용병]
✅ 추가 매치 생성 완료: 1개 매치 추가

🔍 최종 경기수 검증
✅ 모든 선수가 목표 경기수 3게임 달성

🤖용병 시스템 (Mercenary System)

용병 생성 조건

선수 수가 4의 배수가 아닐 때 자동 생성
필요한 용병 수 = (4 - (선수 수 % 4)) % 4

용병 특성

이름: "용병1", "용병2", ... 형태
성별: 부족한 성별로 자동 설정
실력: B급 (평균 실력)
식별: isMercenary: true 플래그

용병 최적화 알고리즘

1단계: 용병 배치 최적화

1. 각 라운드별로 용병 분산 배치 2. 연속 라운드 출전 방지 3. 같은 라운드 내 용병끼리 매칭 최소화

2단계: 용병 교체 최적화

1. 실제 선수 중 교체 가능한 후보 탐색 2. 교체 조건 검증: - 해당 라운드에 미배정 - 앞뒤 라운드에도 미배정 (연속 출전 방지) - 지정 경기수 이내 (최대 +1게임까지 허용) - 성별 매칭 조건 충족 3. 최적 후보로 용병 교체

📊매칭 품질 보장 시스템

1. 중복 페어링 방지

// 사용된 페어링 추적
recordUsedPairings(players, usedPairings) {
    for (let i = 0; i < players.length; i++) {
        for (let j = i + 1; j < players.length; j++) {
            const pairKey = this.getPairKey(players[i].id, players[j].id);
            usedPairings.add(pairKey);
        }
    }
}

// 페어링 중복도 계산
countPairingOverlap(players, usedPairings) {
    let overlap = 0;
    for (let i = 0; i < players.length; i++) {
        for (let j = i + 1; j < players.length; j++) {
            const pairKey = this.getPairKey(players[i].id, players[j].id);
            if (usedPairings.has(pairKey)) {
                overlap++;
            }
        }
    }
    return overlap;
}

2. 연속 라운드 출전 방지

// 선수 스케줄 추적
playerSchedule[playerId] = [라운드1, 라운드3, 라운드5, ...];

// 연속성 검증
const prevRound = match.round - 1;
const nextRound = match.round + 1;
if (playerRounds.includes(prevRound) || playerRounds.includes(nextRound)) {
    return false; // 연속 출전이므로 제외
}

3. 공평한 경기 수 배분

// 게임 수 추적
playerGameCount[playerId] = 현재_경기_수;

// 목표 게임 수 달성 우선순위
const needsGames = players.filter(p => playerGameCount[p.id] < gamesPerPlayer);
const sortedByGames = needsGames.sort((a, b) => 
    playerGameCount[a.id] - playerGameCount[b.id]
);

🎮매칭 생성 프로세스

[선수 목록] ↓ [선수 수 조정 (4의 배수)] ↓ [성별 필터링 적용] ↓ [매칭 방식 선택] ↓ ┌─────────────────────────────────────┐ │ 1단계: 이상적인 매치 생성 │ │ - 중복 페어링 최소화 │ │ - 매칭 방식별 알고리즘 적용 │ │ - 목표 게임 수 달성 │ └─────────────────────────────────────┘ ↓ ┌─────────────────────────────────────┐ │ 2단계: 강제 매치 생성 │ │ - 게임 수 부족한 선수 우선 배정 │ │ - 최소 게임 수 보장 │ └─────────────────────────────────────┘ ↓ ┌─────────────────────────────────────┐ │ 3단계: 라운드 및 코트 배정 │ │ - 연속 출전 방지 │ │ - 코트별 균등 분배 │ └─────────────────────────────────────┘ ↓ ┌─────────────────────────────────────┐ │ 4단계: 용병 최적화 │ │ - 용병 분산 배치 │ │ - 실제 선수로 교체 │ └─────────────────────────────────────┘ ↓ [최종 대진표 생성]

📈성능 최적화

1. 알고리즘 복잡도

매칭 방식	시간 복잡도	특징
랜덤 매칭	O(n)	가장 빠름
급수 매칭	O(n log n)	정렬 필요
실력 매칭	O(n log n)	그룹화 및 정렬 필요
밸런스 매칭	O(n²)	최적화 과정 포함

2. 메모리 사용 최적화

// 사용된 페어링을 Set으로 관리하여 O(1) 검색
const usedPairings = new Set();

// 선수별 게임 수를 객체로 관리
const playerGameCount = {};

// 선수별 스케줄을 배열로 관리
const playerSchedule = {};

3. 조기 종료 조건

// 완벽한 매치를 찾으면 즉시 반환
if (minPairingOverlap === 0) {
    return this.balanceMatch(bestCombination, matchingType);
}

// 최대 시도 횟수 제한
const maxAttempts = players.length * gamesPerPlayer * 3;

🔍품질 검증 지표

1. 매칭 품질 지표

중복 페어링 비율: 전체 페어링 중 중복된 비율
실력 균형도: 팀 간 실력 차이의 평균
게임 수 편차: 선수별 게임 수의 표준편차

2. 시스템 성능 지표

매칭 생성 시간: 대진표 생성에 소요되는 시간
용병 교체율: 전체 용병 중 실제 선수로 교체된 비율
연속 출전 방지율: 연속 라운드 출전이 방지된 비율

🚀향후 개선 계획

1. 청백전 구현

// 팀 대항전 매칭 알고리즘 (구현 예정)
generateTeamVsTeamMatches(redTeam, whiteTeam, tournament) {
    // 팀별 선수 실력 분석
    // 균형잡힌 대진 생성
    // 팀 점수 시스템 적용
}

2. 고급 밸런싱 알고리즘

유전 알고리즘 적용
머신러닝 기반 실력 예측
과거 경기 결과 반영

3. 실시간 매칭 조정

경기 중 실시간 밸런스 조정
동적 용병 교체
적응형 매칭 시스템

📚참고 자료

핵심 클래스

BracketGenerator: 대진표 생성 메인 클래스
MatchingUtils: 매칭 관련 유틸리티
DateUtils: 날짜 관련 유틸리티

🏸배드민턴 대진표 매칭 알고리즘 상세 문서

📋 목차

📋개요

🎯지원하는 경기 방식

1. 자체대회 (현재 구현됨)

2. 청백전 (향후 구현 예정)

🔧매칭 알고리즘 종류

1. 랜덤 매칭 (Random Matching)

알고리즘 흐름:

특징:

2. 비슷한 급수 매칭 (Grade-Based Matching) - 🎯 출전 간격 고려 알고리즘

💡 핵심 아이디어:

🎯 소수 급수 우선 알고리즘:

📊 기존 방식과의 비교:

🎯 알고리즘의 장점:

3. 비슷한 실력 매칭 (Real Skill-Based Matching)

급수와 실력의 차이:

알고리즘 흐름:

특징:

4. 랜덤 밸런스 매칭 (Balanced Random Matching)

팀 밸런스 계산:

밸런스 조정 알고리즘:

특징:

4. 커스텀 매칭 (Custom Matching)

특징:

🛡️ 경기수 보장 시스템:

🔄 용병 교체 시스템:

✅ 완전한 통합 알고리즘의 장점:

🤖용병 시스템 (Mercenary System)

용병 생성 조건

용병 특성

용병 최적화 알고리즘

1단계: 용병 배치 최적화

2단계: 용병 교체 최적화

📊매칭 품질 보장 시스템

1. 중복 페어링 방지

2. 연속 라운드 출전 방지

3. 공평한 경기 수 배분

🎮매칭 생성 프로세스

📈성능 최적화

1. 알고리즘 복잡도

2. 메모리 사용 최적화

3. 조기 종료 조건

🔍품질 검증 지표

1. 매칭 품질 지표

2. 시스템 성능 지표

🚀향후 개선 계획

1. 청백전 구현

2. 고급 밸런싱 알고리즘

3. 실시간 매칭 조정

📚참고 자료

관련 파일

핵심 클래스