'알고리즘 문제풀이/백준' 카테고리의 글 목록 (3 Page)

www.acmicpc.net/problem/1120

1120번: 문자열

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의

www.acmicpc.net

<풀이>

1. 문자열 A와 B를 입력받는다.

2. 문자열 B와 길이가 같아질 때까지, 문자열 A의 앞이나 뒤에 문자를 추가한다.

3. A, B의 차이값 중 최소를 출력한다.

<해법>

1. 두 문자열의 차이가 최소가 되는 방법.

=> 문자열 B에서 문자열 A가 어디에 들어갈지를 결정합니다. 결정한 후, A의 앞이나 뒤에 추가되는 문자는 결국 B와 동일한 문자가 될 것입니다(차이값을 최소로 하기 위해). 따라서, B에서 A가 들어가는 공간과 그 때의 차이값만 계산해서 풀 수 있습니다.

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 <string>
 
using namespace std;
 
string A, B;
int answer;
 
int main() {
 
    //초기화
    A = "", B = "";
    answer = -1;
 
    //입력
    cin >> A >> B;
 
    for (int i = 0; i <= B.length() - A.length(); i++) {
        
        //B문자열에 하나씩 맞춰보기
        int diffCnt = 0;
        for (int j = 0; j < A.length(); j++) {
            if (A[j] != B[i + j]) {
                diffCnt++;
            }
        }
        
        //최소값 갱신
        if (answer == -1 || diffCnt < answer) {
            answer = diffCnt;
        }
    }
 
    //출력
    cout << answer;
 
    //종료
    return 0;
}
 

구현과 문자열에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 1018 - 체스판 다시 칠하기 (0)	2021.01.06
[C++] 백준 14502 - 연구소 (0)	2021.01.03
[C++] 백준 4949 - 균형잡힌 세상 (0)	2021.01.01
[C++] 백준 10773 - 제로 (0)	2021.01.01
[C++] 백준 1764 - 듣보잡 (0)	2021.01.01

www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

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

www.acmicpc.net

<풀이>

1. 문자열을 입력받는다.

2. 문자열이 균형잡혀 있는지 판단 후, 출력한다.

<해법>

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

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
bool isBalanced(string s) {
    //스택 자료구조 사용
    stack<char> st;
 
    //괄호 검사
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(' || s[i] == '[') {
            st.push(s[i]);
        }
        else if (s[i] == ')') {
            if (st.empty() || st.top() != '(') {
                return false;
            }
            else {
                st.pop();
            }
        }
        else if (s[i] == ']') {
            if (st.empty() || st.top() != '[') {
                return false;
            }
            else {
                st.pop();
            }
        }
    }
 
    if (!st.empty()) {
        return false;
    }
 
    return true;
}
 
int main() {
 
    string s = "";
 
    while (true) {
        
        //입력
        getline(cin, s);
 
        //종료 조건
        if (s == ".") {
            break;
        }
 
        //균형잡힌 문자열인지 판단 후 출력
        if (isBalanced(s)) {
            cout << "yes" << "\n";
        }
        else {
            cout << "no" << "\n";
        }
    }
 
    //종료
    return 0;
}
 

스택의 활용인 '괄호 검사'에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 14502 - 연구소 (0)	2021.01.03
[C++] 백준 1120 - 문자열 (0)	2021.01.03
[C++] 백준 10773 - 제로 (0)	2021.01.01
[C++] 백준 1764 - 듣보잡 (0)	2021.01.01
[C++] 백준 2636 - 치즈 (0)	2020.12.28

www.acmicpc.net/problem/10773

10773번: 제로

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경

www.acmicpc.net

<풀이>

1. 정수를 입력받는다.

2. 입력받은 수가 0일 경우, 가장 최근에 넣었던 수를 지운다.

3. 남아있는 모든 수의 합을 출력한다.

<해법>

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

#include <iostream>
#include <vector>
 
using namespace std;
 
int k;
vector<int> v;
 
int answer = 0;
 
int main() {
    
    //입력
    cin >> k;
 
    for (int i = 0; i < k; i++) {
        int tmp;
        cin >> tmp;
        
        //0일 경우 가장 최근에 담은 수 빼기
        if (tmp == 0) {
            v.pop_back();
        }
        //0이 아닌 경우 담기
        else {
            v.push_back(tmp);
        }
    }
 
    //담긴 수 모두 더하기
    for (int i = 0; i < v.size(); i++) {
        answer += v[i];
    }
 
    //출력
    cout << answer;
}
 

후입선출 자료구조에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 1120 - 문자열 (0)	2021.01.03
[C++] 백준 4949 - 균형잡힌 세상 (0)	2021.01.01
[C++] 백준 1764 - 듣보잡 (0)	2021.01.01
[C++] 백준 2636 - 치즈 (0)	2020.12.28
[C++] 백준 2941 - 크로아티아 알파벳 (0)	2020.12.27

www.acmicpc.net/problem/1764

1764번: 듣보잡

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다.

www.acmicpc.net

<풀이>

1. 듣잡 명단과 보잡 명단을 입력받는다.

2. 듣잡 명단과 보잡 명단에 공통적으로 있는 사람을 찾고, 출력한다.

<해법>

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
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
//입력
int n, m;
vector<string> listen;
vector<string> see;
 
//결과
vector<string> answer;
 
//듣잡 벡터에서 문자열 key 찾는 이분탐색
bool find(string key) {
 
    int start = 0, end = listen.size();
 
    while (start <= end) {
        
        int middle = (start + end) / 2;
 
        if (key < listen[middle]) {
            end = middle - 1;
        }
        else if (key > listen[middle]) {
            start = middle + 1;
        }
        //key값을 찾는 경우, true 리턴
        else {
            return true;
        }
    }
 
    //key값을 찾지 못하였을 경우, false 리턴
    return false;
}
 
int main() {
 
    //입력
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        listen.push_back(tmp);
    }
    for (int i = 0; i < m; i++) {
        string tmp;
        cin >> tmp;
        see.push_back(tmp);
    }
 
    //듣잡 벡터 사전순 정렬
    sort(listen.begin(), listen.end());
 
    for (int i = 0; i < m; i++) {
 
        //듣잡 벡터 안에 보잡 문자열이 있는지 확인
        bool isIn = find(see[i]);
 
        //듣보잡인 경우
        if (isIn) {
            //결과 벡터에 추가
            answer.push_back(see[i]);
        }
    }
 
    //결과 벡터 사전순 정렬
    sort(answer.begin(), answer.end());
    
    //결과 출력
    cout << answer.size() << "\n";
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << "\n";
    }
 
    //종료
    return 0;
}
 

이분탐색에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 4949 - 균형잡힌 세상 (0)	2021.01.01
[C++] 백준 10773 - 제로 (0)	2021.01.01
[C++] 백준 2636 - 치즈 (0)	2020.12.28
[C++] 백준 2941 - 크로아티아 알파벳 (0)	2020.12.27
[Python] 백준 10834 - 벨트 (0)	2020.06.21

www.acmicpc.net/problem/2636

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net

<풀이>

1. 치즈 맵을 입력받는다.

2. 바깥쪽 공기와 맞닿는 치즈를 없앤다.

3. 치즈가 모두 없어졌을 때까지 걸린 시간과, 그 전 치즈 개수를 출력한다.

<해법>

1. 바깥쪽 공기와 맞닿는 치즈를 없애는 방법

=> 탐색(BFS, DFS) 이용합니다. 탐색을 이용해서 바깥쪽 공기가 어디까지 퍼져있는지 확인합니다. 탐색 진행 도중에 치즈를 발견했을 경우, 바깥 공기와 맞닿는 치즈이므로 치즈를 없애는 식으로 진행하였습니다.

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
114
115
116
117

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
//4방향 : 북,동,남,서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int height, width;
int map[100][100];
bool visited[100][100];
 
int resTime = 0;
int resCheeze = 0;
 
//구조 : 좌표
struct pos {
    int x, y;
};
 
//맵에 치즈가 없는지 확인 : 없으면 true, 있으면 false
bool noCheeze() {
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (map[i][j] == 1) {
                return false;
            }
        }
    }
    return true;
}
 
//치즈 없애기
void removeCheeze() {
    
    //방문 배열 초기화
    memset(visited, false, sizeof(visited));
 
    //바깥쪽 공기만 탐색
    queue<pos> q;
    q.push({ 0,0 });
    visited[0][0] = true;
 
    while (!q.empty()) {
        pos cur = q.front();
        q.pop();
 
        //4방향 탐색
        for (int i = 0; i < 4; i++) {
            pos nxt = cur;
            nxt.x += di[i];
            nxt.y += dj[i];
 
            //범위 밖 or 방문했던 경우 -> continue
            if (nxt.x < 0 || nxt.y < 0 || nxt.x >= height || nxt.y >= width || visited[nxt.x][nxt.y]) {
                continue;
            }
 
            //공기일 경우 -> 큐에 넣기(계속 탐색을 해야하므로)
            if (map[nxt.x][nxt.y] == 0) {
                q.push(nxt);
            }
            //치즈일 경우 -> 바깥 공기와 맞닿는 치즈이므로 공기로 바꾸어줌, 큐에 담지 않음(더 이상 탐색X)
            else {
                map[nxt.x][nxt.y] = 0;
            }
            visited[nxt.x][nxt.y] = true;
        }
    }
 
}
 
//치즈 개수 세기
int countCheeze() {
    int output = 0;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (map[i][j] == 1) {
                output++;
            }
        }
    }
    return output;
}
 
int main() {
 
    //입력
    cin >> height >> width;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            cin >> map[i][j];
        }
    }
 
    while (true) {
 
        //치즈가 없을 경우 -> 종료
        if (noCheeze()) {
            break;
        }
 
        //치즈 개수 갱신
        resCheeze = countCheeze();
 
        //치즈 없애기
        removeCheeze();
 
        //시간 + 1
        resTime++;
    }
 
    //출력
    cout << resTime << "\n" << resCheeze;
}
 

탐색과 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 10773 - 제로 (0)	2021.01.01
[C++] 백준 1764 - 듣보잡 (0)	2021.01.01
[C++] 백준 2941 - 크로아티아 알파벳 (0)	2020.12.27
[Python] 백준 10834 - 벨트 (0)	2020.06.21
[Python] 백준 10833 - 사과 (0)	2020.06.21

www.acmicpc.net/problem/2941

2941번: 크로아티아 알파벳

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z=

www.acmicpc.net

<풀이>

1. 문자열을 입력받습니다.

2. 입력된 문자열에 크로아티아 문자열이 있는지 찾고, 한 문자로 변경합니다.

3. 바뀐 문자열의 길이를 출력합니다.

<해법>

1. 문자열 문제 마음가짐

=> 문자열 문제를 마주했을 때, 가장 먼저 '문자열 다루는 함수'를 적극적으로 사용하겠다는 생각을 해야합니다. 위 문제도 사실 굳이 문자열 다루는 함수를 사용하지 않더라도 많은 조건문으로 풀 수 있습니다. 직관적으로 풀 수 있다는 장점이 있지만, 코드가 길어져서 지저분해질 뿐만 아니라 많은 예외 처리를 해야 합니다. 하지만, '문자열 다루는 함수를 사용해야겠다.' 라는 마음가짐만 갖고 시작하더라도 문제를 좀 더 쉽게 풀 수 있습니다.

2. 입력된 문자열에서 크로아티아 문자열을 찾는 방법, 크로아티아 문자열 바꾸기

=> string의 find함수, string의 replace함수 사용하기

아래 잘 정리된 블로그를 참고하시면 좋을 것 같습니다.

blockdmask.tistory.com/338

[C++] string 클래스, 문자열에 대해서 (총정리)

안녕하세요 BlockDMask 입니다. 오늘은 C++의 std::string 클래스(문자열)에 대해서 세세 하게 알아볼것 입니다. 예전 글을 보다가 제가 작성한 이 문서를 보게 되었는데요, 너무 내용이 빈약하다고

blockdmask.tistory.com

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 <string>
#include <vector>
 
using namespace std;
 
//c=, c-, dz=, d-, lj, nj, s=, z=
vector<string> croatia = { "c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z=" };
 
string input;
 
//결과
int res = 0;
 
int main() {
 
    //입력 ex) input : ddz=z=
    cin >> input;
 
    for (int i = 0; i < croatia.size(); i++) {
        //크로아티아 문자열 찾기
        while (true) {
            int index = input.find(croatia[i]);
 
            //크로아티아 문자열이 없을 경우
            if (index == string::npos) {
                break;
            }
 
            //크로아티아 문자열 -> "#"으로 바꾸기
            input.replace(index, croatia[i].length(), "*");
        }
    }
 
    //ex) input : d**
    res = input.length();
 
    //출력
    cout << res << "\n";
}

문자열 다루는 방법에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 1764 - 듣보잡 (0)	2021.01.01
[C++] 백준 2636 - 치즈 (0)	2020.12.28
[Python] 백준 10834 - 벨트 (0)	2020.06.21
[Python] 백준 10833 - 사과 (0)	2020.06.21
[C++] 백준 8981 - 입력숫자 (0)	2020.04.30

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

10834번: 벨트

첫 줄에는 벨트의 개수를 나타내는 자연수 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 M개의 줄에는 1번 벨트부터 순서대로 벨트로 이어진 두 바퀴의 회전수의 비를 나타내는 두 개의 양의 정수 a, b와 벨��

www.acmicpc.net

<풀이>

1. 벨트 개수를 입력받는다.

2. 각 벨트마다 다음 바퀴의 방향과 회전 수를 저장한다.

3. 결과를 출력한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def main() :
 
    # 입력
    M = int(input())
 
    # 초기화
    resultDir = 0
    resultCnt = 1
    
    # 구현
    for _ in range(M) :
        first, second, dir = map(int, input().split())
        resultDir = resultDir ^ dir
        resultCnt = resultCnt // first * second
 
    # 출력
    print(resultDir, resultCnt)
 
if __name__ == '__main__' :
    main()
 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 2636 - 치즈 (0)	2020.12.28
[C++] 백준 2941 - 크로아티아 알파벳 (0)	2020.12.27
[Python] 백준 10833 - 사과 (0)	2020.06.21
[C++] 백준 8981 - 입력숫자 (0)	2020.04.30
[C++] 백준 8980 - 택배 (0)	2020.04.30

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

10833번: 사과

경상북도 특산품인 사과를 학생들에게 나눠주기 위해 여러 학교에 사과를 배정하였다. 배정된 사과 개수는 학교마다 다를 수 있고, 학생 수도 학교마다 다를 수 있다. 각 학교에서는 배정된 사��

www.acmicpc.net

<풀이>

1. 학교 수를 입력받는다.

2. 각 학교마다 입력받는 사과 수를 학생 수로 나눈 나머지의 합을 구한다.

3. 결과를 출력한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def main() :
 
    # 입력
    N = int(input())
 
    # 초기화
    result = 0
 
    # 구현
    for i in range(0,N,1) :
        student, apple = map(int, input().split())
        result += (apple % student)
 
    # 출력
    print(result)
 
if __name__ == '__main__' :
    main()
 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 백준 2941 - 크로아티아 알파벳 (0)	2020.12.27
[Python] 백준 10834 - 벨트 (0)	2020.06.21
[C++] 백준 8981 - 입력숫자 (0)	2020.04.30
[C++] 백준 8980 - 택배 (0)	2020.04.30
[C++] 백준 2512 - 예산 (0)	2020.04.30

알고리즘 고수가 되기까지