목표 : 카카오 코드 페스티벌 2018 예선 E,F문제를 풀기 위해 초석 다지기
https://www.acmicpc.net/problem/15957
15957번: 음악 추천
입력의 첫째 줄에는 세 정수로, 곡의 수 N(2 ≤ N ≤ 100,000), 추천 알고리즘의 결과 데이터의 수 K(1 ≤ K ≤ 100,000), 목표 점수 J(10 ≤ J ≤ 108)가 주어진다. 각각의 곡은 1번부터 N번까지 번호가 붙어 있다. 다음 줄에 N-1개의 곡 번호가 주어지는데, 이는 2번 곡부터 해당 곡의 부모 노드가 되는 곡의 번호이다. 1번 곡은 부모 노드가 없다. 다음 줄에 N개의 수가 주어지는데, 이는 1번 곡부터 해당 곡을 부른 가
www.acmicpc.net
E번 문제(음악 추천) 정리
> 음악 추천 알고리즘을 작성하는 것
> 각 노드는 곡을 나타내며 색깔을 가수를 의미한다.
> 사용 패턴 분석을 통해 트리에 있는 노드 중 하나와 "가중치"가 결정된다. 선택된 노드를 루트로 하는 서브트리의 "모든 노드"가 추천 대상이다.
> 예를 들어 선택된 노드에 가중치 23을 부여한다고 가정하고 서브트리의 노드가 총 5개라고 가정한다면 23 / 5 ---> 4....3 이므로 각 서브트리의 노드에 점수 4가 부여된다.(나누어 떨어지지 않는다면 몫만 가져온다.)
> 노드의 색깔이 가수를 의미한다고 했는데 특정 가수의 곡만 추천되는 상황을 방지하기 위해 가수 별로 평점을 관리한다.
> 위에서 서브트리의 노드 중 빨간색 노드가 2개이므로 빨간색 노드의 점수는 8점이다. 그러나 전체 트리 중 빨간색 노드는 3개이므로 평점은 8/3점이 된다.
> 트리의 노드와 가중치가 선택되는 과정이 반복된다고 할 때, 가수 별 평균 점수가 주어진 목표 점수를 언제 초과하게 되는지 계산하려고 한다.
https://www.acmicpc.net/problem/15958
15958번: 프로도의 100일 준비
입력의 첫째 줄에는 직각다각형의 꼭짓점의 개수 N(4 ≤ N ≤ 500,000)이 주어진다. 이어지는 N줄 각각엔 직각다각형 꼭짓점의 좌표를 나타내는 정수 (x, y) (0 ≤ x, y ≤ 109)가 공백을 사이에 두고 주어진다. 입력 다각형의 시작점은 원점 (0,0)이고, 꼭짓점이 시계방향 순서로 주어진다. 즉, 연속하는 두 개의 꼭짓점은 직각다각형의 한 선분을 이루며, x좌표는 단조증가한다. 참고로, 시작점과 끝점만 y좌표가 0이다. 연속하는 세 점이
www.acmicpc.net
F번 문제(프로도의 100일 준비) 정리
> 종이의 정보가 주어진다. (남은 종이는 각 변이 x축 또는 y축에 평행한 히스토그램 모양의 직각다각형이다. 이를 잘 잘라서 L-모양 직각다각형을 만들려고 한다)
> L-모양 직각다각형이란 꼭짓점의 수가 4 또는 6이고 각 변이 모두 x축 또는 y축에 평행한 직각다각형을 의미한다.
> 참고로, 꼭짓점의 수가 4인 직각다각형은 직사각형이다. 직사각형 모서리에서 조그만 직사각형을 오려내면 ‘L’ 자를 만들 수 있다.
'CNU 학습 동아리 > 2020 동계 학습 동아리' 카테고리의 다른 글
| 2020 동계 학습 동아리_7회차_2020-02-17(월) (0) | 2020.02.18 |
|---|---|
| 2020 동계 학습 동아리_6회차_2020-02-14(금) (0) | 2020.02.14 |
| 2020 동계 학습 동아리_4회차_2020-02-10(월) (0) | 2020.02.10 |
| 2020 동계 학습 동아리_3회차_2020-02-07(금) (0) | 2020.02.07 |
| 2020 동계 학습 동아리_2회차_2020-02-04(화) (0) | 2020.02.04 |
댓글