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

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

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 빠른 이진 탐색 트리에 대한 이해 :: http://www.crocus.co.kr/641

2. Map STL

3. lower_bound 이해


위의 빨간 링크를 통해 이진 탐색을 어떻게 빠르게 처리할 지 우선적으로 생각해본다.


그 후 주석을 통해 내용을 확인해본다.(주석에 모든 내용을 다 기술해 두었습니다.)






이진 탐색 트리의 시간 복잡도


이진 탐색 트리는 트리의 구조에 따라 시간 복잡도가 달라진다.

삽입, 삭제

평균 :: 


최악(한 방향으로만 계속 뻗어있는 트리일 경우) :: 


이 이론적 알고리즘을 생각하고 이진 탐색 트리를 어떻게 하면 더 빠르게 삽입, 탐색을 가능하게 할 지 생각해보자.

 

아래 과정을 이해하고 접목한다면 삽입, 탐색이 최악과 관계없이  결이 된다.




이 문제는 알고리즘 그대로를 이용한 코드로 문제를 제출할 시 으로 시간 초과(TLE)를 받게 된다.


따라서 아래의 코드를 통해 에 해결하도록 한다.


아래의 코드를 이용하면 결국 Tree의 구조까지 Map속에 있는 구조체에 의해 모두 파악할 수 있게 된다. 


소스 코드 : 


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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
typedef struct _INFO_ {
    int left;
    int right;
    long long int cnt;
}INFO;
 
map<int, INFO> m;
 
int main()
{
    int n;
    long long int ans = 0;
 
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        int max = -1, min = -1;
 
        scanf("%d"&val);
 
        // 첫번째로 들어오는 값에 대한 예외 처리
        if (!i)
        {
            m[val].cnt = 0;
            printf("%lld\n", m[val].cnt);
            continue;
        }
 
        // 반복자가 map의 끝을 가리키게 한다.
        // it--를 하면 map에서 마지막 값을 가리키게 된다.
        auto it = m.end();
        it--
 
        // 마지막 값이 현재 들어온 값보다 작다면
        // 현재 들어온 값보다 작은 것 중 가까운 값은 마지막 값이다.
        // 현재 들어온 값이 가장 크니 max 는 없다.
        if (it->first < val)
        {
            min = it->first;
            max = -1;
        }
 
        // 마지막 값이 현재 들어온 값보다 크거나 같다면
        // (이미 조건에서 같은 값은 들어오지 않는다고 되어있긴 하다.)
        else
        {
            // lower_bound로 현재 들어온 값보다 크거나 같은 것 중 
            // 가장 가까운 값의 위치에 반복자를 설정한다.
            it = m.lower_bound(val);
 
            // 반복자가 map의 처음을 가리키고 있다면
            // 현재 들어온 값이 가장 작은 값이라는 의미이므로 min은 없다.
            // max는 map의 처음인 값이 현재 값보다 큰 값 중 가장 가까운 값이다.
            if (it == m.begin())
            {
                min = -1;
                max = it->first;
            }
 
            // 반복자가 map의 처음위치가 아닌 위치라면
            // 즉, map의 처음과 끝이 아닌 사이의 값이 들어왔다면
            // max는 현재 반복자가 가리키는 곳을 의미한다.
            // min은 현재 반복자가 가리키는 바로 전 단계를 의미한다.
            else
            {
                max = it->first;
                it--;
                min = it->first;
            }
            
        }
 
        // 앞의 식으로 인해 구해진 min, max로 부터
        // min과 max가 둘다 -1이 아니라면 즉, 사잇값이라면
        if (min != -&& max != -1)
        {
            // max의 왼쪽에 노드가 없다면 달아준다.
            if (m[max].left == 0)
            {
                m[max].left = val;
                m[val].cnt = m[max].cnt + 1;
            }
 
            // max의 왼쪽에 노드가 있다면
            // min의 오른쪽에 노드가 달리는 것이 자명하다.
            // (트리를 그려보면 알 수 있다.)
            else
            {
                m[min].right = val;
                m[val].cnt = m[min].cnt + 1;
            }
        }
 
        // min만 -1이라면
        // 즉, 가장 작은 값이라면
        // max밖에 없으니 max의 왼쪽에 달린다.
        else if (min == -&& max != -1)
        {
            m[max].left = val;
            m[val].cnt = m[max].cnt + 1;
        }
 
        // max만 -1이라면
        // 즉, 가장 큰 값이라면
        // min밖에 없으니 min의 오른쪽에 달린다.
        else if (min != -&& max == -1)
        {
            m[min].right = val;
            m[val].cnt = m[min].cnt + 1;
        }
 
        // 결과 값을 누적한다.
        ans += m[val].cnt;
        printf("%lld\n", ans);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





일반 알고리즘을 이용한 소스 코드(TLE)

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
typedef struct _INFO_ {
    int left;
    int right;
    int cnt;
}INFO;
 
map<int, INFO> m;
 
int main()
{
    int n;
    int ans = 0;
    
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        int max = -1, min = -1;
 
        scanf("%d"&val);
 
        if (!i)
        {
            m[val].cnt = 0;
            printf("%d\n", m[val].cnt);
 
            continue;
        }
 
        for (auto it = m.begin(); it != m.end(); it++)
        {
            if (it->first < val)
                min = it->first;
 
            else if (max == -&& it->first > val)
                max = it->first;
 
            if (min != -&& max != -1)
                break;
        }
 
        if (min != -&& max != -1)
        {
            if (m[max].left == 0)
            {
                m[max].left = val;
                m[val].cnt = m[max].cnt + 1;
            }
            else
            {
                m[min].right = val;
                m[val].cnt = m[min].cnt + 1;
            }
        }
 
        else if (min == -&& max != -1)
        {
            m[max].left = val;
            m[val].cnt = m[max].cnt + 1;
        }
 
        else if (min != -&& max == -1)
        {
            m[min].right = val;    
            m[val].cnt = m[min].cnt + 1;
        }
 
        ans += m[val].cnt;
        printf("%d\n", ans);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[11052번] 붕어빵 판매하기  (0) 2017.03.06
[1699번] 제곱수의 합  (0) 2017.03.06
[2957번] 이진 탐색 트리  (0) 2017.03.06
[5637번] 가장 긴 단어  (2) 2017.03.06
[2294번] 동전 2  (0) 2017.03.06
[13913번] 숨바꼭질 4  (2) 2017.03.04