반응형

문제 링크:https://www.acmicpc.net/problem/7576

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

 

<문제 풀이> BFS

이문제는 기본적인 bfs를 사용해서 최단거리를 구하면 됩니다.

 

그런데 익은 토마토가 여러 개이면 모든 익은 토마토에 대해서 동시에 출발을 해야 됩니다.

 

시작점을 여러개 두고 bfs를 동시에 진행하는 방법은

시작점을 모두 queue에 넣고 시작하면 됩니다. (그러면 번갈아가면서 push, pop을 하기 때문에 동시에 출발시킨 효과)

 

 

<C++ 소스 코드>

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
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
using namespace std;
 
#define X first
#define Y second
 
int box[1000][1000];
int visited[1000][1000];
int dx[4= {1 ,0-10};
int dy[4= {0-101};
int n, m;
 
 
void bfs() {
    queue<pair<intint> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (box[i][j] == 1) {
                Q.push({ i,j });
            }
            if (box[i][j] == 0) {
                visited[i][j] = -1;
            }
        }
    }
    
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny <0 || nx>=|| ny >=m) continue;
            if (visited[nx][ny] >= 0continue;
            Q.push({ nx, ny });
            visited[nx][ny] = visited[cur.X][cur.Y] + 1;
        }
    }
    
}
 
int cal_res() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visited[i][j] == -1return -1;
            res = max(res, visited[i][j]);
        }
    }
    return res;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> box[i][j];
        }
    }
    bfs();
   
    cout << cal_res();
    return 0;
}
 
cs
반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 10026번] 적록색약  (0) 2021.11.05
[백준 4179번] 불!  (0) 2021.11.04
[백준 4949번] 균형잡힌 세상  (0) 2021.11.01
[백준 5430번] AC  (0) 2021.10.28
[백준 2164번] 카드2  (0) 2021.10.27
반응형

문제 링크:https://www.acmicpc.net/problem/4949

 

4949번: 균형잡힌 세상

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마

www.acmicpc.net

 

<문제 풀이>

문자열에서 괄호를 제외한 다른 문자들은 무시하고 괄호만 확인해서 괄호들이 짝이 맞는지만 확인하면 됩니다.

 

[괄호 쌍 체크]

문자를 하나씩 확인해서

1. 여는 괄호 일 때 괄호를 스택에 push

2. 닫는 괄호 일때 스택의 top이 가리키는 괄호와 같으면 pop, 다르면 짝이 안 맞으므로 False

 

순회를 마쳤을 때 스택이 비어있으면 True, 비어있지 않으면 False

 

 

<C++ 소스 코드>

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 <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
 
 
bool solve(string& s) {
    stack<char> st;
    for (auto& c : s) {
        if (c == '(' || c == '[') st.push(c);
        else if (c == ')') {
            if (st.empty()) return false;
            if (st.top() != '('return false;
            st.pop();
        }
        else if (c == ']') {
            if (st.empty()) return false;
            if (st.top() != '['return false;
            st.pop();
        }
    }
    if (st.empty()) return true;
    else return false;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (true) {
        string s;
        getline(cin, s);
        if (s == "."return 0;
        if (solve(s)) cout << "yes\n";
        else cout << "no\n";
    }
    return 0;
}
 
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 4179번] 불!  (0) 2021.11.04
[백준 7576번] 토마토  (0) 2021.11.03
[백준 5430번] AC  (0) 2021.10.28
[백준 2164번] 카드2  (0) 2021.10.27
[백준 6198번] 옥상 정원 꾸미기  (0) 2021.10.21
반응형

문제 링크: https://www.acmicpc.net/problem/5430

 

5430번: AC

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

www.acmicpc.net

문제 풀이

 

[주의 1]

R 연산을 할 때마다 reverse 함수를 사용하면 시간 초과가 납니다.

왜냐하면

reverse 함수가 O(N)의 시간복잡도가 걸리니깐

전체 O(n * len(p))의 시간복잡도가 걸립니다.

p의 길이가 0 <= len(p) <= 100,000,

n의 범위가 0 <= n <= 100,000 이므로

만약에 p가 전부 R로 이루어져 있고, n = 100,000 이면

O(10^5 * 10^5) = O(10^10)이 되니깐 시간제한 1초 안에 해결할 수 없습니다.

[주의 2]

빈 배열에서 R연산을 해도 error가 아니다

 

 

reverse 함수를 사용하지 않고 R연산을 구현하는 방법은

deque를 사용하면 됩니다.

 

D연산을 배열의 앞과 뒤에서 할 수 있는데

처음엔 앞에서 시작해서 R연산을 할 때마다 앞, 뒤를 바꿔주면 됩니다.

 

<c++ 소스 코드> deque 덱, 자료구조

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
#include <iostream>
#include <deque>
#include <string>
#include <vector>
using namespace std;
 
//false return is error
bool solve(deque<int> &x, string& p, bool& flag) {
    flag = true//true = queue, false = stack
    for (auto& c : p) {
        if (c == 'R') flag = !flag;
        else if (c == 'D' && x.empty()) {
            return false;
        }
        else if (c == 'D' && flag) { //queue
            x.pop_front();
        }
        else if (c == 'D' && !flag) { // stack
            x.pop_back();
        }
    }
    return true;
}
void print_x(bool flag, deque<int> &x) {
    if (flag) { //queue
        cout << '[';
        while (!x.empty()) {
            cout << x.front(); x.pop_front();
            if(!x.empty())cout << ',';
        }
        cout << ']';
    }
    else { //stack
        cout << '[';
        while (!x.empty()) {
            cout << x.back(); x.pop_back();
            if (!x.empty())cout << ',';
        }
        cout << ']';
    }
    cout << '\n';
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int test_case; cin >> test_case;
    while (test_case--) {
        string p; cin >> p;
        int n; cin >> n;
        string s; cin >> s;
        deque<int> x;
        string num;
        s.erase(s.begin());
        for (auto& c : s) {
            if (c == ',' || c == ']' && num.size()) {
                x.push_back(stoi(num));
                num.clear();
            }
            else if (c >= '0' && c <= '9') {
                num.push_back(c);
            }
        }
        bool flag = true;
        if (solve(x, p, flag)) {
            if (flag) print_x(true, x);
            else print_x(false, x);
        }
        else {
            cout << "error\n";
        }
 
    }
    return 0;
}
 
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 7576번] 토마토  (0) 2021.11.03
[백준 4949번] 균형잡힌 세상  (0) 2021.11.01
[백준 2164번] 카드2  (0) 2021.10.27
[백준 6198번] 옥상 정원 꾸미기  (0) 2021.10.21
[백준 2493번] 탑  (2) 2021.10.15
반응형

문제 링크: https://www.acmicpc.net/problem/2164

 

2164번: 카드2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

문제 풀이

숫자 카드를 위 그림과 같이 큐에 넣고

큐의 크기가 1이 될 때까지 다음을 반복하면 됩니다.

first 원소를 pop
그 다음 first원소를 push + pop

 

<c++ 소스 코드> 큐, 자료구조

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 <iostream>
#include <queue>
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    queue<int> q;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) q.push(i);
 
    while (q.size() != 1) {
        q.pop(); //카드 버리고
 
        q.push(q.front()); // 뒤로 옮기기
        q.pop();
    }
    cout << q.front();
 
 
    return 0;
}
 
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 4949번] 균형잡힌 세상  (0) 2021.11.01
[백준 5430번] AC  (0) 2021.10.28
[백준 6198번] 옥상 정원 꾸미기  (0) 2021.10.21
[백준 2493번] 탑  (2) 2021.10.15
[백준 3273번] 두 수의 합  (0) 2021.10.06
반응형

문제 링크: https://www.acmicpc.net/problem/6198

 

6198번: 옥상 정원 꾸미기

문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으

www.acmicpc.net

 

[문제 풀이] 스택, 자료구조

 

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

먼저 크기가 N인 배열을 준비합니다.

arr[i]는 i번째 빌딩을 바라보는 관리자들의 수가 됩니다.

->arr[1] == 0 (어떤 빌딩도 바라볼 수 없음)

   arr[2] == 1 (1번 빌딩이 바라보고 있음)

   arr[3] == 1 (1번 빌딩이 바라보고 있음)

   arr[4] == 2 (1번, 3번 빌딩이 바라보고 있음)

   arr[5] == 0 (어떤 빌딩도 바라볼 수 없음)
   arr[6] == 1 (5번 빌딩이 바라보고 있음)

 

그리고 빌딩을 저장할 수 있는 스택을 하나 준비합니다

이때 스택엔 i번째 빌딩을 볼 수 있는 빌딩을 저장합니다. 

-> 1번 빌딩 stack = {0}

    2번 빌딩 stack = {0, 1}

    3번 빌딩 stack = {0, 1}    

    4번 빌딩 stack = {0, 1, 3}

    5번 빌딩 stack = {0}

    6번 빌딩 stack = {0, 5}

 

스택의 size -1은 i번째 빌딩을 바라볼 수 있는 관리자의 수가 됩니다.

 

1 ~ N 빌딩을 순회하면서

i 번째 i +1 번째 빌딩을 체크해서

 

if(i + 1 번째 i번쨰 빌딩보다 작으면)

->i번째 빌딩이 i+1번째 빌딩을 볼 수 있으니깐 i번쨰 빌딩을 스택에 추가합니다.

else if(i +1번째 빌딩이 i번쨰 빌딩보다 크거나 같으면)

->i+1번째 빌딩을 볼 수 없는 관리자들을 스택에서 제거합니다.

  ex) 5번 빌딩일 때 1번, 3번을 제거함)

 

 

 

<c++ 소스 코드> 

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 <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <numeric>
using namespace std;
 
int height[80001];
int sum[80001];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> height[i];
    }
    
    stack<int> manager; //스택의 관리자들은 i번째 빌딩을 볼 수 있다
    manager.push(0);
    for (int i = 1; i <= n; i++) {
        sum[i] = manager.size() - 1;//i번째 빌딩을 바라보는 관리자들의 수
        if (height[i + 1< height[i]) {//다음 빌딩이 더 작으면 i번째 빌딩이 다음 빌딩을 볼 수 있음
            manager.push(i); //i번째 빌딩을 i+1번째 빌딩을 볼 수 있는 관리자로 추가
        }
        else if (height[i + 1>= height[i] && manager.top()) { // 다음 빌딩이 더 크거나 같으면
            //다음 빌딩을 볼 수 없는 관리자들을 스택에서 제거
            while (height[manager.top()] <= height[i + 1&& manager.top()) manager.pop();
 
        }
    }
    long long res = 0;
    cout << accumulate(sum + 1, sum + n + 1, res);
    return 0;
}
 
cs
반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 5430번] AC  (0) 2021.10.28
[백준 2164번] 카드2  (0) 2021.10.27
[백준 2493번] 탑  (2) 2021.10.15
[백준 3273번] 두 수의 합  (0) 2021.10.06
[백준 10871번] X보다 작은 수  (0) 2021.10.02
반응형

문제 링크: https://www.acmicpc.net/problem/2493

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

문제 풀이

첫 번째 탑에서 시작해서 탑을 두 개씩(i, i+1) 이용하면 스택으로 문제를 해결할 수 있습니다. 

 

 

스택을 하나 준비해서 탑의 번호를 저장합니다

이때 스택의 top()은 i번쨰 탑이 레이저를 발사했을 때 수신받을 수 있는 가장 가까운 탑입니다.

 

수신받을 수 있는 탑이 없는 경우는 높이가 0인 0번째 탑이 존재한다고 생각하고 0번째 탑이 수신하도록 하면 됩니다.

 

이제 i번째와 i+1번째 탑 두 개를 이용해서 다음과 같은 알고리즘을 만들 수 있습니다.

1. 만약 i+1번째 탑이 i번째 탑보다 크다면

-> 스택의 top()이 i+1번쨰 탑보다 클 때까지 스택을 pop()합니다

  ->스택의 top()이 i+1 번째 탑보다 작으면 top()이 i+1번째 탑의 레이저를 수신하지 못합니다.

  (단 스택의 top() > 0 이상일 때입니다. 왜냐하면 아무것도 수신받는 레이저가 없을 땐 0번째 탑이 수신하도록 했습니다.

2. 그렇지 않으면 만약 i+1번째 탑이 i번째 탑보다 작으면

-> i번째 탑을 스택에 push()합니다.

  -> i번쨰 탑이 i+1번째의 탑의 레이저를 수신하게 만듭니다.

 

3. 그렇지 않으면 만약 i+1번째 탑이 i번쨰 탑보다 작으면

-> 스택을 pop()하고 i번쨰 탑을 스택에 push()합니다.

  -> i+1번째 레이저를 가장 가까운 탑이 수신하도록 합니다.

 

문제의 입력을 예로 설명하면

i = 1일 때

0번째 탑이 1번째 탑의 레이저를 수신합니다.

 

i = 2일 때

1번째 탑이 2번째 탑의 레이저를 수신하고 2번째 탑을 스택에 push()합니다.

 

i = 3일 때

2번째 탑이 3번째 탑의 레이저를 수신합니다.

 

i = 4일 때

2번째 탑이 4번째 탑의 레이저를 수신하고 4번째 탑을 스택에 push()합니다.

 

i = n일 때

4번째 탑이 5번째 탑의 레이저를 수신합니다.

 

 

 

<C++ 소스 코드> 스택, 자료구조

 

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 <vector>
#include <stack>
using namespace std;
 
int height[500001];
int res[500001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; cin >> n;
    stack<int> big;
    for (int i = 1; i <= n; i++) {
        cin >> height[i];
    }
 
    big.push(0);
 
    for (int i = 1; i < n; i++) {
        res[i] = big.top(); //스택에 top()은 i번째 레이저를 수신
        if (height[i + 1> height[i] && big.top()) {
            while (height[big.top()] < height[i + 1&& big.top()) {//스택의 top()이 i+1번째 탑보다 커야 하므로 작은 top()은 제거
                big.pop();
            }
        }
        else if (height[i + 1< height[i]) {
            big.push(i);//i번째 탑을 i+1번째 탑이 만나는 가장 가까우면서 큰 탑으로 만듬
        }
        else if (height[i + 1== height[i]) { // 연속된 크기의 탑일 경우엔 가장 가까운 탑이 수신하도록 함
            big.pop();
            big.push(i);
        }
    }
    res[n] = big.top();
    for (int i = 1; i <= n; i++) {
        cout << res[i] << " ";
    }
 
 
    return 0;
}
 
cs
반응형
반응형

문제 링크:https://www.acmicpc.net/problem/3273

 

3273번: 두 수의 합

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는

www.acmicpc.net

 

<문제 풀이>

시간제한이 1초이고 N < 10^6 이므로 O(N^2) 풀이는 시간 초과입니다.

 

수열을 하나씩 꺼내보면서, 꺼낸 수와 합이 X가 되도록 하는 수열 내의 다른 어떤 수가 존재하는지 확인할 수 있으면 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.

 

수열에서 하나씩 꺼내서 X에서 뺀 뒤 그 수가 수열 내에 존재하는지 확인하면 됩니다.

-> a1 + a2 = X

    a2 = X - a1

 

문제 입력을 예로 들면

9

5 12 7 10 9 1 2 3 11

13

 

1) 5 -> 13(X) - 5 = 8 

2) 12 -> 13(X) - 12 = 1

3) 7 -> 13(X) - 7 = 6 

4) 10 -> 13(X) - 10 = 3

5) 9 -> 13(X) - 9  = 4

6) 1 -> 13(X) - 1  = 12

7) 2 -> 13(X) - 2  = 11

8) 3 -> 13(X) - 3  = 10

9) 11 -> 13(X) - 11  = 2

 

꺼낸 수가 등장한 수인지를 체크하는 배열을 만들고 입력받은 데이터를 순회하면서 

1. X - data가 이전에 등장했다면 카운트. 9) 11 -> 13(X) - 11 = 2  : 2는 7)에서 등장한 수로 체크함

2. 꺼낸 수는 등장한 수 배열에 체크해줍니다.  

 

X - data가 음수가 나올 수도 있음(배열 런타임 에러)

 

<C++ 소스 코드>

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
#include <iostream>
#include <vector>
using namespace std;
 
bool flag[2000001];
 
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    vector<int> v;
    int n; cin>>n;
    for(int i=0; i<n;i++){
        int data; cin>>data;
        v.push_back(data);
    }
    int x; cin>>x;
    
    int cnt = 0;
 
    for(auto &data : v){
        if(x >= data && flag[x - data]) cnt++;
        flag[data] = true;
    }
    cout<<cnt;
    
    return 0;
}
cs
반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 6198번] 옥상 정원 꾸미기  (0) 2021.10.21
[백준 2493번] 탑  (2) 2021.10.15
[백준 10871번] X보다 작은 수  (0) 2021.10.02
[백준 1197번] 최소 스패닝 트리  (0) 2020.07.26
[백준 4256번] 트리  (0) 2020.07.18
반응형

문제 링크:https://www.acmicpc.net/problem/10871

 

10871번: X보다 작은 수

첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000) 둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

<문제 풀이>

입력받은 수를 X보다 작으면 출력하면 되는 문제입니다.

 

<C++ 소스 코드> 수학, 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, X;
    cin>>N>>X;
    for(int i=0; i<N; i++){
        int data; cin>>data;
        if(data < X) cout<<data<<" ";
    }
 
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2493번] 탑  (2) 2021.10.15
[백준 3273번] 두 수의 합  (0) 2021.10.06
[백준 1197번] 최소 스패닝 트리  (0) 2020.07.26
[백준 4256번] 트리  (0) 2020.07.18
[백준 10974번] 모든 순열  (0) 2020.07.05

+ Recent posts