×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,488,492명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)

수가 다음과 같이 있다고 가정해보자.


3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2


이때 과반수가 넘는 수는 '1'임을 알 수 있다.


과반수가 넘는 수를 찾는 방법에는 다양한 알고리즘이 존재하는데 한번 생각해보자.


1. O(N^2)


부르트포스를 이용하여 문제를 풀되 자신보다 뒤에 나오는 수가 있다면 카운팅해주며 과반수인지 파악해준다.


말그대로 최악의 방법이다.



2. O(NlgN)


정렬을 하고 난 후, 그대로 순차적으로 읽어가며 카운팅을 해주면 된다.


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
#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int arr[100];
int main()
{
    int n;
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++)
        scanf("%d"&arr[i]);
 
    sort(arr, arr + n);
 
    int cnt = 1;
 
    for (int i = 1; i < n; i++)
    {
        if (arr[i] == arr[i - 1])
            cnt++;
        else
        {
            if (cnt > n / 2)
                return !printf("과반수가 넘는 수 :: %d\n", arr[i - 1]);
            else
                cnt = 1;
        }
 
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


3. O(N)


계수정렬

http://www.crocus.co.kr/470


계수정렬을 이용하여 문제를 해결 할 수 있다.

이때 수가 커진다면 좌표 압축을 통해 수의 범위를 줄여 계수 정렬을 해볼 수 있으나 메모리 공간의 낭비가 심할 수 있다.




과반수의 개념을 이용


어떤 집단에서 과반수라면 그 수는 항상 다른 수들과 상쇄 시켰을 때 1개 이상이 남게 될 것이다.


3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2 에서 상쇄를 시켜나가보자.



3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2


2 2 1 1 1 1 2 1 3 2 1 1 1 2


2 2 1 1 1 1 2 1 3 2 1 1 1 2


2 1 1 1 2 1 3 2 1 1 1 2


1 1 2 1 3 2 1 1 1 2


1 1 3 2 1 1 1 2


1 2 1 1 1 2


1 1 1 2


1 1


따라서 우리는 이 과정을 스택을 이용하여 해결한다면 O(N)만에 해결 할 수 있다.


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
#include <iostream>
#include <cstdio>
#include <stack>
 
using namespace std;
 
int arr[100];
int main()
{
    stack<int> st;
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        int val;
        cin >> val;
 
        if (st.empty())
            st.push(val);
        else
        {
            if (st.top() != val)
                st.pop();
            else
                st.push(val);
        }
 
        arr[i] = val;
    }
    if (st.empty())
        cout << "과반수 이상되는 수가 없습니다. " << endl;
    else
    {
        // 실제 그 수가 과반수인지 한번 더 확인
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (arr[i] == st.top())
                cnt++;
 
        if (cnt > n / 2)
            cout << "과반수 이상인 수 :: " << st.top() << endl;
        else
            cout << "과반수 이상되는 수가 없습니다. " << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus









'Applied > 알고리즘' 카테고리의 다른 글

확장 유클리드 알고리즘  (2) 2018.04.18
모듈러 연산(Modular Arithmetic)  (4) 2018.04.18
과반수 찾기 알고리즘  (4) 2018.04.08
단절점(Articulation Point), 단절선(Articulation Bridge)  (0) 2018.02.21
[STL] qsort 구현  (0) 2018.02.02
해시 테이블(Hash Table)  (0) 2018.01.31
  1. It 2019.12.18 08:11

    안녕하세요. 글 잘읽었습니다

    스택으로 구현한 알고리즘을 보고 궁금한점이 생겨 글남깁니다.

    마지막부분에 한번더 확인해주는 과정이 필요한이유가무엇인가요?? 예외가있어 그러는 것같은데 사례하나만 들어주시면 감사하겠습니다.

    • 가누 2019.12.18 09:11 신고

      3
      1 2 3
      이 케이스는 스택이 비지않으나 3이 과반수는 아닙니다.

    • It 2019.12.18 10:49

      아하 답변 감사드립니다!

      위의 스택을이용한 시간복잡도가 O(n)이라고 하셨는데

      밑에 확인하는 과정에서 for문을 한번 더 돌리므로 O(n)이라고 할수 있나요??

      다시 한번 검증하는 과정이 없으면 O(n)은 이해가가는데...

    • 가누 2019.12.18 17:40 신고

      O(2N)==O(N)입니다