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


공백을 포함한 문자열을 받을 때는



getline(cin, string변수);


이와 같이 사용한다. 다만 이를 다른 입력과 함께 사용할 경우 버퍼에 개행이 포함되어 개행이 누락되는 경우가 있기 때문에 조심해야 한다. 이 문제의 경우에는 입력을 한 번만 받기 때문에 상관이 없었지만, 조심해야 한다.




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
#include<iostream>
#include<string>
using namespace std;
 
int main(void) {
    char chr[1000001];
    //cin >> str;
    string str;
    getline(cin, str);
 
 
    int cnt = 0;
    bool findOne = false, findSpace = false;
    //첫번째 단어를 찾았는지, 현재 공백이 등장한 상태인지
 
    for (int i = 0; i < str.length(); i++) {
        if (!findOne && str[i] != ' ') {
            findOne = true;
            cnt++;
            continue;
        }
        else if(findOne) {
            if (str[i] == ' ') findSpace = true;
            else {
                if (findSpace) {
                    cnt++;
                    findSpace = false;
                }
            }
        }
    
    }
    cout << cnt << '\n';
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11724번: 연결 요소의 개수 (C++)  (0) 2019.09.25
백준 11403번: 경로 찾기 (C++)  (0) 2019.09.25
백준 2193번: 이친수 (C++)  (0) 2019.09.19
백준 1003번: 피보나치 함수 (C++)  (0) 2019.09.19
백준 9095번: 1,2,3 더하기 (C++)  (0) 2019.09.19

주어진 숫자의 개수만큼 연산자를 결정해주면 된다.


첫번째로 결정된 연산자는 첫번째 사용되는 숫자의 부호를 결정한다고 볼 수 있다.


이후의 연산자는 말그대로 연산자로 생각해서 숫자들을 더하거나 빼주는 계산을 해주면 된다.



백트레킹을 통해서 모든 경우의 수에 대하여 연산자를 결정해준다.




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 <string>
#include <vector>
#include<iostream>
 
using namespace std;
int val, opr[2] = {1,0}; //+, -
int arr[20], ret = 0;
void btk(int k, vector<int> &nums, int tar) {
    if (k == val) {
        int Sum = 0;
        for (int i = 0; i < k; i++) {
            if (i == 0) { //첫 숫자 부호
                if (arr[0] == 1)
                    Sum = nums[0];
                else
                    Sum = nums[0] * -1;
            }
            else { //나머지 연산자
                if (arr[i] == 1)
                    Sum += nums[i];
                else
                    Sum -= nums[i];
            }
        }
        if (Sum == tar) ret++;
        return;
    }
    
    for (int i = 0; i < 2; i++) {
        arr[k] = opr[i];
        btk(k + 1, nums, tar);
    }
}
int solution(vector<int> nums, int tar) {
    val = nums.size();
    btk(0, nums, tar);
    return ret;
}
 
int main(void) {
    solution({ 1,1,1,1,1 }, 3);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27
프로그래머스: 소수찾기 (C++)  (0) 2019.09.27
프로그래머스: 문자열 내 p와 y의 개수 (C++)  (0) 2019.09.20
프로그래머스: 전화번호 목록  (0) 2019.09.19
카카오 2017 블라인드 테스트 1차: 셔틀버스 (C++)  (0) 2019.08.25

https://programmers.co.kr/learn/courses/30/lessons/12916



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <string>
#include <iostream>
#include<algorithm>
using namespace std;
 
int cnt[2];
bool solution(string s)
{
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'p') cnt[0]++;
        else if (s[i] == 'y') cnt[1]++;
    }
    if (cnt[0] == cnt[1]) return 1;
    else return 0;
 
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 소수찾기 (C++)  (0) 2019.09.27
프로그래머스: 타겟 넘버 (C++)  (0) 2019.09.20
프로그래머스: 전화번호 목록  (0) 2019.09.19
카카오 2017 블라인드 테스트 1차: 셔틀버스 (C++)  (0) 2019.08.25
카카오 2017 블라인드 테스트 1차: 캐시 (C++)  (0) 2019.08.25

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



설명은 주석으로 대체한다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
typedef long long ll;
using namespace std;
 
ll d[91]; //i자리 이친수의 개수
int main(void) {
    
    d[1] = 1; // 1
    d[2] = 1; //10
    for (int i = 3; i <= 90; i++) {
        d[i] = 1;
        for (int j = i - 2; j >= 1; j--) {
            d[i] += d[j]; 
        }//맨앞 1두면 바로옆은 무조건 0이고, 남은 자리에 이친수를 채워준다
    }
    
    int val;
    cin >> val;
    cout << d[val];
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11403번: 경로 찾기 (C++)  (0) 2019.09.25
백준 1152번: 단어의 개수 (C++)  (0) 2019.09.20
백준 1003번: 피보나치 함수 (C++)  (0) 2019.09.19
백준 9095번: 1,2,3 더하기 (C++)  (0) 2019.09.19
백준 1600번: 말이 되고픈 원숭이 (C++)  (0) 2019.09.06


0과 1이 사용되는 횟수를 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
#include<iostream>
using namespace std;
 
int zero[41], one[41];
int main(void) {
    
    zero[0] = 1;
    zero[1] = 0;
    zero[2] = 1;
    one[0] = 0;
    one[1] = 1;
    one[2] = 1;
    
    for (int i = 3; i < 41; i++) {
        zero[i] = zero[i - 1] + zero[i - 2];
        one[i] = one[i - 1] + one[i - 2];
    }
    int n;
    cin >> n;
    while (n--) {
        int val;
        cin >> val;
        cout << zero[val] << ' ' << one[val] << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1152번: 단어의 개수 (C++)  (0) 2019.09.20
백준 2193번: 이친수 (C++)  (0) 2019.09.19
백준 9095번: 1,2,3 더하기 (C++)  (0) 2019.09.19
백준 1600번: 말이 되고픈 원숭이 (C++)  (0) 2019.09.06
백준 5397번: 키로거 (C++)  (0) 2019.09.02

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



시작하는 수를 설정해둔다.


가령 5를 만드는 경우는


1 + 4를 만드는 경우

2 + 3을 만드는 경우

3 + 2를 만드는 경우


이렇게 볼 수 있다.


arr[i] = 1,2,3을 사용해서 합 i를 만드는 방법의 수라고 한다면



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
 
using namespace std;
int arr[11]; //1,2,3을 적절히 더해서 i를 만드는 방법의 수 (순서 다르면 다른 경우로 봄)
int main(void) {
    
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;
 
    for (int i = 4; i <= 10; i++) 
        arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1];
    
    int n;
    cin >> n;
    while (n--) {
        int val;
        cin >> val;
        cout << arr[val] << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2193번: 이친수 (C++)  (0) 2019.09.19
백준 1003번: 피보나치 함수 (C++)  (0) 2019.09.19
백준 1600번: 말이 되고픈 원숭이 (C++)  (0) 2019.09.06
백준 5397번: 키로거 (C++)  (0) 2019.09.02
백준 1987번: 알파벳 (c++)  (0) 2019.09.01

https://www.welcomekakao.com/learn/courses/30/lessons/42577



해시 카테고리로 분류되어 있긴 하지만, 본인이 편한 풀이로 풀면 그만이다.



본인은 전화번호들을 길이가 길어지는 순서대로 정렬하였다.


이후에 짧은 전화번호를 기준으로 그것보다 긴 전화번호들을 비교했다.




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
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
 
bool cmp(string a, string b) {
    return a.length() < b.length();
}
bool solution(vector<string> pb) {
    sort(pb.begin(), pb.end(), cmp); //길이 짧은게 앞으로
    
    
 
    for (int i = 0; i < pb.size(); i++) {
        for (int j = i+1; j < pb.size(); j++) {
            bool isSame = true;
            for (int k = 0; k < pb[i].length(); k++) {
                if (pb[i][k] != pb[j][k]) {
                    isSame = false;
                    break;
                }
            }
            if (isSame) return false;
        }
    }
    return true;
}
 
int main(void) {
    solution({  "97674223", "1195524421", "119" });
    return 0;
}
 
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 타겟 넘버 (C++)  (0) 2019.09.20
프로그래머스: 문자열 내 p와 y의 개수 (C++)  (0) 2019.09.20
카카오 2017 블라인드 테스트 1차: 셔틀버스 (C++)  (0) 2019.08.25
카카오 2017 블라인드 테스트 1차: 캐시 (C++)  (0) 2019.08.25
카카오 2017 블라인드 테스트 1차: 다트 게임 (C++)  (0) 2019.08.25

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


방문 처리 배열을 3차원으로 만들어 준다. 나이트처럼 이동하는 것을 점프라고 하면, 


[row][col][이 지점에서 가능한 점프 횟수]


위와 같이 설정해준다.



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
#include<iostream>
#include<queue>
 
using namespace std;
int map[201][201], row, col, k;
bool  vis[201][201][31]; //r, c, 점프 가능 횟수
struct Info {
    int r, c, jump, cnt;
};
 
queue<Info> q;
const int dr[4] = { 0,0,1,-1 };
const int dc[4] = { 1,-1,0,0 };
const int jr[8] = { -2,-1,1,2,2,1,-1,-2 };
const int jc[8] = { 1,2,2,1,-1,-2,-2,-1 };

void bfs() {
    q.push({ 0, 0, k, 0 });
    vis[0][0][k] = true;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            
            Info cur = q.front();
            q.pop();
            if (cur.r == row - 1 && cur.c == col - 1) {
                cout << cur.cnt;
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 1) continue;
                
                if (vis[nr][nc][cur.jump]) continue; //z만큼 점프 개수를 남기고 온적이 있으면 pass
                q.push({ nr, nc, cur.jump, cur.cnt + 1 });
                vis[nr][nc][cur.jump] = true;
                
            }
 
            if (cur.jump <= 0) continue;
            for (int i = 0; i < 8 ; i++) {
                int nr = cur.r + jr[i];
                int nc = cur.c + jc[i];
                if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 1) continue;
                
                if (vis[nr][nc][cur.jump - 1]) continue; //z만큼 점프 개수를 남기고 온적이 있으면 pass
                q.push({ nr, nc, cur.jump - 1, cur.cnt + 1 });
                vis[nr][nc][cur.jump - 1] = true;
            }
 
        }
    }
    cout << -1;
}
 
int main(void) {
    cin >> k >> col >> row;
    for (int i = 0; i < row; i++) 
        for (int j = 0; j < col; j++) 
            cin >> map[i][j];
            
    bfs();
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1003번: 피보나치 함수 (C++)  (0) 2019.09.19
백준 9095번: 1,2,3 더하기 (C++)  (0) 2019.09.19
백준 5397번: 키로거 (C++)  (0) 2019.09.02
백준 1987번: 알파벳 (c++)  (0) 2019.09.01
백준 12851번: 숨바꼭질2 (C++)  (0) 2019.08.31

C++ STL list의 삽입과 삭제에 대해서 간단히 정리하고자 한다.


STL list .insert(iterator, 넣을 값)



L = { A, B, C }



연결리스트는 A->B->C 와 같이 구성되어 있는 것이지만 표기의 편의성을 위해 위와 같이 표기하였다.



위와 같은 연결리스트가 있고, 현재 iterator의 위치가 B라면, L.insert(iterator, 'K') 라는 코드를 실행하게 되면 결과는 다음과 같다.


{A, K, B, C}



iterator의 왼편에 새로운 값이 삽입이 되고, iterator는 원래 가르키던 값을 가르킨다고 생각하면 된다. 

( 이해의 편의를 위해서 이렇게 적었다)


그리고, insert 함수의 경우 아무 것도 반환하지 않는다.





다음으로는 삭제에 대해서 알아보자.


Iterator = list.erase(Iterator)


erase 함수는 삭제를 수행한 이후에 iterator를 반환한다. 따라서 반드시 반환되는 iterator을 받아서 갱신(저장)하는 방식으로 구현해줘야 한다.


L = { A, B, C }


위와 동일한 상황이고, 현재 iterator가 B를 가르키고 있는 상태에서, 


itr = list.erase(itr)


다음과 같은 구문을 실행하게 되면, L = {A, C } 이와 같은 상황이 되고, iterator는 없어진 B의 우측에 있던 값인 C를 가르킨다고 생각할 수 있다.

저작자표시 비영리 변경금지

'Programming Language > C++' 카테고리의 다른 글

vector upper_bound, lower_bound 사용 (C++)  (0) 2019.09.01
string 대소문자 변환  (0) 2019.08.25
priority_queue  (0) 2019.08.14
(C++) abs 함수의 사용  (0) 2019.08.07
(C++) list STL 출력 및 iterator  (0) 2019.08.04

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



여러가지 풀이가 가능하겠지만, 링크드리스트를 활용해서 풀었다.



STL list의 여러가지 함수들을 자유롭게 활용할 줄 안다면 무리 없이 풀리는 문제이다.



커서의 초점을 삽입에 맞추느냐 삭제에 맞추느냐에 따라서 풀이가 약간씩은 달라질 수 있겠다.



즉  a b c 이러한 문자열 상황에서, 커서가 a에 있는 상태에서, 삽입 명령이 들어오면 a 왼편에 새로운 문자가 들어가야 하고


삭제 명령이 들어오면 아무런 변화도 일어나지 않아야 한다.


하지만 실제 구현을 할 때, iterator를 .begin()에 두고 삭제를 하게 되면 a가 삭제될 것이다.


즉 삭제의 경우에는, 커서의 왼편에 있는 값을 삭제해주도록 구현을 해야한다.



정리하면, iterator의 위치를 insert의 인자로 활용하는 경우에, 삭제를 구현하려면 한 칸 왼쪽의 값을 삭제해주어야 한다.




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
#include<iostream>
#include<list>
#include<string>
using namespace std;
//list insert할 때, itr이 가리키는 왼편에 새로운 수 삽입, itr은 원래 가리키던 수를 가리킴
//erase: itr이 가리키던 수 지워버리고, 우측에 있는 수를 가리킴
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        string str;
        cin >> str;
        list<char> ans;
 
        
        list<char>::iterator itr = ans.end(); //커서의 초기 위치
        
        for (int i = 0; i < str.length(); i++) {
            
            if (str[i] == '<') {
                if (itr == ans.begin()) continue;
                itr--;
            }
            else if (str[i] == '>') {
                if (itr == ans.end()) continue;
                itr++;
            }
            else if (str[i] == '-') {
                if (itr == ans.begin()) continue;
                itr = ans.erase(--itr); //erase 시에는 반환되는 itr을 받아서 갱신해줘야 한다
            }
            else {
                ans.insert(itr, str[i]);
            }
        }
 
        //print
        for (auto it = ans.begin(); it != ans.end(); it++) 
            cout << *it;
        cout << '\n';
        ans.clear();
    }
    return 0;
}
 
 
cs

 

저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 9095번: 1,2,3 더하기 (C++)  (0) 2019.09.19
백준 1600번: 말이 되고픈 원숭이 (C++)  (0) 2019.09.06
백준 1987번: 알파벳 (c++)  (0) 2019.09.01
백준 12851번: 숨바꼭질2 (C++)  (0) 2019.08.31
백준 9019번: DSLR (C++)  (0) 2019.08.30

+ Recent posts

티스토리툴바