[백준] 2587번 : 대표값2 | C++

 

1. 문제 상세

 

https://www.acmicpc.net/problem/2587

 

 

 

2. 문제 접근

 

다섯 개의 숫자를 입력받고, 수들의 평균을 출력하고, 정렬 후 중앙값인 3번째 값을 출력하자.

 

이번에는 정렬 알고리즘에 선택 정렬을 사용해보자.

 

■ 선택 정렬

선택 정렬 알고리즘은 최솟값을 찾고 그 값을 맨 앞부터 넣어서 순차적으로 정렬해가는 알고리즘이다. 

 

배열의 크기가 N 이라고 해보자.

선택 정렬은 첫 번째 원소부터 두 번째, 세 번째, ... N 번째 원소까지 비교 후 최솟값을 찾아

그 값을 맨 앞으로 가져온다.

첫 과정이 끝나면 두 번째 원소와 세 번째, 네 번째, ... N 번째 원소까지 비교 후 최솟값을

두 번째 위치로 가져온다.

이 정렬을 계속 수행하면 마지막 값은 자동으로 정렬되기 때문에 N - 1 번 수행했을 때 모두 정렬된다.

따라서 최솟값을 찾아 앞쪽으로 순서대로 가져오는 과정을 총 N - 1 번 반복한다.

 

아래는 선택 정렬의 예시이다.

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

 

선택 정렬의 시간복잡도를 확인해보자.

비교 횟수는 1부터 N - 1 까지의 합이므로 

이 된다.

 

교환은 최솟값을 찾는 비교가 끝나고 실행한다.

따라서 교환 횟수는 총 비교 과정의 반복 횟수 N - 1 에 교환 과정에 필요한 교환 3을 곱해 3(n - 1) 이 된다.

 

따라서 선택 정렬의 시간복잡도는 O(N2)이다.

 

선택 정렬 또한 다른 정렬의 시간복잡도와 비교해보면 꽤 비효율적이라는 것을 볼 수 있다.

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

 

문제풀이를 통해 선택 정렬을 구현해보자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int a[5], ave = 0, temp, min;

    for (int i = 0; i < 5; i++) cin >> a[i];

    for (int i = 0; i < 5; i++) ave += a[i];
    cout << ave / 5 << endl;

    for (int i = 0; i < 5; i++) {
        min = i;
        for (int j = i + 1; j < 5; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }

        if (min != i) {
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
    cout << a[2];
}

 

크기가 5인 정수형 배열 a, 정수형 변수 ave, temp, min 을 선언하고 ave 를 0으로 초기화한다.

 

for문으로 i 가 0부터 5보다 작을 때 1씩 더하며 반복, cin 으로 a 의 i 번 원소에 값을 입력받아 저장한다.

// 배열의 값 입력받기

 

for문으로 i 가 0부터 5보다 작을 때 1씩 더하며 반복, ave 에 a 의 i 번 원소의 값을 더한다.

cout 으로 ave 를 5로 나눈 값과 개행문자를 출력한다.

// 입력받은 5개 수의 평균 구하기

 

for문으로 i 가 0부터 5보다 작을 때 1씩 더하며 반복한다. // N - 1번 반복 실행.

min 을 i 값으로 초기화한다. // 정렬되지 않은 맨 앞의 값을 기준으로 한다.

다시 for문으로 j 가 i + 1 부터 5보다 작을 때 1씩 더하며 반복한다.

// 정렬되지 않은 맨 앞의 값부터 맨 뒤의 값까지 비교하며 최솟값을 찾는다.

반복에서는 if문으로 a 의 j 번 원소가 min 번 원소보다 작다면 min 에 j 값을 저장한다.

// 작은 값 저장하기.

반복이 끝나면 if문으로 min 이 i 값과 다를 때 a 의 i 번 원소와 min 번 원소를 교환한다.

// 맨 앞의 값이 최솟값이라면 자리변경 X

 

모든 반복이 끝나면 cout 으로 a 의 2번 원소를 출력한다. // 3번째 값, 즉 중앙값을 출력.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

이미지 및 참고 글 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

이번에는 정렬 알고리즘 중 하나인 선택 정렬을 사용해 보았다.