[학습 2회차] kakoFestival 2018 예선문제 B
오늘은 학습 동아리 동아리 시간에 카카오 페스티벌 예선 문제 B를 해결해 보았다. 문제가 다소 조금 길고, 요구하는 바가 어떤 것인지 파악하는 것이 실제 코드를 구현하는 시간보다 더 오래걸렸던 것 같다.
문제를 해결하기 위하여 작성한 코드는 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
import java.util.Arrays;
public class Main {
public static void main (String args[]) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt(); //1~500 인형의 개수
int K = scan.nextInt(); //1~N 몇 개를 뽑는지
int storeK = K;
int index = 0;
//비교를 위한 숫자를 몇 개 담아야 하는지 알기 위해서
while(true) {
if((N-K) < 0) {
break;
}
else {
index += N-K+1;
}
K++;
}
K = storeK; //초기화
double compare[] = new double[index]; //비교 배열을 만들기
int user[] = new int[N]; //사용자가 입력한 만큼의 배열
for(int i=0; i<N; i++) { //입력 받은 값 배열로 만들기
user[i] = scan.nextInt();
}
//각각의 표준 편차 구하기
int arrayIndex = 0;
while(true) {
int temp = 0;
if((N-K) < 0) {
break;
}
else {
//될때까지 표준편차 구하기
while(temp + K != (N+1)) {
//산술 평균 구하기
//꼭 3번이 아니라 4번 5번 등등 늘어날 수 있다는 것 간과함
double m = 0, disper=0, stan=0; //각각 평균, 분산, 표준편차
for(int a=0; a<K; a++) {
m += user[temp+a];
}
m = m/K;
for(int b=0; b<K; b++) {
}
disper = disper/K;
compare[arrayIndex] = stan; //비교 배열에 넣기
arrayIndex++;
temp++;
}
}
K++;
}
Arrays.sort(compare); //오름차순 정렬
System.out.println(compare[0]); //가장 작은 값 도출
}
}
|
이 문제를 읽고 어떤 바를 요구하는지 애매한 사람들을 위해 한번 더 간략하게 정리해보았다.
1. 입력 값은 인형의 개수와, 뽑을 인형들의 개수이다. 문제에서는 이를 각각 N과 K의 변수로 예를 들었다.
2. 연속된 K개 이상의 인형을 뽑는다는 것은, 만약 입력 값으로 5와 3을 입력했을 경우, 5개의 숫자를 입력받게 되는데 이 때, 1 2 3 4 5를 입력했다면 뽑을 수 있는 선택지는 아래와 같다.
K = 3일 경우, 1 2 3/ 2 3 4/ 3 4 5
K = 4일 경우, 1 2 3 4/ 2 3 4 5
K = 5일 경우, 1 2 3 4 5
3. 입력 값에 의해 위처럼 뽑을 수 있는 경우의 수에 대해 표준편차를 구하고, 구한 표준 편차 중 가장 작은 표준편차의 값을 출력하면 문제가 해결된다.
본인의 경우, 결과값을 담을 배열을 하나 만들고, 그 배열에 모든 경우의 표준편차를 담은 다음, Arrays.sort()를 이용하여 오름차순으로 정렬하여 가장 작은 값을 선택하는 형식으로 문제를 풀었다.
수식을 보면 울렁거릴 다른 사람들을 위해서 간단하게 정리하면 산술평균, 분산, 표준편차를 구하는 방법은 아래와 같다.
예를 들어 설명하면 더 쉽게 느껴지니, 위에서 예시를 들었던 대로
인형의 개수(N)는 5개, 뽑을 인형의 개수(K)는 3개라고 했을 때 구하는 식은 다음과 같다.
(5개의 입력은 1 2 3 4 5)
어떤 한 경우, N=5, K=3, 연속된 숫자의 경우 중 1 2 3이라고 할 때 구하는 방법.
> 산술평균
(1+2+3)/3 -> 모든 값의 합/총 개수
그리고 이렇게 구한 산술 평균을 m이라고 한다.
> 분산
(1-m)의 제곱 + (2-m)의 제곱 + (3-m)의 제곱들의 모든 합 /총 개수
그리고 이렇게 구한 분산의 값을 S라고 한다.
> 표준편차
표준 편차는 간단히 분산의 제곱근, 분산 값에 루트를 씌운 값이라고 생각하고 구하면 된다.
S의 값에 루트를 씌운 값이 표준 편차이다.
위와 같은 방법으로 나온 예시의 결과는 아래와 같았다.
오늘 문제도 그다지 어렵게 해결하지는 않았다. 다음 문제부터 조금 더 집중해서 풀어봐야겠다.
'Undergraduate Records' 카테고리의 다른 글
| [학습 4회차] C 숏코딩 문제 풀이 (0) | 2020.02.07 |
|---|---|
| [학습 3회차] union find & 카카오 페스티벌 문제 C 숏코딩 (0) | 2020.02.07 |
| [학습1회차] kakaoFestival 2018 예선문제 A (0) | 2020.02.03 |
| [6회차] Toad 설치 및 데이터베이스 명령문 맛보기 (0) | 2020.02.01 |
| 데이터베이스 초기 구축 단계 (0) | 2020.02.01 |
