[백준] 4344번 : 평균은 넘겠지 - [C++]
https://www.acmicpc.net/problem/4344
4344번: 평균은 넘겠지
대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다.
www.acmicpc.net
- 문제
이 번 문제도 그리 어려운 문제는 아닐 것이다.
다만, 소수점 출력과 반올림 문제 때문에 틀린 분 들도 은근 있을 것이고, 이 번 문제는 입력받은 수에 따라 배열을 생성해야하기에 동적 할당 개념을 모를 경우 어려웠을 수도 있으리라 본다. 이 부분을 유의하면서 한 번 같이 풀어보도록 하자.
- 알고리즘 [접근 방법]
사실 이 문제자체가 어려운 것은 아니다.
다만, 짚고 넘어가야 할 것이 있다. 바로 배열의 동적 할당과 정적 할당이다.
그동안은 배열을 선언하고 쓸 때 다음과 같이 썼었을 것이다.
int main() {
int arr[5]; // 배열의 정적 할당
}
이는 코드를 작성 할 때, 사용자의 입력에 따라 변하는 것이 아닌 이미 공간이 정해져서 실행되는 배열이다.
이러 한 것을 비가변 배열 혹은 정적 배열이라고 한다.
그러면 사용자의 요청에 따른 가변적인 배열을 사용하려면 어떻게 해야 할까? 자바를 먼저 배웠다면 정말 간단하게 만들 수 있다.
int size;
size = input();
int[] arr = new int[size]; // 사용자의 입력에 따른 길이가 정해진 배열 선언
C++의 경우도 사실 다음과 같이 해도 gcc나 clang을 사용하고 있다면 되긴 한다.
int main() {
int size;
cin >> size;
int arr[size];
}
사용자의 입력 요청에 따른 배열 생성이 가능하다. 하지만, 만약 C나 C++을 배워보신 분이라면 위와 같이 가르치진 않는다. 이에 대한 이유를 알기 전에 일단 VLA에 대해 알아야 한다.
위와 같이 사용자의 요청에 따른 가변 길이 배열을 VLA(Variable Length Arrays)라고 한다. (동적 배열이라고도 부른다)
그러면 정적과 동적 배열의 차이는 무엇일까?
이전의 C와 C++의 경우에는 배열 선언은 기본적으로 컴파일 타임(Compile time)에 크기가 결정된다. (할당이 아니다. 결정이다.)
쉽게말해 예로들어 int arr[5] 라고 작성한 코드를 컴파일러가 읽으면 컴파일러는 int형의 5개 공간을 필요로 하는 구나 하고 그 정보를 갖고있게 되는 것이다. 여기서는 int형이 4byte 이고, 총 5개의 공간이 필요하므로 arr는 20byte가 필요하다는 정보를 갖게 되는 것이다.
그렇게 컴파일이 끝나고, 해당 실행 파일을 실행하게 되면, 즉 런 타임(Run time) 때 해당 정보를 갖고 20byte를 할당하게 된다.
반대로 가변 길이 배열의 경우에는 int arr[n] 라고 작성하게 되면 컴파일 타임에는 해당 변수에 대한 타입 정보 정도만 갖고 있고, 런 타임에 n이 주어지게 되면 그 때 되가 되어서야 n의 크기를 읽고 할당을 하게 된다.
그래서 보통은 C, C++의 경우 -alloc (malloc, calloc 등) 을 사용하여 동적 할당을 한다.
가장 대표적인 예로는 다음과 같다.
int main() {
int size;
cin >> size;
int* arr = (int*)malloc(sizeof(int) * size);
}
위의 경우 C언어 방식의 대표적인 동적 배열 생성 방식이다. 물론 C++에서도 가능하다.
또 다른 방법으로는 C++의 경우 좀 더 쉽게 new 키워드를 통해 자바처럼 생성 할 수도 있다.
int main() {
int size;
cin >> size;
int* arr = new int[size];
}
그럼 왜 int arr[size] 형태를 가르치지 않는 것일까? 일단, 가장 큰 이유는 C++ 표준 문법이 아니다.
해당 문법은 C99의 문법인데, C++의 경우 C의 환경도 포함되어있다보니 가능해진 것이다. 실제 C++표준으로만 컴파일을 하게 되면 에러가 나거나, 컴파일러마다 차단 된 경우들이 있다.
예로들어 다음과 같이 테스트를 해볼 수 있다.
[test.cpp]
int main(int argc, const char * argv[]) {
int size = 10;
int arr[size];
return 0;
}
위와 같이 작성하고 터미널에서
g++ -o test test.cpp
위와 같이 수행하면 정상적으로 컴파일도 되고, 에러를 내뱉진 않을 것이다. (물론 컴파일 설정마다 다를 수는 있다)
만약 아래 명령어로 컴파일 하면 경고를 내뱉을 것이다.
g++ -o test test.cpp -pedantic
-pedantic 명령어는 비표준 구현 부분을 진단하여 경고를 보낸다. 아래와 같이 말이다.
보면 vla 가 C99의 문법이라면서 경고를 보낸다.
그래서 엄격하게 표준을 준수하고자 할 경우에는 아래 명령어를 사용하면 된다.
g++ -o test test.cpp -pedantic -Werror
그러면 경고가 발생할 경우 error가 되어 컴파일이 중단되게 된다.
즉, 비 표준 문법이니, int arr[size] 같은 것은 C++에서는 피하는게 좋다. (사실 C에서도 안쓰는 것이 좋다.)
너무 말이 길어졌다.
일단, 우리가 배열을 동적으로 생성해야한다는 것을 알았으니 어떻게 생성해야하는지를 생각해보자.
앞서 배열 선언 과정에서 필자가 3가지를 보여주었었다.
int arr[size];
int* arr = (int*)malloc(sizeOf(int) * size);
int* arr = new int[size];
그 중 첫 번째 문법은 비표준 방식이니, 두 번째 혹은 세 번째 방법을 쓰는 것이 좋겠다.
마지막으로, 가장 편리한 방식이 있다.
바로 vector 클래스를 사용하는 것이다. vector의 경우 사이즈를 결정하지 않아도 자유롭게 원소를 추가, 삭제 등을 수행할 수 있는 자료구조 클래스다.
또 다른 방법으로는 문제에서 입력으로 주어지는 배열의 최대 길이(N)가 1000이니, 배열을 그냥 1000개를 두고 그 안에서 쓰는 방법도 있긴 하다. 다만, 여기서는 동적 할당에 초점을 맞추고자 이 방법은 쓰지 않겠다.
먼저 malloc을 사용한 방식부터 설명하겠다.
그럼 입력 받는 형식부터 보자.
테스트 케이스인 C가 주어진다. 즉, C만큼 반복한다는 의미이니 일단 무시하고 하나의 테스트에 대해서만 생각해보자.
각 테스트 케이스에 대해서는 N과 N개의 요소들이 입력이 된다. 즉, 다음과 같이 만들 수 있다.
int N;
cin >> N;
// 동적 배열 선언 및 생성
int* arr = new int[N]; // 혹은 int* arr = (int*)malloc(sizeOf(int) * size)
for(int i = 0; i < N; i++) {
cin >> arr[i]; // i ~ N - 1 까지 입력받은 요소로 초기화
}
주석으로도 달았지만, malloc이든, new 키워드든 배열 접근 방법은 같기 때문에 어느 방식을 하더라도 상관은 없다. (다만 type-safe 관점에서 new 키워드를 이용한 배열 생성을 추천한다.)
그리고 우리는 일단, 평균을 구해야 한다. 평균은 (합계 / 개수) 이므로, 다음과 같이 해줄 수 있다. 이 때, 위 문제에서도 보았지만, 소수점을 활용해야 하기 때문에 평균을 구할 때에는 float, double형과 같은 부동소수점 자료형을 활용해야한다.
int N;
cin >> N;
// 동적 배열 선언 및 생성
int* arr = new int[N]; // 혹은 int* arr = (int*)malloc(sizeOf(int) * size)
for(int i = 0; i < N; i++) {
cin >> arr[i]; // i ~ N - 1 까지 입력받은 요소로 초기화
}
// 평균 구하기
double avg = 0;
for(int i = 0; i < N; i++) {
avg += arr[i]; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
여기까지 했으면, 거의 끝난 것이나 마찬가지다. 평균을 구했으니, 평균을 넘는 인원 수를 체크해보자.
int N;
cin >> N;
// 동적 배열 선언 및 생성
int* arr = new int[N]; // 혹은 int* arr = (int*)malloc(sizeOf(int) * size)
for(int i = 0; i < N; i++) {
cin >> arr[i]; // i ~ N - 1 까지 입력받은 요소로 초기화
}
// 평균 구하기
double avg = 0;
for(int i = 0; i < N; i++) {
avg += arr[i]; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
// 평균 점수를 넘는 인원 수 구하기
double count = 0;
for(int i = 0; i < N; i++) {
if(arr[i] > avg) {
count++;
}
}
평균을 넘은 인원을 구했다. 그럼 최종적으로, N명중에 몇 명이 평균을 넘었는지 '비율(%)' 표현해야한다.
즉, 전체 인원 수 중에서 평균 넘는 사람이 몇 % 나 되는지를 구하면 되는 것이므로, 다음과 같이 해주면 된다.
int N;
cin >> N;
// 동적 배열 선언 및 생성
int* arr = new int[N]; // 혹은 int* arr = (int*)malloc(sizeOf(int) * size)
for(int i = 0; i < N; i++) {
cin >> arr[i]; // i ~ N - 1 까지 입력받은 요소로 초기화
}
// 평균 구하기
double avg = 0;
for(int i = 0; i < N; i++) {
avg += arr[i]; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
// 평균 점수를 넘는 인원 수 구하기
double count = 0;
for(int i = 0; i < N; i++) {
if(arr[i] > avg) {
count++;
}
}
// 평균을 넘는 인원 %
double result = (count / N) * 100;
마지막으로 출력문이다. C++에서 소수점을 고정하여 출력하는 방법은 크게 두 가지가 있다.
전통적 C 방식인 printf() 방식과, C++ 방식의 cout 이 있다.
이에 대한 내용은 이 전에 A/B 문제에서 다뤘으므로 링크로 남겨두겠다.
https://st-lab.tistory.com/212
[백준] 1008번 : A/B - [C++]
www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 알고리즘 [접근 방법] 이 문제는 '부동 소수점'에 대한 이해를 필요로..
st-lab.tistory.com
다음 두 가지 방식으로 출력을 할 수 있다.
printf("%.3lf%%", result); // %기호를 출력하려면 %% 를 해야한다.
// or
cout << fixed;
cout.percision(3);
cout << result << "%";
앗, 그러면 반올림 처리는 어떻게 해야하나요? 라고 하실 수 있는데, 참 감사하게도, 두 방식 모두 고정 된 소수점 아래에서 알아서 반올림을 해준다.
다음으로 vector 클래스를 사용하는 방식이다.
배열을 좀 더 동적으로 쉽게 사용 할 수 있도록 만들어진 클래스인데, 해당 클래스에 모두 다뤄볼 수는 없으니... 만약 vector에 대해 모른다면 기본적인 메소드는 검색해보시기를 바란다. (여기서는 주석정도로만 사용하겠다.)
각 테스트 케이스에 대해서는 N과 N개의 요소들이 입력이 된다. 즉, 다음과 같이 만들 수 있다.
int N;
cin >> N;
// 동적 배열 선언 및 생성
vector<int> vec;
for(int i = 0; i < N; i++) {
int value;
cin >> value;
vec.push_back(value); // 벡터의 맨 마지막 원소 뒤에 원소 추가
}
사실 vector클래스를 사용하면 vector 자체가 가변적이라서 N 을 넘겨 줄 필요가 없다.
예로들어 vec = {1, 2, 3, 4} 라고 하자.
근데, vec에 1개를 더 추가한다고 하면, 에러가 나는 것이 아닌 그만큼 증량을 하여 크기를 늘려준다. 예로들어 v.push_back(7) (벡터의 맨 마지막 원소 뒤에 원소를 추가) 을 쓰면, vec = {1, 2, 3, 4, 7} 이 되는 것이다.
그 다음 마찬가지로 평균을 구해야 한다. 평균은 (합계 / 개수) 이므로, 다음과 같이 해줄 수 있다.
int N;
cin >> N;
// 동적 배열 선언 및 생성
vector<int> vec;
for(int i = 0; i < N; i++) {
int value;
cin >> value;
vec.push_back(value); // 벡터의 맨 마지막 원소 뒤에 원소 추가
}
// 평균 구하기
double avg = 0;
for(int i = 0; i < N; i++) {
avg += vec[i]; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
참고로 vec.at(i) 방식으로 벡터 내의 i 번째 원소를 접근 할 수 있는 방식이 있고, 기존의 배열처럼 index 형식으로 접근 할 수 있다.
아니면, for-each문으로 해도 된다.
평균을 구했으니, 평균을 넘는 인원 수를 체크해보자.
int N;
cin >> N;
// 동적 배열 선언 및 생성
vector<int> vec;
for(int i = 0; i < N; i++) {
int value;
cin >> value;
vec.push_back(value); // 벡터의 맨 마지막 원소 뒤에 원소 추가
}
// 평균 구하기
double avg = 0;
for(int i = 0; i < N; i++) {
avg += vec[i]; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
// 평균 점수를 넘는 인원 수 구하기 (for-each)
double count = 0;
for(auto &val : vec) {
if(val > avg) {
count++;
}
}
// 평균을 넘는 인원 %
double result = (count / N) * 100;
위와 같이 for-each문을 사용하여 풀이 할 수도 있다. (for-each 부분은 C++11 부터 지원하므로 참고 바란다.)
그 다음에 출력을 해주면 끝나는 것이다.
단일 케이스에 대해 만들었으니, 이제 이를 토대로 C 입력에 따른 반복만 해주면 된다. 함수로 만들던, 그냥 for문안에 넣건 상관은 없다.
필자는 이해하기 편하도록 함수로 만들겠다.
- 4가지 방법을 사용하여 풀이한다.
이전 포스팅과 여타 다를 바 없이 기본 입출력 빠른 입출력 방식을 비교하고자 하는데, 다만 위 알고리즘 설명에서 크게 두 가지 방식(배열 동적 할당과 벡터)을 설명했으므로, 이에 대해서도 한 번 같이 교차하여 테스트 해보고자 한다.
그러니 이번에는 다음과 같이 테스트 해보고자 한다.
1. 배열 동적 할당 + 기본 입출력
2. vector + 기본 입출력
3. 배열 동적 할당 + 향상 된 입출력
4. vector + 향상 된 입출력
- 풀이
- 방법 1 : [배열 동적 할당 + 기본 입출력]
#include <iostream>
using namespace std;
void func();
int main(int argc, const char *argv[]) {
int C;
cin >> C; // test case
for (int i = 0; i < C; i++) {
func();
}
return 0;
}
void func() {
int N;
cin >> N;
// 동적 배열 선언 및 생성
int *arr = new int[N]; // 혹은 int* arr = (int*)malloc(sizeOf(int) * size)
for (int i = 0; i < N; i++) {
cin >> arr[i]; // i ~ N - 1 까지 입력받은 요소로 초기화
}
// 평균 구하기
double avg = 0;
for (int i = 0; i < N; i++) {
avg += arr[i]; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
// 평균 점수를 넘는 인원 수 구하기
double count = 0;
for (int i = 0; i < N; i++) {
if (arr[i] > avg) {
count++;
}
}
// 평균을 넘는 인원 %
double result = (count / N) * 100;
cout << fixed;
cout.precision(3);
cout << result << "%\n";
delete[] arr; // 동적 할당을 할 경우에는 더이상 안쓰는 경우 반드시 메모리 해제를 해야한다.
}
가장 기본적인 방법이라 할 수 있겠다.
여기서 중요한 점은 동적 할당을 할 경우 delete 키워드를 통해 반드시 메모리를 해제해주어야 한다.(사실 대부분의 경우 프로세스가 종료되면 알아서 해제해주기는 하지만, 좋지 않은 방식이기도 하고, 이후 지속적으로 운용해야하는 서비스를 만들게 될 경우에는 메모리 해제를 안하게 되면 위험하므로, 동적할당의 경우 반드시 명시적으로 해제를 해주는 버릇을 들여주어야 한다.
만약 malloc을 통해 생성했을 경우에는 delete가 아닌 free(arr); 을 해주시기를 바란다.
- 방법 2 : [vector + 기본 입출력]
배열 동적 할당이 아닌 vector 을 사용하여 풀이하는 방법이다. 단, 이 때 vector을 쓰고자 한다면, vector 헤더를 포함해야 한다.
#include <iostream>
#include <vector>
using namespace std;
void func();
int main(int argc, const char *argv[]) {
int C;
cin >> C; // test case
for (int i = 0; i < C; i++) {
func();
}
return 0;
}
void func() {
int N;
cin >> N;
// 동적 배열 선언 및 생성
vector<int> vec;
for (int i = 0; i < N; i++) {
int value;
cin >> value;
vec.push_back(value); // 벡터의 맨 마지막 원소 뒤에 원소 추가
}
// 평균 구하기
double avg = 0;
for (auto &val : vec) {
avg += val; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
// 평균 점수를 넘는 인원 수 구하기 (for-each)
double count = 0;
for (auto &val : vec) {
if (val > avg) {
count++;
}
}
// 평균을 넘는 인원 %
double result = (count / N) * 100;
cout << fixed;
cout.precision(3);
cout << result << "%\n";
}
알고리즘은 그대로라 크게 어렵지는 않았을 것이다.
vector의 경우 포인터 벡터일 경우 소멸자를 재정의 하거나 직접 지워주어야 하는데, 여기서는 primitive 타입이기 때문에 굳이 해주지 않더라도 함수가 끝나면 자동으로 소멸자를 실행해준다.
- 방법 3 : [배열 동적 할당 + 향상 된 입출력]
다음으로 동적 할당 방식에서 향상 된 입출력을 사용하는 방법이다.
#include <iostream>
using namespace std;
void func();
int main(int argc, const char *argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int C;
cin >> C; // test case
for (int i = 0; i < C; i++) {
func();
}
return 0;
}
void func() {
int N;
cin >> N;
// 동적 배열 선언 및 생성
int *arr = new int[N]; // 혹은 int* arr = (int*)malloc(sizeOf(int) * size)
for (int i = 0; i < N; i++) {
cin >> arr[i]; // i ~ N - 1 까지 입력받은 요소로 초기화
}
// 평균 구하기
double avg = 0;
for (int i = 0; i < N; i++) {
avg += arr[i]; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
// 평균 점수를 넘는 인원 수 구하기
double count = 0;
for (int i = 0; i < N; i++) {
if (arr[i] > avg) {
count++;
}
}
// 평균을 넘는 인원 %
double result = (count / N) * 100;
cout << fixed;
cout.precision(3);
cout << result << "%\n";
delete[] arr;
}
여기서 중요한 점은 sync_with_stdio 를 통해 C의 io와 C++의 io 간 동기화를 끊어주었기 때문에 반드시 한쪽만 써야한다는 점이다.
- 방법 4 : [vector + 향상 된 입출력]
다음으로 vector를 사용하면서 향상 된 입출력을 사용하는 방법이다.
#include <iostream>
#include <vector>
using namespace std;
void func();
int main(int argc, const char *argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int C;
cin >> C; // test case
for (int i = 0; i < C; i++) {
func();
}
return 0;
}
void func() {
int N;
cin >> N;
// 동적 배열 선언 및 생성
vector<int> vec;
for (int i = 0; i < N; i++) {
int value;
cin >> value;
vec.push_back(value); // 벡터의 맨 마지막 원소 뒤에 원소 추가
}
// 평균 구하기
double avg = 0;
for (auto &val : vec) {
avg += val; // 모든 성적 누적합
}
avg = avg / N; // 누적합에 대해 N으로 나눈다.
// 평균 점수를 넘는 인원 수 구하기 (for-each)
double count = 0;
for (auto &val : vec) {
if (val > avg) {
count++;
}
}
// 평균을 넘는 인원 %
double result = (count / N) * 100;
cout << fixed;
cout.precision(3);
cout << result << "%\n";
}
- 성능
채점 번호 : 36403264 - 방법 4 : vector + 향상 된 입출력
채점 번호 : 36403257 - 방법 3 : 배열 동적 할당 + 향상 된 입출력
채점 번호 : 36403252 - 방법 2 : vector + 기본 입출력
채점 번호 : 36403249 - 방법 1 : 배열 동적 할당 + 기본 입출력
보면 그렇게 큰 차이가 나지 않는다.
- 정리
오늘은 동적 할당에 대해 간략하게나마 알아보았다. 사실 알고리즘을 풀 때에는 배열보다는 vector를 많이 쓰긴 한다. 이유는 일단 코딩할 때 크게 사이즈나 nullptr 에 대해 고려해 줄 필요가 없기 때문이다.
이 것만으로도 매우 강력한 도구임에는 틀림없지만, 반대로 순수 배열을 주로 사용하는 경우도 있다. 왜냐하면, 일단 아무래도 vector 자체가 하나의 클래스다보니 내부 구현에 의해 오버헤드가 일반 배열보다 클 수 밖에 없다.
그래서 알고리즘에서 대량의 데이터가 오고가는 경우, 혹은 한정 된 자원 안에서 철저한 메모리 관리가 필요한 경우에는 배열을 쓰기도 하니 여러분이 문제를 풀어보면서 자신이 편한 것으로 선택해 나아가면 될 것 같다.
혹여 이해가 안되거나 어려운 부분이 있다면 언제든 댓글 남겨주시기를 바란다.
'C++ - 백준 [BAEK JOON] > 1차원 배열' 카테고리의 다른 글
| [백준] 8958번 : OX퀴즈 - [C++] (6) | 2021.12.09 |
|---|---|
| [백준] 1546번 : 평균 - [C++] (0) | 2021.10.20 |
| [백준] 3052번 : 나머지 - [C++] (9) | 2021.10.06 |
| [백준] 2562번 : 최댓값 - [C++] (2) | 2021.08.17 |
| [백준] 10818번 : 최소, 최대 - [C++] (2) | 2021.07.23 |