[바미] 통계학

문제

 

https://www.acmicpc.net/problem/2108https://www.acmicpc.net/problem/26069

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0], 10);
const connections = input.slice(1);

const danceSet = newSet(); // Set을 생성할 때 new Set()으로 생성합니다.
danceSet.add('ChongChong');

// 각 사람의 연결 관계를 탐색for (let i = 0; i < N; i++) {
    const [A, B] = connections[i].split(' ');

    // A 또는 B가 무지개 댄스를 추고 있으면, 다른 사람도 추게 된다.if (danceSet.has(A) || danceSet.has(B)) {
        danceSet.add(A);
        danceSet.add(B);
    }
}

console.log(danceSet.size);

문제 해설

이 문제는 기본적인 통계값을 계산하는 문제로 다음 네 가지 통계값을 구해야 하는 문제입니다.

 

• 산술평균: 주어진 N개의 수의 합을 N으로 나눈 값
  • 이 값은 소수점 첫째 자리에서 반올림하여 출력해야 함.
• 중앙값: 주어진 N개의 수를 오름차순으로 정렬했을 때, 가운데 위치하는 값.
  • 문제에서 N이 홀수라고 명시되어 있으므로, 항상 중간 위치에 하나의 값이 존재함.
• 최빈값: 주어진 N개의 수 중에서 가장 자주 나타나는 값을 의미.
  • 여러 개의 최빈값이 있을 경우, 두 번째로 작은 값을 출력해야 함.
• 범위: 주어진 N개의 수 중 최댓값과 최솟값의 차이.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

4가지 통계값에 대한 시간 복잡도를 계산해야합니다.

 

• 산술평균
  • 숫자들의 합을 계산하는 데 걸리는 시간은 O(N)이 걸림.
• 중앙값
  • 배열을 정렬하는 데 걸리는 시간은 O(N log N).
  • 중간 값을 찾는 데 걸리는 시간은 O(1).
  • 따라서, 중앙값을 계산하는 시간복잡도는 O(N log N)가 됨.
• 최빈값
  • 주어진 숫자들의 빈도를 계산하는 데 걸리는 시간은 O(N).
  • 빈도를 확인하고 최빈값을 찾는 데 걸리는 시간도 O(N).
  • 최빈값 후보군을 정렬하는 데 걸리는 시간은 O(k log k)임. 여기서 k는 고유한 숫자의 개수.
    최악의 경우 k는 N과 같으므로 O(N log N)가 됨.
• 범위
  • 이미 배열이 정렬된 상태이기 때문에 가장 첫 번째와 마지막 원소만 확인하면 됨. 따라서 배열의 최댓값과 최솟값을 찾는 시간은 O(1).

따라서 이 코드의 전체 시간복잡도는 정렬을 포함하기 때문에 O(N log N)가 됩니다.

 

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

마찬가지로 4가지 통계값에 대한 공간 복잡도를 계산해야합니다.

 

• 산술평균
  • 숫자들의 합을 저장하기 위해 O(1)의 추가 공간이 필요함
• 중앙값
  • 정렬된 배열을 사용하지만 입력 데이터 자체에서 정렬되어 추가적인 공간을 사용하지 않기 때문에 공간복잡도는 O(1)이 됨.
• 최빈값
  • 빈도를 저장하기 위해 Map을 사용함. 최악의 경우 모든 숫자가 고유한 값을 가지면 Map은 N개의 항목을 저장해야 하기 때문에 공간복잡도는 O(N).
• 범위
  • 정렬된 배열에서 최댓값과 최솟값을 찾기 위해 추가적인 공간이 필요하지 않기 때문에 공간복잡도는 O(1).

따라서 이 코드의 공간복잡도는 O(N)입니다.