How We Coding

[3649] 로봇 프로젝트

BOJ/Parametric Search2018. 7. 24. 13:59

### Sort + Binary Search ###


[3649] 로봇 프로젝트 : http://boj.kr/3649


<소스코드>


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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int x, n;
vector<int> lego;
 
void solve()
{
    for(int i=0; i<n-1; i++) {
        int cur = lego[i];
        if(binary_search(lego.begin()+i+1, lego.end(), x-cur)) {
            printf("yes %d %d\n", cur, x-cur);
            return ;
        }
    }
    puts("danger");
}
 
int main()
{
    while(scanf("%d", &x) == 1) {
        scanf("%d", &n);
        lego = vector<int>(n);
        for(int i=0; i<n; i++) {
            scanf("%d", &lego[i]);
        }
 
        x *= 10000000;
        sort(lego.begin(), lego.end());
        solve();
    }
}
 
 
cs

>> 정렬 후 i 번째 값과 x-i번째 값이 [i+1, n-1] 구간에 존재하는지 확인. 

>> 시간복잡도 O(N*logN)

'BOJ > Parametric Search' 카테고리의 다른 글

[13905] 세부 (다른방법으로 풀어보기)  (0) 2018.07.24
[1939] 중량제한  (0) 2018.07.24

[13905] 세부 (다른방법으로 풀어보기)

BOJ/Parametric Search2018. 7. 24. 02:15

### Parametric Search + BSF ###


[13905] 세부 : http://boj.kr/13905


- 다익스트라 or MST+LCA 로도 풀 수 있다고 한다. 나중에 도전해봐야겠다..!!


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int to, w; };
 
int n, m;
int s, e;
vector<P> g[100001];
 
bool isPossible(int mid)
{
    queue<int> q;
    q.push(s);
 
    vector<bool> visited(n+1, 0);
    visited[s] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        for(auto &p : g[cur]) {
            int next = p.to;
            int w = p.w;
            if(!visited[next] && mid <= w) {
                if(next == e) return 1;
                visited[next] = 1;
                q.push(next);
            }
        }
    }
    return 0;
}
 
int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &e);
 
    while(m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back((P){b, c});
        g[b].push_back((P){a, c});
    }
 
    if(s == e) return !printf("0\n");
 
    int S=1, E=1000000;
    while(S <= E) {
        int mid = (S+E)/2;
        if(isPossible(mid)) S = mid+1;
        else E = mid-1;
    }
    printf("%d\n", S-1);
    return 0;
}
 
cs

>> [1939] 중량제한 문제와 동일한 문제.

>> 근데 조건 한개가 다르다. 중량제한 문제는 출발지와 도착지가 서로 다르다고 명시가 되어 있는데, 위 문제는 그렇지 않다. 

>> 그래서 47 라인이 추가되었다.

'BOJ > Parametric Search' 카테고리의 다른 글

[3649] 로봇 프로젝트  (0) 2018.07.24
[1939] 중량제한  (0) 2018.07.24

[1939] 중량제한

BOJ/Parametric Search2018. 7. 24. 01:51

### Parametric Search + BFS ###


[1939] 중량제한 : http://boj.kr/1939


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int to, limit; };
 
int n, m;
int a, b, c;
vector<P> v[10001];
 
bool isPossible(int mid)
{
 
    queue<int> q;    
    q.push(a);
    
    vector<bool> visited(n+1, 0);
    visited[a] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        for(auto &p : v[cur]) {
            int next = p.to;
            int c = p.limit;
            if(!visited[next] && mid <= c) {
                if(next == b) return true;
                q.push(next);
                visited[next] = 1;
            }
        }
    }
    return false;
}
 
int main()
{
    scanf("%d%d", &n, &m);
 
    while(m--) {
        scanf("%d%d%d", &a, &b, &c);
        v[a].push_back((P){b, c});
        v[b].push_back((P){a, c});
    }
 
    scanf("%d%d", &a, &b);
    
    int s=1, e=1e9;
    while(s <= e) {
        int mid = (s+e)/2;
        if(isPossible(mid)) s = mid+1;
        else e = mid-1;
    }
    printf("%d\n", s-1); 
    return 0;
}
 
cs

>> 중량을 mid 로 설정했을 때, 이게 답이 될 수 있으면 탐색범위를 [mid+1, e] 로 좁혀간다. 

>> 답이될 수 없다면 [s, mid-1] 로 좁힌다.

'BOJ > Parametric Search' 카테고리의 다른 글

[3649] 로봇 프로젝트  (0) 2018.07.24
[13905] 세부 (다른방법으로 풀어보기)  (0) 2018.07.24

[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

[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

[RUNNINGMEDIAN] 변화하는 중간 값

PS/종만북2018. 7. 20. 01:58

[RUNNINGMEDIAN] 변화하는 중간 값 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN


### 우선순위 큐 (힙) ###


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long int lli;
const lli MOD = 20090711LL; 
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, b;
        lli a;
        scanf("%d%lld%d", &n, &a, &b);
 
        lli ai = 1983LL;
        lli ans = ai;
        priority_queue<lli> minH, maxH;
        maxH.push(ai);
        for(int i=1; i<n; i++) {
            ai = (1LL*ai*a+b)%MOD; 
            
            if(i&1) minH.push(-ai);
            else maxH.push(ai);
           
            if(-minH.top() < maxH.top()) {
                int a = maxH.top(); maxH.pop();
                int b = -minH.top(); minH.pop();
                maxH.push(b);
                minH.push(-a);
            }
            ans = (ans + maxH.top()) % MOD;
       }
        printf("%lld\n", ans);
    }
    return 0;
}
 
cs


>> 맥스힙에는 중간값 기준으로 중간값 포함, 그보다 작은 것들을, 민힙에는 중간값보다 큰 녀석들이 들어가게 된다. 


'PS > 종만북' 카테고리의 다른 글

[DICTIONARY] 고대어 사전  (0) 2018.05.22
[BOGGLE] 보글게임  (0) 2018.04.30
[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)

PS/Topcoder training2018. 7. 16. 12:50

### 전체탐색 ###


### SRM 484 Div2 Level 1 ###


<소스코드>


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
#include <string>
using namespace std;
 
class NumberMagicEasy {
public:
    int theNumber(string answer) {
        int card[4][8] = {{1, 2, 3, 4, 5, 6, 7, 8},
                         {1, 2, 3, 4, 9, 10, 11, 12},
                         {1, 2, 5, 6, 9, 10, 13, 14},
                         {1, 3, 5, 7, 9, 11, 13, 15}};
        
        int cnt=0;
        int check[17]={0};
        for(int i=0; i<4; i++) {
            if(answer[i] == 'Y') {
                cnt++;
                for(int k=0; k<8; k++) 
                    check[card[i][k]]++;
            }
            else {
                for(int k=0; k<8; k++) 
                    check[card[i][k]]--;
            }
        }
       
        for(int i=1; i<=16; i++) {
            if(cnt == check[i])
                return i;
        }
        return 0;
    }
};
 
cs


>> 정답이 있는 카드들에 대한 교집합 - 정닶이 없는 카드에 대해 차집합

>> 정답 카드의 갯수만큼 카운트된 숫자가 정답이 된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)

PS/Topcoder training2018. 7. 16. 12:26

### 전체탐색 ###


### SRM 433.5 Div2 Level 2 ###


<소스코드>


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
#include <vector>
#include <queue>
#include <string>
using namespace std;
 
int rSize, cSize;
int visited[51][51];
 
struct P { 
    int r, c; 
    P(int r, int c) : r(r), c(c) {}
};
 
bool safe(int r, int c)
{
    return (0 <= r && r < rSize) && (0 <= c && c < cSize);
}
 
class MazeMaker {
public:
    int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
        rSize = maze.size();
        cSize = maze[0].size();
               
        P cur(startRow, startCol);
        visited[startRow][startCol] = 1;
        
        queue<P> q;
        q.push(cur);
 
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int sz = moveRow.size();
            for(int k=0; k<sz; k++) {
                int nr = curR + moveRow[k];
                int nc = curC + moveCol[k];
                if(safe(nr, nc) && maze[nr][nc] == '.' && !visited[nr][nc]) {
                    P tmp(nr, nc);
                    q.push(tmp);
                    visited[nr][nc] = visited[curR][curC]+1;
                }
            }
        }
        int ans = 0;
        for(int r=0; r<rSize; r++) {
            for(int c=0; c<cSize; c++) {
                if(maze[r][c] == '.' && visited[r][c] == 0) return -1;
                if(maze[r][c] == '.' && ans < visited[r][c]) {
                    ans = visited[r][c];
                }
            }
        }
        return ans-1;
    }
};
 
cs


>> 방문할 수 있는 모든 곳을 탐색. 방문을 못한 곳이 있으면 -1; 모두 방문했다면, 방문한 곳중 가장 먼 곳이 정답.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

티스토리툴바