https://www.acmicpc.net/problem/10828


그리 어려운 문제는 아니고 라이브러리 쓰는 방법을 블로그에 저장용.


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 <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
int main() {
    int N;
    stack<int> stack1;
    cin >> N;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        if (str == "push") {
            int a;
            cin >> a;
            stack1.push(a);
        }
        else if (str == "top") {
            if (stack1.empty() == 1)
                cout << "-1" << endl;
            else
                cout << stack1.top() << endl;
        }
        else if (str == "size")
            cout << stack1.size() << endl;
        else if (str == "empty")
            cout << stack1.empty() << endl;
        else if (str == "pop") {
            if (stack1.empty() == 1) {
                cout << "-1" << endl;
            }
            else {
                cout << stack1.top() << endl;
                stack1.pop();
            }
        }
    }
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06

https://www.acmicpc.net/problem/10953


%*c 를 처음봐서 참고용으로 올리게 되었다.

%*c는 입력은 받지만 저장은 안한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
 
using namespace std;
 
int main() {
    int N, a, b;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%1d %*c %1d", &a, &b);
        printf("%d\n", a + b);
    }
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20

https://www.acmicpc.net/problem/11722


이 문제는 11053번(https://www.acmicpc.net/problem/11053)에서 부등호만 바꾸면 된다.


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 <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
int ary[1001];        //array
int lis[1001];        //LIS values
 
int main() {
    int N, input, output;
 
    scanf("%d", &N);
 
    for (int k = 0; k < N; k++) {
        scanf("%d", &input);
        ary[k] = input;
    }
 
    for (int k = 0; k < N; k++) {
        lis[k] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (ary[i] < ary[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
 
    output = lis[0];
    for (int k = 0; k < N; k++) {
        if (output < lis[k]) {
            output = lis[k];
        }
    }
 
    printf("%d", output);
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20

https://www.acmicpc.net/problem/11053


Longest Increasing Subsequence(이하 LIS)를 이용하여 푸는 문제이다.

일단 최대한 간단하고 직관적으로 풀었다.

ary[]에는 값을 전부다 받아왔고

lis[]는 배열을 줄을 세워 줄의 길이를 넣었다. 초기값은 1로 해야한다.

output는 lis[0]로 초기화한다.



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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
int ary[1001];        //array
int lis[1001];        //LIS values
 
int main() {
    int N, input, output;
    int sum = 0;
 
    scanf("%d", &N);
 
    for (int k = 0; k < N; k++) {
        scanf("%d", &input);
        ary[k] = input;
    }
 
    for (int k = 0; k < N; k++) 
        lis[k] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (ary[i] > ary[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
 
    output = lis[0];
    for (int k = 0; k < N; k++) {
        if (output < lis[k]) {
            output = lis[k];
        }
    }
 
    printf("%d", output);
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20

이 문제는 동적계획법으로 푸는 문제로

시간초과는  memoization으로 해결하면 되고

딱히 큰 어려움은 없는 문제이다.



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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[36];
 
unsigned long long t(int n) {
    if (n == 0)
        return result[n] = 1;
    if (result[n] > 0)
        return result[n];
    else {
        for (int i = 0; i < n + 1; i++)
            result[n] += t(i)*t(n - i - 1);
        return result[n];
    }
}
 
int main() {
    int input;
    cin >> input;
    cout << t(input);
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13

이 문제는 동적계획법으로

첫 번째 타일이 세로로 있을 때(n-1)랑 2개의 타일이 가로로 되어있을 때(n-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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[1001];
 
unsigned long long fibonacci(int n) {
    if (n == 1)
        return result[n] = 1;
    if (n == 2)
        return result[n] = 2;
    if (result[n] > 0)
        return result[n];
    else
        return result[n] = (fibonacci(n - 1) + fibonacci(n - 2))%10007;
}
 
int main() {
    int input;
    cin >> input;
    cout << fibonacci(input);
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17

이 문제는 간단한 동적 계획법을 이용하여 풀 수 있다.

어떤 동적계획법이든 마찬가지지만 시간초과가 제일 문제이다.

일단 이 문제는 확률과통계에서 나오는 조합을 이용하여 풀 수 있다.

eCr = e-1Cw-1 + e-1Cw (e = east, w = west) 공식을 이용하여 풀면 된다.

eC0 = 1일 때와 e==w일 때를 출구조건으로 하면 간단하게 풀 수 있다.

(memoization을 이용하지 않으면 시간초과가 뜨므로 주의한다.)



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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
unsigned long long result[30][30];
 
unsigned long long combination(int east, int west) {
    if (east == west || west == 0)
        return result[east][west] = 1;
    if (result[east][west] > 0)
        return result[east][west];
    else
        return result[east][west] = combination(east - 1, west - 1) + combination(east - 1, west);
}
 
int main() {
    int N;
    int west, east;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> west >> east;
        cout << combination(east, west) << endl;
    }
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03

https://www.acmicpc.net/problem/1730


비트마스크를 풀려고 이 문제를 건드렸으나

비트마스크를 이용해서 푸는 방법을 몰라서 배열로 케이스를 나눠서 풀었다.

예외케이스가 좀 있어서 해결하는데 시간이 좀 걸렸다.

 case문으로 하고 싶었으나 할줄모르겠다...ㅎㅎ



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
#include <iostream>
#include <cstdio>
#include <string>
#pragma warning(disable : 4996)
 
using namespace std;
int ary[101][101];
int main() {
    int N;
    scanf("%d", &N);
    string input;
    cin >> input;
    int a = 0, b = 0;                // a = row , b = column
                                    // 0 means ., 1 means |, 2 means -, 3 means +
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == 'D') {            // input = D
            if (a + 1 == N) continue;
            else {
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
 
                a += 1;
 
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
            }
        }
        else if (input[i] == 'U') {
            if (a - 1 < 0) continue;
            else {
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
 
                a -= 1;
 
                if (ary[a][b] == 2)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 1;
            }
        }
        else if (input[i] == 'R') {
            if (b + 1 == N) continue;
            else {
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
 
                b += 1;
 
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
            }
        }
        else if (input[i] == 'L') {
            if (b - 1 < 0) continue;
            else {
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
 
                b -= 1;
                
                if (ary[a][b] == 1)
                    ary[a][b] = 3;
                else if (ary[a][b] == 0)
                    ary[a][b] = 2;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int output = ary[i][j];
            // 0 means ., 1 means |, 2 means -, 3 means +
            if (output == 0)
                printf("%c", 46);
            else if (output == 1)
                printf("%c", 124);
            else if (output == 2)
                printf("%c", 45);
            else if (output == 3)
                printf("%c", 43);
        }
        cout << endl;
    }
    
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03
[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03

https://www.acmicpc.net/problem/11657


이 문제는 최단경로 문제이다. 보통은 다익스트라(Dijstra) 알고리즘을 쓰지만 이 문제의 경우에는 경로 가중치가 음수인 경우가 있으므로


벨만-포드(Bellman-Ford) 알고리즘 또는 플로이드-워셜(Floyd-Warshall) 알고리즘을 이용해야 한다.


두 개의 차이점은 구현 면에서 보면 플로이드-워셜은 이해하기는 힘드나 구현은 간단하다.


벨만-포드는 이해하기도 쉽고 구현도 그렇게 어렵지는 않지만 플로이드-워셜에 비하면 좀 더 복잡하다.


다음 시간 복잡도 면에서 보면, 벨만-포드는 O(E*V)이고 플로이드-워셜은 O(V^3)이다.


주어진 문제(E = 6000, V = 500)에 대입하면,


벨만-포드는 O(E*V) = 3000000정도이고 플로이드-워셜은 O(V^3) = 125000000정도로 시간 제한이 1초인것을 감안하면


플로이드-워셜은 시간 초과가 날 가능성이 높다.


그러므로 벨만-포드 알고리즘을 이용할 것이다.


https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

(위키피디아 Bellman-Ford Algorithm)

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

(위키백과 벨만-포드 알고리즘)


이 문제 난이도 면에서 보면 어렵지는 않으나


벨만-포드 알고리즘을 실제로 구현해보는 문제로 괜찮은 문제이다.


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 <cstdio>
#pragma warning (disable : 4996)
struct Edge {
    int to;
    int from;
    int weight;
};
Edge edge[6001];
int dist[501];
int main() {
    int N, M;
 
    bool NegativeCycleExist = false;    // 시작점에서 도달 가능한 타임머신으로 되어있는 사이클이 존재해 가장 빠른 시간이 존재하지 않는 경우
 
    scanf("%d %d", &N, &M);
    for (int i = 0; i <= N; i++)
        dist[i] = 0x07ffffff;            // 무한대 값이라 가정
    for (int i = 0; i < M; i++)
        scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].weight);
    dist[1] = 0;
    for (int i = 0; i < N - 1; i++) {    // N-1번 실행
        for (int j = 0; j < M; j++) {
            if (dist[edge[j].to] > dist[edge[j].from] + edge[j].weight) {
                dist[edge[j].to] = dist[edge[j].from] + edge[j].weight;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        if (dist[edge[i].to] > dist[edge[i].from] + edge[i].weight) {
            NegativeCycleExist = true;
        }
    }
    if (NegativeCycleExist) {
        printf("-1\n");
        return 0;
    }
    for (int i = 2; i <= N; i++) {
        if (dist[i] == 0x07ffffff)
            printf("-1\n");
        else
            printf("%d\n", dist[i]);
    }
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20
[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[9935번] String Explosion 문자열 폭발 - Stack[C++] ☆  (0) 2017.01.03
[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03
[5397번] Keylogger 키로거 - Stack[C++]  (0) 2017.01.02
https://www.acmicpc.net/problem/9935

아이디어는 스택에 문자열을 하나씩 받아오면서 문자열의 끝자리가 폭발 문자열의 끝자리와 같으면

폭발 가능성을 검사한다.

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 <iostream>
#include <string>
#include <stdio.h>
 
#pragma warning (disable : 4996)
using namespace std;
 
int main() {
    string str, bomb;
    char stack1[1000001];
    cin >> str >> bomb;
 
    int index = 0;
    int strlen = str.length();
    int bomblen = bomb.length();
 
    for(int i = 0; i < strlen; i++){
        stack1[index++] = str[i];
        if (str[i] == bomb[bomblen - 1]) { //compare
            bool check = false;
            for (int j = bomblen - 1, k = index - 1; j >= 0; j--, k--)
                if (bomb[j] != stack1[k]) {
                    check = true;
                    break;
                }
            if (!check) index -= bomblen;
        }
    }
 
    if (index != 0)
        for (int i = 0; i < index; i++)
            printf("%c", stack1[i]);
    else
        printf("FRULA");
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1730번] 판화 - 비트마스크, 배열[C++]  (0) 2017.02.13
[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆  (0) 2017.01.17
[1158번] Josephus Problem 조세퍼스 - Deque [C++] ☆  (0) 2017.01.03
[5397번] Keylogger 키로거 - Stack[C++]  (0) 2017.01.02
[10817번] Three Interger 세 수 - if condition[C++]  (0) 2017.01.02

+ Recent posts

티스토리툴바