2016 년 크루세이더 퀘스트 에 ' 신수 의 둥지 ' 를 대체 하 고 새롭 게 생긴 파밍 컨텐츠 ' 탐험 ' 간략히 설명 하 자면 , 용사 조합 을 짜 서 탐 험지 에 ' 파견 ( 실제로 는 기다리 는 것 외 에 아무것 도 하 지 않 는다 ) ' 을 보내 면 최고 등급 인 6 성 용사 의 능력 치 를 추가 적 으로 올려 주 는 ' 열매 ' 와 약간 의 ' 골드 ' 를 얻 을 수 있 는 시스템 이 다 .   또한 ,   보너스 로 주어지 는 10 개 의 조건 중 n 개 의 조건 을 만족 하 면 추가 보너스 가 주어진다 . 각 탐 험지 의   보너스 조건 은 다음 중 에서 무작위 로 10 개 조건 이 선정 되 는 듯 하 다 . < 용사 클래스 >   워리 어 , 팔라딘 , 아처 , 헌터 , 위 자드 , 프리스트 < 레어 리티 >   전설 용사 , 계약 전용 용사 , 일반 승급 용사 < 성별 >   남성 , 여성 , 무성 ( ?   무성 용사 가 있 는지 는 확실히 모른다 ) < 등급 >   4 성 , 5 성 , 6 성 < 세력 >   그란 시아 제국 , . .. ( 중략 ) . .. 총 7 개 세력 존재 . 총 5 개 분류 22 개 속성 이 존재 . 또한 각 용사 들 은 각 분류 들 에 대하 여 1 개 씩 의 속성 을 가지 고 있 다 . 즉 각 탐 험지 의 보너스 조건 에 어떤 용사 는 자신 의 5 개 속성 모두 가 보너스 조건 에 부합 할 수 도 있 고 , 어떤 용사 는 단 하나 의 속성 도 보너스 조건 에 부합 하 지 않 을 수 있 는 것 이 다 .   조금 만 머리 를 굴리 면 수동 으로 조합 을 짜 는 것 정도 는 어렵 지 않 게 할 수 있 지만 ,   직접 조합 을 짜 는 걸   귀찮 아 할 유저 들 이 많 을 것 으로 예상 했 는지 개발 측 에서 는   자동 으로 조합 을 짜 는   ' 추천 용사 ' 기능 을 만들 어 넣 은 듯 하 다 . 문제 ) 주어진 10 개 의 속성 을 최대한 만족 하 는 5 명 의 최적 용사 조합 을 구성 하 라 . 해결 방법 에 대해 접근 해 보 기 위해 우선 수동 으로 용사 조합 을 짜 보 았 다 . 최대한 적 은 수 의 용사 로 10 개 조건 을 빠르 게 채우 고 , 나머지 는 최대한 부합 하 지 않 는 용사 들 로 채워 다른 탐 험지 에 대비 하 고자 한다 . 광휘 의 레온 :   워리 어 , 전설 용사 , 남성 , 6 성 - 총 4 개 속성 만족 네스 군 장교 유리아 : 프리스트 , 계약 전용 용사 , 여성 , 6 성 ( 이미 레온 에서 만족 ) - 3 개 속성 추가 만족 신사 까마귀 : 헌터 , 일반 승급 용사 , 남성 - 3 개 속성 추가 만족 단 3 명 의 용사 로 10 개 속성 을 모두 채웠 다 . 나머지 는 최대한 보너스 조건 에 부합 하 지 않 는 용사 들 로 채워 넣 으면 끝 . 이러 한 해결 방법 은 눈앞 에 보이 는 최선 의 해결책 부터 일단 풀 고 보 는 방법 으로 ,   탐욕 알고리즘 ( Greedy Algorithm ) 이 라는 이름 으로 널리 알려져 있 다 . 이번 엔 한 번 자동 으로 용사 조합 을 짜 보 았 다 . 레온 , 유리아 는 수동 조합 과 결과 가   같 았 고 까마귀 대신 사령관 스파이 로 ( 까마귀 와 같이 남성 , 헌터 , 일반 승급 ) 이 들어갔 다 . 나머지 는 크 게 상관 없 는 용사 들 . 수동 조합 과 마찬가지 로 단 3 명 의 용사 로 10 개 조건 을 채웠 다 . ( 잉여 용사 두 명 을 뺐 는데 도 10 개 조건 모두 만족 ) 자동 용사 조합 역시 탐욕 알고리즘 과 비슷 한 방법 을 사용 해 추천 용사 조합 을 짜 는 듯 하 다 . 추정 해 보 면 1 )   용사 n 명 에 대하 여 보너스 조건 과   일치 하 는 속성 이 몇 개 존재 하 는 지 를 비교 하 여 ' 만족 도 ' 를 메모 한다 . 2 ) 구해진 ' 만족 도 ' 를 바탕 으로 탐욕 알고리즘 등 을 사용 하 여 추천 용사 조합 을 선정 한다 . 의 방법 으로 추천 조합 을 짜 는 것 이 아닌가 생각 된다 . ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ탐욕 알고리즘 을 어떻게 적용 했 을까 ? 어떤 알고리즘 을 적용 했 을까 ? 일단 탐욕 알고리즘 하 면 생각 해낼 수 있 는 여러 대표 알고리즘 들 이 존재 한다 .   - 다익스트라 ( 최소 비용 경로 ) , 프림 ( 최소 spanning tree 문제 ) , etc . ... 하지만 해당 알고리즘 들 은 네트워크 의 각 변의 흐름 이 fixed , 즉 한 변 을 택하 여 경로 를 진행 하 여도 다른 변의 흐름 에 변화 를 주 지 않 는 네트워크 에서 정의 가 가능 하 다 . 일단 이것 을 ' 독립 ' 이라고 부르 도록 하 자 .   ( 그림 출처 : 위키백과 ) 우리 는 null 용사 를 출발점 으로 하 여 각 용사 를 노드 로 , 각 용사 의 만족도 를 변의 흐름 ( 가중치 ) 로 하 는 네트워크 로 표현 해 줄 수 있 는데 , 문제 는 한 용사 를 선택 해서 몇몇 속성 들 이 채워 지 게 되 면 다른 용사 들 의 만족도 는 전부 변하 게 된다 . 즉 각 변의 흐름 은 독립 이 아니 다 . 네스 군 장교 유리아 - 레온 을 고르 기 전 에 는 만족도 가 4 였으나 레온 을 고른 후 에 는 만족도 가 3 ( 이미 6 성 용사 조건 이 만족 되 었 으므로 여성 , 계약 전용 , 프리스트 의 3 속성 만 이 남 았 다 ) 또 , 한 용사 를 고르 게 되 면 그 다음 용사 를 고르 는 경우 의 수 는 용사 의 전체수 를 n 이 라고 할 때 n - 1 이 다 . 즉 이 말 은 용사 네트워크 를 짰 을 때 다음 과 같 은 그래프 가 된다는 이야기 이 다 . 이렇게 될 경우 n 이 수백 수천 으로 커지 면 단순 배열 메모리 에서 시간 복잡도 가 O ( n ^ 2 ) 인 다익스트라 알고리즘 의 특성 상 계산 횟수 가 어마어마 하 게 커지 게 된다 . 그리고 다익스트라 알고리즘 은 시작점 과 끝점 이 존재 하 는데 , 지금 풀 고자 하 는 알고리즘 은 끝점 은 없 고 최대한 짧 은 경로 로 만족 도 총합 10 을 채우 는 게 목적 이 다 . 사용 하 기 에 는 무리 가 많 다 . ( 차라리 다른 탐욕 알고리즘 을 적용 하 는 게 더 속편 하 다 ) 탐욕 알고리즘 의 의의 만 을 남기 고 아예 새로운 알고리즘 을 정의 해 보 자 . < CQ ' s Algorithm > 0 .   depth = 0 , list = [ 속성 조건 1 ~ 속성 조건 10 ] , stack = [ 빈 리스트 ] 1 .   전체 용사 들 을 대상 으로 만족도 를 계산 하 고 그 만족도 를 각 용사 마다 label 이 라는 변수 를 두 어 저장 한다 . label 값 이 최대 인 용사 중 하나 ( 용사 A ) 를 골라 경로 를 진행 하 고 , 용사 가 선택 되 었 으므로 용사 의 만족도 를 충분히 작 은 값 ( 여기 서 는 - 1 ) 로 만든다 . stack 에 용사 A 의 이름 을 저장 하 며 ,   용사 A 가 만족 하 는 속성 을 list 에서 제거 하 여 subproblem 을 생성 한다 . 만족도 를 계산 하 는 횟수 = n 2 . depth = 1 , list = [ ??? 최선 4 개 , 최악 10 개 가 남 아 있 을 것 이 다 ] stack = [ 용사 A ] list 의 길이 가 depth = 0 일 때 와 depth = 1 일 때 변화 가 없 으면 이 문제 는 해 가 없 다 . 왜냐하면 모든 용사 의 만족도 가 0 이 라는 소리 이 기 때문 이 다 . >> 해당 depth 를 Terminate 하 고 랜덤 으로 용사 를 아무 나 고른다 list 의 길이 가 0 이 되 었 으면 이미 해 가 구해진 것 이 다 . >> 해당 depth 을 Terminate 하 고 랜덤 으로 용사 를 아무 나 고른다 용사 A 를 제외 한 나머지 용사 들 ( 만족도 가 음 이 아닌 용사 들 ) 을 대상 으로 만족도 를 계산 하 고 label 값 을 갱신 한다 . 이후 부터 는 1 번 과정 대로 진행 한다 . 만족도 를 계산 하 는 횟수 = n + ( n - 1 ) = 2 n - 13 . 이 방법 을 depth = 4 일 때 까지 반복 한다 . 그러면 용사 다섯 이 stack 에 쌓일 것 이 고 , list 에 속성 이 남 아 있 느냐 아니 냐 에 따라 해 의 유무 여부 가 판별 날 것 이 다 . 해 의 유무 여부 는 프로그램 이 판단 하 는 것 이 아니 라 사람 이 판단 하 게 된다 . 만족도 를 계산 하 는 횟수 = 5 n - 10   시간 복잡도 : depth 가 유한 하 므로 ( O ( n ) ) . / / ? 하지만 용사 가 없 어질 때가 지 이 방법 을 무한히 지속 하 는 것 으로 문제 가 변경 되 면 O ( n ^ 2 ) 가 된다 . ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ이를 그림 으로 표현 하 면 다음 과 같 다 . ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ이를 의사코드 로 작성 하 면 다음 과 같 다 . ... . .. 변수 들 과   용사 정보 를 담 을 클래스 , 오브젝트 , 리스트 는 이미 선언 이 되 어 있 다고 가정 용사 . name = 용사 오브젝트 의 이름 , 용사 . label = 용사 오브젝트 의 만족 도 list . Length = list 의 크기 maxlabel = 용사 들 의 만족도 중 최대 인 것 void YONGSA ( 용사 들 의 정보 를 담 은 리스트 ) {   for ( depth 는 0 부터 4 까지 )   {     if ( depth >   0 )      {       if ( 이전 단계 에서 list . Length 가 현재 단계 에서 list . Length 와 같 다 )         { 랜덤 으로 용사 를 하나 뽑 아 용사 . name 을   stack 에 push 해 기록 하 고          용사 . label = - 1 }       else if ( list . Length 가 0 )       { 랜덤 으로 용사 를 하나 뽑 아 용사 . name 을 stack 에 push 해 기록 하 고         용사 . label = - 1 }       else       for ( 용사 리스트 의 길이 만큼 )       {         for ( list 의 길이 만큼 )           {             if ( 용사 . label > - 1 ) { 용사 . label 초기 화 }             용사 의 개인 속성 과 list 의 속성 간 에 일치 하 는 것 을 비교 한다 .             if ( 일치 ) { label ++, maxlabel 과 label 을 비교 하 여 최댓값 을 maxlabel 에 넣 는다 }          }        }       for ( 용사 리스트 의 길이 만큼 )       {         용사 오브젝트 내부 의 label 변수 와 maxlabel 이 일치 하 는 용사 를 찾 는다 .         if ( 찾 음 ) { 해당 용사 의 속성 과 일치 하 는 list 의 속성 을 제거 하 고 ,   루프 밖 으로 빠져 나온다 }        }       용사 . name 을 stack 에 push 해 기록 하 고 용사 . label = - 1          else / / depth = 0       for ( 용사 리스트 의 길이 만큼 )       {         for ( list 의 길이 만큼 )          {           if ( 용사 . label > - 1 ) { 용사 . label 초기 화 }           용사 의 개인 속성 과 list 의 속성 간 에 일치 하 는 것 을 비교 한다 .           if ( 일치 ) { label ++, maxlabel 과 label 을 비교 하 여 최댓값 을 maxlabel 에 넣 는다 }         }      }       for ( 용사 리스트 의 길이 만큼 )       {         용사 오브젝트 내부 의 label 변수 와 maxlabel 이 일치 하 는 용사 를 찾 는다 .         if ( 찾 음 ) { 해당 용사 의 속성 과 일치 하 는 list 의 속성 을 제거 하 고 ,   루프 밖 으로 빠져 나온다 }      }       용사 . name 을 stack 에 push 해 기록 하 고 용사 . label = - 1     }     depth ++   }}//   이후 결과물 :   / /   용사 다섯 이 사라진 용사 리스트 / /   depth = 5 / / list = { 최소 0 개 최대 10 개 의 속성 값 이 남 아 있 음 } ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ유니티엔진 하 에서 구현 가능 한 형태 의 C # 실제 코드 는 아래 와 같 다 . https : / / github . com / Soundpiercer / CQ _ IDOLCATCH _ Backup / blob / master / CQ . cs ( 작성 중 ) ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡ ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ저기서 계산 횟수 를 더 줄일 수 는 없 을까 ? 다음 과 같 은 방법 으로 ' label 변수 와 maxlabel 이 일치 하 는 용사 를 찾 는 ' 과정 을 줄일 수 있 다 , 라고 생각 해 볼 수 있 다 .   - 만족도 를 갱신 하 는 과정 에서 maxlabel 도 갱신 이 될 것 이 고 , 만족도 가 갱신 된 maxlabel 보다 작 으면 그 용사 의 만족도 를 0 로 만든 다 . 어차피 그 용사 는 해당 depth 에서 선택 이 안 될 것 이 고 다음 depth 에서 새롭 게 만족도 가 갱신 될 것 이 므로 , maxlabel 값 을 갱신 한 용사 들 만 이 남 아 비교 될 것 이 다 . 하지만 이렇게 되 면 if 문 이 하나 더 들어가 게 되 고 비교 횟수 는 더 커 지 게 된다 . 또 다른 최적화 방법 은 없 을까 ?