How We Coding

[POJ/2431] Expedition

PS/etc.2018. 6. 27. 10:38

[2431] Expedition : http://poj.org/problem?id=2431


### Priority Queue ###


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct Exp { int dist, fuel; };
 
int n, L, P;
 
bool cmp(Exp a, Exp b)
{
    return L-a.dist < L-b.dist;
}
 
int main()
{
    scanf("%d", &n);
 
    vector<Exp> v;
    for(int i=0; i<n; i++) {
        int d, f;
        scanf("%d%d", &d, &f);
        v.push_back((Exp){d, f});
    }
 
    scanf("%d%d", &L, &P);
    sort(v.begin(), v.end(), cmp);
 
    int ans=0;
    int curL = P;
    priority_queue<int> pq;
 
    v.push_back((Exp){0, 0});
 
    for(int i=0; i<=n; i++) {
        while(L-v[i].dist > curL && !pq.empty()) {
            curL += pq.top(); pq.pop();
            ans++;
        }
        if(curL < L-v[i].dist) break;
        pq.push(v[i].fuel);
    }
 
    if(curL < L) ans = -1;
    printf("%d\n", ans);
    return 0;
}
 
cs

>> 34 번 라인이 없으면 틀렸다고 뜬다.

'PS > etc.' 카테고리의 다른 글

[POJ/1182] 먹이 사슬  (0) 2018.07.25
[카카오 코드 / 예선] 카카오프렌즈 컬러링북  (0) 2018.05.04
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

Week 1 - DP1

Tutoring/PS2018. 6. 26. 15:43

<180625>


### DP Basic ###


1) [11051] 이항계수2 : http://boj.kr/11051


combi(n, r) : nCr 을 구하는 함수. nCr = n-1Cr + n-1Cr-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
#include <stdio.h>
 
const int MOD=10007;
 
int d[1001][1001];
 
int combi(int n, int r)
{
    int *ret = &d[n][r];
    if(r == 0 || r == n) return 1;
    if(*ret != -1) return *ret;
 
    return *ret = (combi(n-1, r-1)+combi(n-1, r))%MOD;
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            d[i][j] = -1;
    printf("%d\n", combi(n, k));
    return 0;
}
cs



2) [11055] 가장 큰 증가하는 부분 수열 : http://boj.kr/11055


d[i] : i ~ (n-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
#include <stdio.h>
 
int n;
int a[1001], d[1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lis(int s)
{
    int *ret = &d[s];
    if(s == n-1) return a[s];
    if(*ret) return *ret;
 
    *ret = a[s];
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i])
            *ret = max(*ret, a[s]+lis(i));
    }
    return *ret;
}
 
int main()
{
    int ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<n; i++)
        ans = max(ans, lis(i));
    printf("%d\n", ans); 
    return 0;
}
 
cs



3) [11048] 이동하기 : http://boj.kr/11048


d[i][j] : (i,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
#include <stdio.h>
 
int g[1001][1001];
int d[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int move(int r, int c)
{
    int *ret = &d[r][c];
    if(r <= 0 || c <= 0) return 0;
    if(*ret != -1) return *ret;
    
    *ret = move(r-1, c)+g[r][c];
    return *ret = max(*ret, move(r, c-1)+g[r][c]);
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = -1;
        }
    }
 
    printf("%d\n", move(n, m));
    return 0;
}
 
cs




4) [11066] 파일합치기 : http://boj.kr/11066


d[i][j] : i~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
40
41
42
43
44
45
#include <stdio.h>
 
int n, a[501];
int d[501][501];
int pSum[501];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int file(int s, int e)
{
    int *ret = &d[s][e];
    if(s == e) return 0;
    if(*ret != -1) return *ret;
 
    *ret = 0x7fffffff;
    for(int i=s; i<e; i++) 
        *ret = min(*ret, file(s, i)+file(i+1, e)); 
    return *ret = *ret + (pSum[e]-pSum[s-1]);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            pSum[i] = 0;
        for(int i=1; i<=n; i++) {
            scanf("%d", a+i);
            pSum[i] += (pSum[i-1]+a[i]);
 
            for(int j=1; j<=n; j++) 
                d[i][j] = -1;
        }
        printf("%d\n", file(1, n));
    }
 
    return 0;
}
 
cs


>> 누적합을 누적해나가야 한다.

>> pSum 을 초기화 안해서 뻣질 많이 함...ㅜㅜ



<180629>


1) [2410] 2의 멱수의 합 : http://boj.kr/2410



2) [2228] 구간 나누기 : http://boj.kr/2228


'Tutoring > PS' 카테고리의 다른 글

Week 7 - DFS+BFS  (0) 2018.04.07
Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07

[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

[3124] 최소 스패닝 트리

PS/SW Expert Academy2018. 6. 20. 21:11

### SW Expert Academy - D4 ###


[3124] 최소 스패닝 트리 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE


<소스코드>


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 <algorithm>
using namespace std;
 
struct P { int f, t, w; };
 
int p[100001];
 
bool cmp(P a, P b)
{
    return a.w < b.w;
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
bool Union(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int v, e;
        scanf("%d%d", &v, &e);
 
        for(int i=1; i<=v; i++)
            p[i] = i;
 
        vector<P> g;
        for(int i=0; i<e; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g.push_back((P){a, b, c});
        }
        
        sort(g.begin(), g.end(), cmp);
 
        long long ans=0LL;
        for(int i=0; i<e; i++) 
            if(Union(g[i].f, g[i].t)) 
                ans += g[i].w;
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}
 
cs


>> Union-Find 를 이용한 크루스칼 알고리즘 사용.

>> ans 값은 int 범위를 벗어남에 주의.


'PS > SW Expert Academy' 카테고리의 다른 글

[1486] 장훈이의 높은 선반  (0) 2018.06.20
[4408] 자기방으로 돌아가기  (0) 2018.06.10

[1486] 장훈이의 높은 선반

PS/SW Expert Academy2018. 6. 20. 21:09

### SW Expert Academy - D4 ###


[1486] 장훈이의 높은 선반 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=CODE



<소스코드>


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>
 
int h[21];
int n, b, ans;
 
void go(int idx, int sum)
{
    if(sum >= b) {
        if(ans > sum-b)
            ans = sum-b;
        return ;
    }
    if(idx == n) return ;
 
    go(idx+1, sum+h[idx]);
    go(idx+1, sum);
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        scanf("%d%d", &n, &b);
 
        ans = 0;
        for(int i=0; i<n; i++) {
            scanf("%d", h+i);
            ans += h[i];
        }
 
        go(0, 0);
        printf("#%d %d\n",  tc, ans);       
    }
    
    return 0;
}
 
cs


>> n 제한이 20이므로 2^20 = 1048576 이므로 모든 경우의 수를 다 확인해봐도 된다.

'PS > SW Expert Academy' 카테고리의 다른 글

[3124] 최소 스패닝 트리  (0) 2018.06.20
[4408] 자기방으로 돌아가기  (0) 2018.06.10

[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 은 역시 오바였다.

[4408] 자기방으로 돌아가기

PS/SW Expert Academy2018. 6. 10. 00:57

### SW Expert Academy - D4 ###


[4408] 자기방으로 돌아가기 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8


<소스코드>


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
#include <stdio.h>
 
int main()
{
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int n, ans=0;
        int room[201]={0};
        scanf("%d", &n);
 
        while(n--) {
            int a, b;
            scanf("%d%d", &a, &b);
            if(a > b) { int t=a; a=b; b=t; }
            
            if(a&1) a++;
            a/=2; 
 
            if(b&1) b++;
            b/=2; 
 
            for(int i=a; i<=b; i++)
                room[i]++;
        }
        
        for(int i=1; i<=200; i++)
            if(ans < room[i])
                ans = room[i];
        printf("#%d %d\n", tc, ans);
    }
     
    return 0;
}
 
cs


- 1, 2번방의 복도 번호를 1로, 3, 4번방의 복도 번호는 2로 ... 이런식으로 값을 설정

- 같은 복도 번호를 동시에 갈 수 없기 때문에, 특정 복도 번호를 최대로 지나쳐야하는 경우가 답이 된다.

'PS > SW Expert Academy' 카테고리의 다른 글

[3124] 최소 스패닝 트리  (0) 2018.06.20
[1486] 장훈이의 높은 선반  (0) 2018.06.20

Week 8-2 : Binary Search Tree (종강) (추가:180814)

Tutoring/18-1 DS2018. 6. 8. 00:49

<180608>


<소스코드>


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
#include <cstdio>
 
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data) : data(data), left(0), right(0) {}
};
 
class bst {
private:
    Node *root;
 
public:
    bst() : root(0) {}
    
    void insert(int data) {
 
        if(!root) {
            root = new Node(data); 
            return ;
        }
 
        Node *p = 0;
        Node *cur = root;
        while(cur) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
        if(p->data < data) p->right = new Node(data);
        else p->left = new Node(data);
    }
 
    Node* getRoot() { return root; }
 
    void display(Node *root) {
        if(!root) return ; 
        display(root->left);
        printf("%d\n", root->data);
        display(root->right);
    }
 
    void remove(int data) {
        Node *p = 0;
        Node *cur = root;
        while(cur && cur->data != data) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
 
        if(!cur) return ;
 
        if(cur->left == NULL && cur->right == NULL) {
            if(p == NULL) root = NULL;
            else {
                if(p->left == cur) p->left = NULL;
                else p->right = NULL;
            }
        }
        else if(cur->left == NULL || cur->right == NULL) {
            Node *child = cur->left ? cur->left : cur->right;
 
            if(p == NULL) root = child; 
            else {
                if(p->left == cur) p->left = child;
                else p->right = child;
            }
        }
        else {
            Node *sp = cur;
            Node *sc = cur->right;
 
            while(sc->left != NULL) {
                sp = sc;
                sc = sc->left;
            }
            
            if(sp->left == sc) {
                sp->left = sc->right;     
            }
            else
                sp->right = sc->right;
 
            cur->data = sc->data;
            cur = sc;
        }
 
        delete cur;
    }
};
 
int main()
{
    bst *t = new bst();
    t->insert(5);
    t->insert(1);
    t->insert(3);
    t->insert(2);
    t->insert(10);
    t->insert(9);
    t->insert(7);
    t->insert(8);
    t->display(t->getRoot()); puts("");
    t->remove(2);
    t->display(t->getRoot()); puts("");
    t->remove(1);
    t->display(t->getRoot()); puts("");
    t->remove(9);
    t->display(t->getRoot()); puts("");
    return 0;
}
 
cs



1) 데이터의 삽입 과정


18 7 26 31 3 12 9 27




2) 데이터 찾기.



3) 데이터의 삽입



4) 데이터의 삭제


4-1) 타겟 노드가 단말노드인 경우


4-2) 타겟 노드가 자식을 하나만 가지고 있는 경우


4-3) 타겟 노드가 두개의 자식을 가지고 있는 경우


>> 타겟의 오른쪽 자식이 왼쪽 서브트리를 가진경우 or not



5) 데이터 탐색의 시간 복잡도

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-1 : Binary Tree 2  (0) 2018.06.05
Week 7-2 : Tree, Binary Tree  (0) 2018.05.27
Week 7-1 : Stack, Queue by Linked List  (0) 2018.05.19
Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08

scp 를 이용한 파일 복사

on Mac2018. 6. 8. 00:34

참고 : https://stackoverflow.com/questions/10364950/uploading-files-on-amazon-ec2


AWS 에서 ubuntu 서버를 사용중인 상황.


scp -i MyKeyFile.pem FileToUpload.pdf ubuntu@ec2-123-123-123-123.compute-1.amazonaws.com:FileToUpload.pdf

위와 같이 내 PC에 있는 파일을 ubuntu 서버에 복사할 수 있다.

그렇다면  ubuntu 서버에 있는 파일을 내 PC로 복사하고 싶다면..?

scp -i key.pem ubuntu@DNS:path (local)path 와 같이 하면 된다.


'on Mac' 카테고리의 다른 글

MongoDB 압축파일을 통한 설치  (0) 2018.10.16

Week 12 - 종강

Tutoring/18-1 C Lang2018. 6. 6. 14:55

<180606>


1) 문자열의 길이 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int main()
{
    char str[100];
    int len=0;
    int idx=0;
 
    scanf("%s", str);
 
    while(str[idx++] != 0) 
        len++;
 
    printf("%d\n", len);
    return 0;
}
cs


>> 문자열의 끝은 널문자이다..!!



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
#include <stdio.h>
 
int main()
{
    char str[100];
    int len=0;
    int idx=0;
 
    char str2[100];
 
    scanf("%s", str);
 
    while(str[idx++] != 0) 
        len++;
 
    printf("%d\n", len);
 
    idx = 0;
    for(int i=len-1; i>=0; i--)
        str2[idx++] = str[i];
    str2[idx] = 0;
 
    printf("%s\n", str2);
 
    return 0;
}
cs


>> 21 라인 : 널문자를 꼭 추가해줘야 한다. 널문자의 아스키코드 값은 0


3) 문자열 이어붙이기

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 <stdio.h>
 
int main()
{
    char str[100];
    char str2[100];
    char str3[100];
    int len=0, len2=0;
    int idx=0;
 
    scanf("%s", str);
    scanf("%s", str2);
 
    while(str[idx++] != 0) 
        len++;
 
    idx=0;
    while(str2[idx++] != 0) 
        len2++;
 
    idx=0;
    for(int i=0; i<len; i++)
        str3[i] = str[i];
 
    for(int i=0; i<len2; i++)
        str3[len++] = str2[i];
    str3[len] = 0;
 
    printf("%s\n", str3);
 
    return 0;
}
cs


>> 두 문자열의 길이를 구한 다음. 첫번째 문자의 널문자가 있는 위치부터 이어붙이면 된다.

>> 26 라인을 str3[len+i] 로 하고, 27라인을 str3[len+len2] = 0 으로 바꿔도 된다.



4)  배열과 포인터와의 관계

- 배열의 이름은 배열의 시작주소이며, 그 값을 바꿀 수 없는 상수형태의 포인터이다..!!

- 포인터(변수)는 변수이기 때문에 주소를 원할때마다 변경할 수 있다.


'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 11  (0) 2018.05.30
Week 10  (0) 2018.05.23
Week 09  (0) 2018.05.16
Week 08  (0) 2018.05.09
Week 07  (0) 2018.05.05

티스토리툴바