How We Coding

[2018] 수들의 합 5

BOJ/Math2018. 7. 22. 13:26

### Math ###


[2018] 수들의 합 : http://boj.kr/2018


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
 
 
int main()
{
    int n;
    int L=0, R=0;
    int ans=0, sum=0;
    scanf("%d", &n);
 
    if(n&1) {
        for(int i=3; i<=n; i+=2)
            if(n%i == 0) 
                ans++;
        ans++;
    }
    else {
        for(int i=2; i<=n; i+=2)
            if(n%i == 0 && (n/i)&1)
                ans++;
    }
    printf("%d\n", ans); 
    return 0;
}
cs


1) 홀수의 경우

- 무조건 두개의 연속된 합으로 표현이 가능하다.

- 홀수로 나누어 떨어지면 연속된 수들의 합으로 가능하다. 

   예를들어 9는 3으로 나누어 떨어지므로 3+3+3 으로 표현이 가능하고, 중앙값 기준으로 양옆은 1씩 주고 받으면 가능하다, 숫자가 더있으면, 2씩, 3씩, 주고받으면 된다.


2) 짝수인 경우

- 짝수로 나누어 떨어지고, 그 몫이 홀수이면 가능하다.

   예를 들어 10은 2로 나누어 떨어지고, 그 몫은 5이다. 5는 두개의 수인 2와 3으로, 1과 4로 표현이 가능하다. 즉 1, 2, 3, 4 의 연속된 수로 표현이 가능해진다.

[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

티스토리툴바