[학습 6회차] 카카오 코드 페스티벌 E 문제 해결하기

이번 문제는 '음악 추천'이라는 문제이다. 이 문제를 풀기에 앞서 문제를 정리해보았다.

 

제목 그대로 내용의 발단은 음악을 추천하는 플랫폼에서 음악을 추천하는 방법으로 음악 알고리즘을 사용한다. 이 알고리즘을 우리가 구현을 해 보는 것이 목적이다. 프로도는 사용자가 좋아할 만한 음악을 추천하기 위해 새로운 추천 알고리즘을 고안했는데, 그 방법은 아래와 같다.

 

1. 이 알고리즘은 음악 간 유사도를 트리 형태로 만든 뒤 사용자의 입력에 따라 추천 음악을 결정한다.

2. 위의 그림처럼 각 노드의 색깔은 가수를 의미한다.

 

3. 추천이 이뤄지는 방법은 다음과 같다.

-> 사용 패턴 분석을 통해 트리의 노드 중 하나와 가중치가 결정된다. 

-> 선택한 노드가 루트가 되는 서브 트리의 모든 노드가 추천 대상이 되고, 이 가중치에 따른 점수가 분배된다.

ex) 빨간색 노드가 하나 선택되었고, 이 노드의 가중치가 23이라고 가정한다면 이 노드의 서브트리 노드가 총 5개이고, 나누게 되면 23/5 = 4이고, 나머지가 3이게 되므로 이 서브트리 노드들에게 4의 점수가 부여된다. 

-> 점수가 높을수록 선택될 확률이 높아진다.

 

4. 이 때, 특정한 가수의 곡만 추천되는 상황을 방지하기 위해 가수별로 평균 점수를 관리하려고 한다.

ex) 빨간 색 노드가 특정 가수의 곡이라고 지정해보면, 위와 같이 서브트리가 선택된 경우 총 점수는 4+4=8이지만, 트리에서 표시된 노드가 3이므로 평균 점수는 8/3점이 된다. 이런 식으로 계산을 한다.

 

이와 같이 가중치가 계산될 때, 가수 별 평균 점수가 주어진 목표 점수를 언제 초과하게 되는지 계산을 하여라.

 

입력해야할 사항은 아래와 같다.

첫번째 입력: (세 정수) 곡의 수/ 추천 알고리즘의 결과 데이터 수/ 목표 점수가 주어진다.

각 곡은 1번부터 N번까지 번호가 붙어있게 된다. 3을 입력했을 경우 노래는 1, 2, 3의 번호가 붙게 된다.

그 다음 입력으로 번호가 주어지는데, 이는 2번 곡부터 해당 곡의 부모가 되는 곡의 번호이다.

1번 곡은 부모 노드가 없음에 주의한다. 

 

사실 여기까지 문제를 알아들어서 생각을 해 보았다. 가중치를 판단하는 것도 꽤 걸리는데, 이 문제를 어떻게 해결해야할지 생각을 해 보았지만 꽤 막막했다.

 

우선 트리를 만들고, 각각 곡에 대한 번호를 노드에 저장한다. 그리고 그 곡을 구별할 수 있도록 한다.

그리고 나서 구별한 각각의 노드에 대한 가중치를 매기고, 어느 한 노드를 선택한 것에 대한 합을 구하며 초과를 구하면 될 것 같은 생각이 들었지만 그렇게 쉽게 해결될 문제는 아닌 것 같다.

 

찾아 보았지만 처음 들어보는 생소한 알고리즘 이론을 사용하는 문제여서 조금 더 고민해보아야 할 것 같다.

학습 동아리를 진행하는 시간만으로는 다소 부족했다.