시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 89 | 30 | 15 | 40.541% |
요즘은 바야흐로 빅데이터 전성시대. 너도나도 머신러닝과 데이터사이언스를 배우기 위하여 노력하고 있다. 급하게 데이터마이닝과 머신러닝을 공부한 동이는 자신이 배운 내용을 바탕으로 주어진 데이터들을 분류할 수 있는 선형 분류기(Linear Classifier)를 찾는 알고리즘을 설계하고자 한다.
선형 분류기란 쉽게 말해서 어떤 데이터가 가지고 있는 두 특징 값(x1, x2)을 통하여 올바르게 데이터의 유형을 분류할 수 있는 직선의 방정식을 의미한다. 실제로 주어진 데이터들 사이에서 이러한 방정식 중 최적의 방정식을 자동으로 찾기 위해 수많은 알고리즘들이 개발되었다.
<위의 데이터들은 선형 분류기를 이용해 두 그룹으로 정확히 나눌 수 있다>
위의 예시를 보자 H1과 H2라는 직선은 두 특징 x1과 x2를 통해 흰 그룹과 검은 그룹을 완전히 분류할 수 있으므로 좋은 분류기이다. 하지만 H3은 직선만으로 두 그룹을 분류할 수 없으므로 좋은 분류기가 아니다.
하지만 항상 이렇게 정확하게 분류할 수 있는 선형 분류기가 존재하는 것은 아니다. 현실의 데이터들은 수많은 예외와 오차가 존재하고 이에 반해서 선형 분류기는 너무 단순하기 때문이다.
동이는 N명의 사람을 표현할 수 있는 두 특징값과 각 사람이 가장 좋아하는 걸그룹 정보를 수집하였다. 이를 바탕으로 동이는 두 특징값을 이용해 러블리즈를 가장 좋아하는 사람을 분류할 수 있는 선형 분류기를 찾고자 한다. 동이가 찾고자 하는 선형 분류기는 아래와 같은 조건을 만족하여야 한다.
동이는 다양한 알고리즘을 도입하여 자동으로 최적의 선형분류기를 컴퓨터가 찾아낼 수 있도록 할 예정이었지만, 그 전에 자신이 가진 데이터상에서 이론적으로 위의 조건을 만족하는 최적의 선형분류기는 어느 정도의 성능을 가지는지 궁금해졌다. 그래야만 동이의 프로그램이 찾아낸 선형 분류기와 비교하여 성능 평가가 가능하기 때문이다.
동이가 선형 분류기를 만드는 데 사용할 데이터들이 주어질 때, 위의 조건을 만족하며 가장 좋은 선형분류기는 러블리즈를 가장 좋아하는 사람 중 몇 명을 Positive 그룹으로 분류할 수 있는지 계산하는 프로그램을 작성해주자.
<흰 점을 가장 많이 Positive에 포함시키는 선형분류기는 L이다>
위의 예시를 보자. 흰점이 러블리즈가 가장 좋다고 응답한 사람의 이고 검은 점이 다른 그룹이 가장 좋다고 응답한 데이터라고 하자. Positive에 흰 점을 가장 많이 포함하는 선형 분류기가 가장 좋은 분류기이므로 Lx를 설정하고 아래를 Positive, 위를 Negative로 설정하면 가장 좋은 선형 분류기가 된다. 이때 정답은 7이 된다.
가장 첫 줄에 응답 데이터 수를 나타내는 자연수 N(6 ≤ N ≤ 100)이 주어진다. 이후 N줄에 걸쳐서 x1 x2 NAME 형식으로 데이터가 주어진다(-1,000 ≤ x1, x2 ≤ 1,000, 1 ≤ Length of NAME ≤ 15). x1과 x2는 각각 그 사람의 특징을 나타내는 두 정수값이다. 그룹의 이름은 공백없이 알파벳 대문자로 주어진다.
러블리즈를 가장 좋아한다고 응답한 사람은 항상 그룹 이름이 “LOVELYZ”이다. 러블리즈를 가장 좋아하는 사람과 그렇지 않은 사람은 각각 최소 3명씩은 존재한다.
각 사람의 특징을 좌표로 2차원 평면 위에 데이터를 나타내었을 때 세 개 이상의 점이 한 직선 위에 놓이는 경우는 없다.
최적의 선형분류기가 러블리즈를 좋아하는 사람을 Positive로 분류할 수 있는 수를 한 줄에 출력한다.
6 1 1 GIRLFRIEND 2 3 GIRLSDAY 3 6 GIRLSGENERATION 3 2 LOVELYZ 4 4 LOVELYZ 6 3 LOVELYZ
3
7 1 1 WOOLLIM 2 3 LOVELYZ 1 6 EPIKHIGH 5 4 LOVELYZ 6 1 NELL 4 5 LOVELYZ 6 6 INFINITE
0
University > 아주대학교 > 2017 아주대학교 프로그래밍 경시대회 (APC) > Division 1 G1번