How We Coding

[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

[11985] 오렌지 출하

BOJ/DP2018. 6. 21. 01:18

### DP ###


[11985] 오렌지 출하 : http://boj.kr/11985


<소스코드>


d[i] : i번째 오랜지부터 포장했을 때, 비용의 최소값.


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
#include <stdio.h>
 
int a[20001];
long long d[21001];
int n, m, k;
 
long long min(long long a, long long b)
{
    return a < b ? a : b;
}
 
long long orange(int s, int e)
{
    long long *ret = &d[s];
    int size, big=0, small=0x7fffffff;
    long long box;
 
    if(s >= e) return 0;
    if(*ret != -1) return *ret;
 
    *ret = 0x7fffffffffffffff;
    size = m < e-s+1 ? m : e-s+1;
    for(int i=0; i<size; i++) {
        if(big < a[s+i]) big = a[s+i];
        if(small > a[s+i]) small = a[s+i];
        box = 1LL*(i+1)*(big-small) + k;
        *ret = min(*ret, box+orange(s+i+1, e));
    }
    return *ret;
}
 
int main()
{
    scanf("%d%d%d", &n, &m, &k);
 
    for(int i=0; i<n; i++) {
        scanf("%d", a+i);
        d[i] = -1;
    }
 
    printf("%lld\n", orange(0, n));
    return 0;
}
 
cs


>> 시간복잡도 : O(NM)

'BOJ > DP' 카테고리의 다른 글

[9177] 단어 섞기  (0) 2018.05.22
[2602] 돌다리 건너기  (0) 2018.05.17
[9252] LCS2  (0) 2018.04.22
[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18

[3063] 게시판

BOJ/Ref2018. 6. 13. 01:03

[3063] 게시판 : http://boj.kr/3063


### ACM-ICPC > Asia Regional - Daejeon Nationalwide Internet Competition 2002 A번 ###


참고 : https://fatc.club/2017/03/01/827


<소스코드>


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 max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    while(n--) {
        int ans, diff;
        int x1, y1, x2, y2;
        int x3, y3, x4, y4;
        int lbx, lby, rtx, rty;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        scanf("%d%d%d%d", &x3, &y3, &x4, &y4);
 
        ans = (x2-x1)*(y2-y1);
 
        rtx = min(x2, x4);
        rty = min(y2, y4);
        lbx = max(x1, x3);
        lby = max(y1, y3);
        
        diff = (rtx-lbx)*(rty-lby);
 
        printf("%d\n", ans-diff);
    }
    
    return 0;
}
 
cs


>> 경우의 수는 10가지. 그림을 그려보니 규칙이 보인다. 

>> 우상의 좌표들은 x2, x4 혹은 y2, y4 중 하나이고, 

     좌하의 좌표들은 x11, x3 혹은 y1, y3 중 하나이다.



- 메모리 초과 코드


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
#include <stdio.h>
 
int poster[10001][10001];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    while(n--) {
        int ans=0;
        int x1, y1, x2, y2;
        int x3, y3, x4, y4;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
 
        for(int x=x1; x<x2; x++)
            for(int y=y1; y<y2; y++)
                poster[x][y] = 1;
 
        scanf("%d%d%d%d", &x3, &y3, &x4, &y4);
        for(int x=x3; x<x4; x++)
            for(int y=y3; y<y4; y++)
                poster[x][y] = 0;
        
        for(int x=x1; x<x2; x++)
            for(int y=y1; y<y2; y++)
                if(poster[x][y] == 1)
                    ans++;
 
        printf("%d\n", ans);
    }
    
    return 0;
}
cs

>> 배열 10000 * 10000 은 역시 오바였다.

[1021] 회전하는 큐

BOJ/Simulation2018. 6. 4. 02:09

[1021] 회전하는 큐 : http://boj.kr/1021


### 시뮬레이션 ###


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 <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    vector<int> v;
    for(int i=1; i<=n; i++)
        v.push_back(i);
 
    int cur=0, ans=0;
    for(int i=0; i<m; i++) {
        int target, tmp = 0;
        int size = v.size();
        scanf("%d", &target);
 
        for(int j=0; j<size; j++) {
            if(v[cur] == target) {
                v.erase(v.begin()+cur);
                if(cur == size-1) cur = 0;
                break;
            }
            cur = (cur+1)%size;
            tmp++;
        }
        ans += min(tmp, size-tmp);
    }
    printf("%d\n", ans); 
}
cs


>> 24 라인이 중요한 것 같다. 중간에 있는 벡터를 삭제하면 자동으로 앞당겨져 cur 에 저장되어 있는 인덱스를 변경할 필요가 없지만, 

     맨 마지막 데이터가 삭제되면 cur 의 인덱스를 0으로 변경해야 한다.

[9177] 단어 섞기

BOJ/DP2018. 5. 22. 10:58

[9177] 단어 섞기 : http://boj.kr/9177


### DP ###


d[i][j] : 문자열 a의 i번째, 문자열 b의 j번째 인덱스에서 시작해서 단어를 섞어 세번째 문자열을 만들 수 있는지 여부.


<소스코드>


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
#include <stdio.h>
#include <string.h>
 
int aLen, bLen;
char a[201], b[201], c[401];
int d[201][201];
 
int word(int aIdx, int bIdx, int cIdx)
{
    int *ret = &d[aIdx][bIdx];
    if(aIdx == aLen && bIdx == bLen) return 1;
    if(*ret != -1) return *ret;
 
    *ret = 0;
    if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1);    
    if(*ret) return *ret;
    if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1);
    return *ret;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    
    for(int tc=1; tc<=n; tc++) {
        scanf("%s%s%s", a, b, c);
      
        printf("Data set %d: ", tc);
        
        aLen = strlen(a);
        bLen = strlen(b);
 
        memset(d, -1, sizeof(d));        
        word(0, 0, 0) ? puts("yes") : puts("no");
    }
    
    return 0;
}
cs

>> 처음에는 그리디방식으로 햇는데, 두번째 테케가 반례가 되어버렸다. 

>> 유형이 DP 라고 되어 있어서 생각을 바꿔보았다...


<시간초과 코드>

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>
#include <string.h>
 
int aLen, bLen;
char a[201], b[201], c[401];
int d[201][201][401];
 
int word(int aIdx, int bIdx, int cIdx)
{
    int *ret = &d[aIdx][bIdx][cIdx];
    if(aIdx == aLen && bIdx == bLen) return 1;
    if(*ret != -1) return *ret;
 
    *ret = 0;
    if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1);    
    if(*ret) return *ret;
    if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1);
    return *ret;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    
    for(int tc=1; tc<=n; tc++) {
        int ai=0, bi=0, ci=0;
        scanf("%s%s%s", a, b, c);
      
        printf("Data set %d: ", tc);
        
        aLen = strlen(a);
        bLen = strlen(b);
 
        memset(d, -1, sizeof(d));        
        word(0, 0, 0) ? puts("yes") : puts("no");
    }
    
    return 0;
}
cs


>> AC 받은 코드와 차이가 있다면 cache 역할을 하는 배열을 3차원으로 잡은것. 생각해보면 2차원으로 충분하단 생각이 들었다. 

>> 그리고 시간초과 난 이유를 곰곰히 생각해보니, 매 테케마다(n*200*200*400에 해당하는) memset() 을 돌려 그런 것 같아. 

'BOJ > DP' 카테고리의 다른 글

[11985] 오렌지 출하  (0) 2018.06.21
[2602] 돌다리 건너기  (0) 2018.05.17
[9252] LCS2  (0) 2018.04.22
[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18

[4803] 트리

BOJ/Tree2018. 5. 21. 01:58

[4803] 트리 : http://boj.kr/4803


- 정점의 갯수를 세고, 간선의 갯수를 센다.

- 트리는 정점의 갯수-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
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
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
 
int n, m;
bool visited[501];
bool check[501];
 
int dfsV(vector<int> v[], int s)
{
    int ret = 1;
    visited[s] = 1;
    for(int i=0; i<v[s].size(); i++) {
        int next = v[s][i];
        if(!visited[next])
            ret += dfsV(v, next);
    }
    return ret;
}
 
int dfsE(vector<int> v[], int s)
{
    int ret=v[s].size();
    check[s] = 1;
    for(int i=0; i<v[s].size(); i++) {
        int next = v[s][i];
        if(!check[next])
            ret += dfsE(v, next);
    }
    return ret;
}
 
int main()
{
    int tc=0;
    while(1) {
        int ans=0;
 
        scanf("%d%d", &n, &m);
        if(!n && !m) break;
 
        vector<int> v[501];
        while(m--) {
            int a, b;
            scanf("%d%d", &a, &b);
            v[a].push_back(b);
            v[b].push_back(a);
        }
        
        memset(visited, 0, sizeof(visited));
        memset(check, 0, sizeof(check));
        for(int i=1; i<=n; i++) {
            if(!visited[i]) {
                int vertex = dfsV(v, i);
                int edge = dfsE(v, i);
                if(vertex-1 == edge/2)
                    ans++;
            }
        }
        tc++;
        printf("Case %d: ", tc);
        if(ans == 0) puts("No trees.");
        else if(ans == 1) puts("There is one tree.");
        else printf("A forest of %d trees.\n", ans);
    }
    return 0;
}
 
cs



<예전코드>

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>
using namespace std;
 
int v, e;
 
void dfs(vector<int> g[], bool visited[], int cur) 
{
    visited[cur] = true;
    v++;
 
    for(int i=0; i<g[cur].size(); i++) {
        int next = g[cur][i];
        e++;
        if(!visited[next]) {
            dfs(g, visited, next);
        }
    }
}
 
int main()
{
    int tc=1;
 
    while(1) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        if(!n && !m) break;
        
        vector<int> g[501];
        while(m--) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        int ans=0;
        bool visited[501]={0};
        for(int i=1; i<=n; i++) {
            if(!visited[i]) {
                v = e = 0;
                dfs(g, visited, i);
                
                if(v-1 == e/2) ans++;
            }
        }
        printf("Case %d: ", tc++);
        if(!ans) puts("No trees.");
        else ans > 1 ? printf("A forest of %d trees.\n", ans) : puts("There is one tree.");
    }
 
    return 0;
}
 
 
cs


>> dfs 를 한번만 호출해서 정점의 수와 간선의 수를 카운트했다.

'BOJ > Tree' 카테고리의 다른 글

[11725] 트리의 부모 찾기  (0) 2018.05.20
[1991] 트리 순회  (0) 2018.05.20

[11725] 트리의 부모 찾기

BOJ/Tree2018. 5. 20. 01:52

[11725] 트리의 부모 찾기 : http://boj.kr/11725


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;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    vector<int> v[100001];
    for(int i=1; i<n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    vector<int> p(n+1, 0);
    
    queue<int> q;
    q.push(1);
    p[1] = -1;
 
    while(!q.empty()) {
        int parent = q.front(); q.pop();
 
        for(int i=0; i<v[parent].size(); i++) {
            int child = v[parent][i];
            if(!p[child]) {
                q.push(child); 
                p[child] = parent;
            }
        }
    }
 
    for(int i=2; i<=n; i++)
        printf("%d\n", p[i]);
 
    return 0;
}
cs


>> 부모를 찾지 못했다면 큐에 넣고 부모 저장. BFS.

'BOJ > Tree' 카테고리의 다른 글

[4803] 트리  (0) 2018.05.21
[1991] 트리 순회  (0) 2018.05.20

[1991] 트리 순회

BOJ/Tree2018. 5. 20. 01:19

[1991] 트리 순회 : http://boj.kr/1991


<소스코드>


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
 
#include <stdio.h>
 
char tree[26][2];
 
void pre(int root)
{
    if(root == '.') return ;
    printf("%c", root+'A');
    pre(tree[root][0]);
    pre(tree[root][1]);
}
 
void in(int root)
{
    if(root == '.') return ;
    in(tree[root][0]);
    printf("%c", root+'A');
    in(tree[root][1]);
}
 
void post(int root)
{
    if(root == '.') return ;
    post(tree[root][0]);
    post(tree[root][1]);
    printf("%c", root+'A');
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    while(n--) {
        char p, lc, rc;
        scanf(" %c %c %c", &p, &lc, &rc);
        tree[p-'A'][0] = lc == '.' ? lc : lc-'A';
        tree[p-'A'][1] = rc == '.' ? rc : rc-'A';
    }
 
    pre(0); puts("");
    in(0); puts("");
    post(0); puts("");
    
    return 0;
}
cs

'BOJ > Tree' 카테고리의 다른 글

[4803] 트리  (0) 2018.05.21
[11725] 트리의 부모 찾기  (0) 2018.05.20

[2602] 돌다리 건너기

BOJ/DP2018. 5. 17. 00:25

[2602] 돌다리 건너기 : http://boj.kr/2602


- 난 3차원으로 풀었는데, 다른 사람들은 2차원으로 풀었다. 


d[bidx][ad][sidx] : 상태가 ad(0은 천사차례, 1은 악마차례) 일때, 

       bidx번째 돌다리에서, sidx 번째 문자부터 시작하는 문자열에 적힌 순서대로 다리를 건널 수 있는 방법의 수


<소스코드>

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
#include <stdio.h>
 
char str[21];
char ang[101], dev[101];
int d[101][2][21];
 
int bridge(int bidx, int ad, int sidx)
{
    int *ret = &d[bidx][ad][sidx];
    if(!str[sidx]) return 1;
    if(ad == 0 && !ang[bidx]) return 0;
    if(ad == 1 && !dev[bidx]) return 0;
    
    if(*ret) return *ret;
 
    if(ad == 0) {
        if(ang[bidx] == str[sidx])
            *ret = bridge(bidx+1, !ad, sidx+1);
        *ret += bridge(bidx+1, ad, sidx);
    }
    else {
        if(dev[bidx] == str[sidx])
            *ret = bridge(bidx+1, !ad, sidx+1);
        *ret += bridge(bidx+1, ad, sidx);
    }
    return *ret;
}
 
int main()
{   
    scanf("%s%s%s", str, ang, dev);
    printf("%d\n", bridge(0, 0, 0)+bridge(0, 1, 0));
    return 0;
}
cs

>> 천사다리를 먼저 택한 경우 + 악마다리를 먼저 택한 경우

'BOJ > DP' 카테고리의 다른 글

[11985] 오렌지 출하  (0) 2018.06.21
[9177] 단어 섞기  (0) 2018.05.22
[9252] LCS2  (0) 2018.04.22
[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18

[5883] 아이폰 9S

BOJ/etc.2018. 5. 14. 21:06

[5883] 아이폰 9S : http://boj.kr/5883


- 입력으로 들어오는 수를 체크해 놓고, 큐에 저장.

- 큐에서 꺼낸 다음, 이미 사용한 적이 있으면 continue

- 큐에서 꺼낸 값을 제외하고, 가장 길게 연속하는 수를 세가며 갱신.


<소스코드>


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 a[1001];
int check[1000001];
int q[1001], f, r;
 
int main()
{
    int n, ans=1;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++) {
        scanf("%d", a+i);
        check[a[i]] = 1;
        q[r++] = a[i];
    }
 
    while(f != r) {
        int cnt = 1;
        int cur = a[0];
        int exp = q[f++];
 
        if(!check[exp]) continue;
 
        check[exp] = 0;
    
        for(int i=1; i<n; i++) {
            if(a[i] == exp) continue;
            if(cur == a[i]) cnt++;
            else {
                if(ans < cnt) ans = cnt;
                cur = a[i];
                cnt = 1;
            }
        }
        if(ans < cnt) ans = cnt;
    }
    printf("%d\n", ans);
    return 0;
}
cs



티스토리툴바