How We Coding

[5639] 이진 검색 트리

BOJ/Data Structure2018. 7. 22. 12:30

### Tree Traversal ###


[5639] 이진 검색 트리 : http://boj.kr/5639


<소스코드>


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
#include <stdio.h>
 
int arr[10001];
 
void post(int L, int R)
{
    if(L >= R) return ;
    int k = L+1;
    while(k < R && arr[k] < arr[L]) k++;
    post(L+1, k);
    post(k, R);
    printf("%d\n", arr[L]);
}
 
int main()
{
    int n;
    int idx=0;
    while(scanf("%d", &n) == 1) {
        arr[idx++] = n;
    }
    
    post(0, idx);
    return 0;
}
 
cs

>> 전위위회의 결과를 준 상태에서 후위순휘의 결과를 출력하는 문제.

>> 전위순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회를 한다. 

>> 후위순회를 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 순회를 한다.

>> 이진탐색트리는 왼쪽 서브트리는 루트보다 작은 키값들을 가지며, 오른쪽 서브트리는 루트보다 큰 키 값을 가진다. 

>> 이 특징을 이용하여 왼쪽 서브트리와 오른쪽 서브트리의 데이터들을 구분할 수 있다.

     그럼 왼쪽 서브트리의 데이터 - 오른쪽 서브트리의 데이터 - 루트 순으로 출력을 하면 된다. 

'BOJ > Data Structure' 카테고리의 다른 글

[1655] 가운데를 말해요  (0) 2018.07.22
[2529] 부등호  (0) 2018.07.22

[1655] 가운데를 말해요

BOJ/Data Structure2018. 7. 22. 12:03

### Priority Queue ###


[1655] 가운데를 말해요 : http://boj.kr/1655


<소스코드>


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
#include <cstdio>
#include <queue>
using namespace std;
 
int main()
{
    int n, k;
    scanf("%d", &n);
 
    priority_queue<int> minQ, maxQ;
    scanf("%d", &k);
    printf("%d\n", k);
    maxQ.push(k);
 
    for(int i=1; i<n; i++) {
        scanf("%d", &k);
        if(i&1) {
            if(maxQ.top() < k) minQ.push(-k);
            else {
                maxQ.push(k); minQ.push(-maxQ.top()); maxQ.pop();
            }
        }
        else {
            if(-minQ.top() > k) maxQ.push(k);
            else {
                minQ.push(-k); maxQ.push(-minQ.top()); minQ.pop();
            }
        }
        printf("%d\n", maxQ.top());
    }
    return 0; 
}
cs

>> max Heap 과 min Heap 을 이용하여, 그때그때마다 중앙값을 알 수 있다.


- input : 1 5 2 10 -99 7 5 순이라면


1) max Heap : 1

   min Heap : empty


2) max Heap : 1

    min Heap : 5


3) max Heap : 1 2

    min Heap : 5


4) max Heap : 1 2

    min Heap : 5 10


5) max Heap : -99 1 2

    min Heap : 5 10


6) max Heap : -99 1 2

    min Heap : 5 7 10


이런식으로 진행이 된다. 그때그때 마다의 중앙값은 max Heap 의 루트가 된다.




'BOJ > Data Structure' 카테고리의 다른 글

[5639] 이진 검색 트리  (0) 2018.07.22
[2529] 부등호  (0) 2018.07.22

[2529] 부등호

BOJ/Data Structure2018. 7. 22. 11:54

### Stack ###


[2529] 부등호 : http://boj.kr/2529


<소스코드>


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
#include <stdio.h>
 
int main()
{
    int n;
    int nextL=8, nextS=1;
    long long int ansL=9LL, ansS=0LL, ans=0LL;
    long long int arrL[10], arrS[10];
    int Lidx=0, Sidx=0;
    char buf[10];
    int factL=10, factS=10;
    scanf("%d", &n); 
 
    for(int i=0; i<n; i++) {
        char ch;
        scanf(" %c", &ch);
        if(ch == '<') {
            if(i == n-1 && nextL == 0) arrL[Lidx++] = 0LL;
            ansL = 1LL*nextL*factL + ansL;
            arrS[Sidx++] = ansS; ansS = nextS; factS = 1;
        }
        else {
            arrL[Lidx++] = ansL; ansL = nextL; factL = 1;
            ansS = 1LL*nextS*factS + ansS;
        }
        nextL--; factL *= 10;
        nextS++; factS *= 10;
    }
    arrL[Lidx++] = ansL;
    arrS[Sidx++] = ansS;
 
    for(int i=0; i<Lidx; i++) 
        printf("%lld", arrL[i]);
    puts("");
    for(int i=0; i<Sidx; i++)
        printf("%lld", arrS[i]);
    puts("");
 
    return 0;
}
cs


>> 큰수의 경우 '>' 를 만나기 전까지 앞에다 갱신을 해주면 된다 '<' 를 만나면 남은 최대값으로 반복.


>> 알고리즘 분류에 그리디와 위상정렬로 되어 있고, kks227 님도 위상정렬로 해설을 하셨는데, 

     한편으로 그리디는 맞다고 생각하지만, 위상정렬은 왜 위상정렬인지 아직도 모르겠다. 

    

>> 그럼에도 불구하고 스택으로 분류를 한 이유는 다른 사람이 스택으로 풀었기 때문이고, 아이디어는 내가 푼 것과 비슷하기 때문이다. 

>> 그분이 더 머리가 좋아보인다...ㅜ (아래는 그 코드)



- coded by t1234


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
#include <cstdio>
#include <stack>
int k, n=9;
char a[15];
std::stack<int> st;
 
void f() {
    while(!st.empty()) printf("%d", st.top()), st.pop();
}
 
int main() {
    int i;
    scanf("%d", &k);
    st.push(n--);
    for(i=0; i<k; i++) {
        scanf("%s", &a[i]);
        if(a[i]=='>') f();
        st.push(n--);
    }
    f();
    puts("");
    n = 0;
    st.push(n++);
    for(i=0; i<k; i++) {
        if(a[i]=='<') f();
        st.push(n++);
    }
    f();
    return 0;
}
cs



'BOJ > Data Structure' 카테고리의 다른 글

[5639] 이진 검색 트리  (0) 2018.07.22
[1655] 가운데를 말해요  (0) 2018.07.22

티스토리툴바