네박자대로
[백준 15954번] 인형들 (C++) 본문
2018 카카오 코드 페스티벌 예선 2번 문제
처음에 문제가 이해되지 않아 겁먹고 포기할 뻔 했는데
반복해서 읽어보니 걱정만큼 어려운 문제가 아니어서 찬찬히 풀 수 있었다!
마찬가지로 곧장 코드를 짜기 전에 어떻게 풀 것인지 손코딩으로 생각해봤다.
우선 N 개의 인형의 나열 순서는 input으로 받기 때문에 고정되어 있었다.
내가 할 일은 이 고정된 인형의 순서에서 K개 이상의 연속된 인형들의 최소 표준편차를 구하는 일이었다.
가령, 테스트케이스 2처럼
N=10, K=3이라면
3개의 연속된 인형, 4개의 연속된 인형, 5개의 연속된 인형, ... , 10개의 연속된 인형 각각의 경우의
표준편차 중 최소값을 골라내면 되는 것이다.
여기서 중요한 건 3개의 연속된 인형도 1번~3번 인형, 2번~4번 인형, 3번~5번 인형, ... 8번~10번 인형
이렇게 8개의 조합이 나올 수 있다는 거다. (4개, 5개 ,... 10개의 연속된 인형의 경우도 그 조합의 가짓수가 다양하기는 마찬가지다.)
그럼 어떻게 푸는 게 좋을까??
예를 들어 5개의 연속된 인형의 표준편차를 구하는 일에는 다음과 같이
가장 처음 HEAD=0, TAIL=4로 초기화해서 HEAD와 TAIL사이의 인형의 선호하는 사람 수에 대한 표준편차를 구하고
그 다음 HEAD와 TAIL을 1씩 증가시켜 배열의 마지막 인덱스에 도달할 때 까지 표준편차 구하는 것을 반복하면 된다.
최소값은 반복문 내에서 바로 바로 갱신해주면 된다.
즉, HEAD와 TAIL이라는 iterator를 반영하여 구해주면 된다.
이러한 방식으로 알고리즘을 설계한 다음 코드를 짜기 시작했다.
main문에서는 최소한의 작동만 해야하므로
위 알고리즘을 수행할 2개의 함수를 구현했는데
(1) head와 tail을 배열 내에서 이동시키면서 최소 표준편차를 찾아내는 함수
(2) 위 (1)함수가 전달해주는 head와 tail을 바탕으로 표준편차를 계산해서 전달해주는 함수
이렇게 두 가지 이다.
하나씩 살펴보도록 하자.
우선 전역변수는 다음과 같다.
int N;
int K;
int doll_arr[501];
doll_arr는 인형 순서를 입력받을 배열이다.
다음 표준편차를 구하는 함수이다.
double Calculator_SD(int _head, int _tail) //Smallest_SD()에서 계산하고자 하는 수열의 표준편차를 계산한 뒤 리턴해준다.
{
double mean = 0;
double sd = 0;
int num = _tail - _head + 1;
for (int j = _head; j <= _tail; j++)
{
mean += doll_arr[j];
}
mean /= num; //평균값 구하기
for (int j = _head; j <= _tail; j++)
{
double temp = (doll_arr[j] - mean);
temp *= temp; //제곱
sd += temp; //제곱값 합산
}
sd /= num;
sd = sqrt(sd);
return sd;
}
num은 몇 개의 연속된 인형인지를 저장하는 변수이다.
배열의 head부터 tail까지에 해당하는 각 인형의 선호하는 사람 수를 모두 더한 후 num으로 나누어주어 평균을 구하고
다시 head부터 tail까지 해당하는 각 인형의 선호하는 사람 수와 평균의 차의 제곱을 합산한 뒤 num으로 나누어
분산을 구했다.
마지막으로 분산에 루트를 씌워 표준편차를 구한 뒤 리턴한다.
다음은 핵심이 되는 함수이다.
double Smallest_SD() //최소가 되는 표준 편차를 리턴한다.
{
int head = 0; //배열의 head
int tail = 0; //배열의 tail
double smallest = 100000000;
for (int i = K-1; i < N; i++) //가령 N=10, K=3일 경우, 반복문은 2,3,4,..,9 총 8회를 돈다.
{
head = 0;
tail = i;
while (tail < N)//즉 tail이 배열의 마지막 인덱스에 닿기 전까지 반복
{
double temp = Calculator_SD(head, tail);
if (smallest >= temp)
{
smallest = temp;
}//최솟값 갱신
head++;
tail++;
}
}
return smallest;
}
k개 이상의 가능한 모든 인형의 나열에 대한 표준편차를 계산하여 최솟값에 해당하는 표준편차를 smallest에 저장한다.
이 후 head와 tail을 1씩 옮겨가며 반복문을 수행한다.
그럼 이제 전체 코드를 살펴보자.
#include <iostream>
#include <cmath>
using namespace std;
int N;
int K;
int doll_arr[501];
double Calculator_SD(int _head, int _tail) //Smallest_SD()에서 계산하고자 하는 수열의 표준편차를 계산한 뒤 리턴해준다.
{
double mean = 0;
double sd = 0;
int num = _tail - _head + 1;
for (int j = _head; j <= _tail; j++)
{
mean += doll_arr[j];
}
mean /= num; //평균값 구하기
for (int j = _head; j <= _tail; j++)
{
double temp = (doll_arr[j] - mean);
temp *= temp; //제곱
sd += temp; //제곱값 합산
}
sd /= num;
sd = sqrt(sd);
return sd;
}
double Smallest_SD() //최소가 되는 표준 편차를 리턴한다.
{
int head = 0; //배열의 head
int tail = 0; //배열의 tail
double smallest = 100000000;
for (int i = K-1; i < N; i++) //가령 N=10, K=3일 경우, 반복문은 2,3,4,..,9 총 8회를 돈다.
{
head = 0;
tail = i;
while (tail < N)//즉 tail이 배열의 마지막 인덱스에 닿기 전까지 반복
{
double temp = Calculator_SD(head, tail);
if (smallest >= temp)
{
smallest = temp;
}//최솟값 갱신
head++;
tail++;
}
}
return smallest;
}
int main()
{
cin >> N >> K;
for (int i = 0; i < N; i++)
{
cin >> doll_arr[i];
} // 테스트케이스를 입력받아 배열에 저장한다.
cout.precision(10);
cout << Smallest_SD() << "\n"; //정답이 되는 최소 표준편차를 출력한다.
return 0;
}
여기서 중요한 건 표준편차의 오차가 소숫점 6자리 이하여야 한다고 했으므로
안전하게 precision(10)으로 설정하여 총 10자리를 출력하도록 하자.
6자리 딱 맞춰서 출력하면 틀린다ㅎㅎ..
아무튼 제출 결과 무사히 정답!
'알고리즘' 카테고리의 다른 글
[프로그래머스 > 고득점kit 해시] 베스트 앨범 (C++) (0) | 2021.03.04 |
---|---|
[프로그래머스 > 고득점kit 해시] 위장 (C++) (0) | 2021.02.04 |
[프로그래머스 > 고득점kit 해시] 전화번호 목록 (C++) (0) | 2021.01.21 |
[프로그래머스 > 고득점kit 해시] 완주하지 못한 선수 (C++) (0) | 2021.01.21 |
[백준 15953번] 상금 헌터 (C++) (0) | 2021.01.16 |