반응형

문제 출처

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


문제풀이

1
2
3
4
5
6
/*
* 모든 높이에 대해 잠기지 않는 안전영역의 갯수를 카운트 해주면 되는 문제
* dfs / bfs로 풀이할 수 있다. 특히 0은 고려하지 않았는데 아래 노트를 보니
* 비가 오지 않는 경우도 있다고 써져있었다.... 하지만 생각해보면 전부 높이가 1인
* 경우가 있을 수 있기 때문에 0도 고려를 해야합니다.
*/
cs


소스코드

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 <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;
int n,result;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
void dfs(int x, int y, int height) {
    visit[x][y] = 1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n)    continue;
        if (map[nx][ny] > height && !visit[nx][ny])    dfs(nx, ny, height);
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int maxDepth = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            maxDepth = max(maxDepth, map[i][j]);
        }
    }
    for (int height = 0; height <= maxDepth; height++) {
        int safeBlock = 0;
        memset(visit, 0, sizeof(visit));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] > height && !visit[i][j]) {
                    dfs(i, j, height);
                    safeBlock++;
                }
            }
        }
        result = max(result, safeBlock);
    }
    cout << result << endl;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1325] 효율적인 해킹  (0) 2019.01.23
[BOJ 10039] 평균점수  (0) 2019.01.22
[BOJ 2661] 좋은 수열  (0) 2019.01.21
[BOJ 1759] 암호만들기  (0) 2019.01.21
[BOJ 1012] 유기농 배추  (0) 2019.01.21
반응형

문제출처

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


반복문을 2번 써서 풀이할 수도 있으나 좋은 방법은 아니다. stl을 사용하기는 했지만 사용하지 않고 더 좋은 방법을 생각해 봐야겠다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string doc, word;
    int cnt = 0;
    getline(cin, doc);
    getline(cin, word);
 
    auto tmp = doc.find(word);
    while (tmp != string::npos) {    // 찾는 문자열이 없을때까지 반복
        cnt++;
        // 해당 글자를 찾은 위치부터 다시 찾는다.
        tmp = doc.find(word, tmp + word.size());
    }
    cout << cnt;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 14501] 퇴사  (0) 2019.01.14
[BOJ 1182] 부분집합의 합  (0) 2019.01.14
[BOJ 2941] 크로아티아 알파벳  (0) 2019.01.07
[BOJ 1316] 그룹 단어 체크  (0) 2019.01.07
[BOJ 2908] 상수  (0) 2019.01.07
반응형

문제출처

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


해당 문자를 찾을 경우 위치 배열에 값을 넣어준다.


소스코드

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>
#include <vector>
#include <string>
 
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string str;
    cin >> str;
 
    // 알파벳 갯수만큼 -1로 초기화
    vector<int> v(26, -1);
    for (int i = 0; i < str.size(); i++) {
 
        // 소문자 a의 ASCII값 = 97
        if (v[str.at(i) - 97] == -1)
            v[str.at(i) - 97] = i;
    }
 
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
        cout << *it << " ";
 
    return 0;
}
cs



1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <string.h>
int main() {
    char s[101];
    int loc[26];
    memset(loc, -1, sizeof(loc));
    scanf("%s", &s);
    int len = strlen(s);
    while(len--) loc[s[len] - 'a'] = len;
    for(int i=0; i<26; i++) printf("%d ", loc[i]);
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1316] 그룹 단어 체크  (0) 2019.01.07
[BOJ 2908] 상수  (0) 2019.01.07
[BOJ_11724] 연결 요소의 개수  (0) 2019.01.07
[카카오 2019] 코딩테스트 - 무지의 먹방 라이브  (0) 2019.01.07
[BOJ 11004] K번째 수  (0) 2019.01.07
반응형

문제출처

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


dfs / bfs 두가지 모두 풀이가 가능하다. 하지만 분류가 bfs로 되어있어 bfs로 풀이하였다. bfs 개념을 익히는데 도움이 되는 문제


소스코드

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
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
int v, e;    //vertex, edge
int result;
bool visit[1001];
bool g[1001][1001];
void bfs(int s) {
    queue<int> q;
    q.push(s);
    visit[s] = 1;
    
    while (!q.empty()) {
        s = q.front();
        q.pop();
 
        for (int i = 1; i <= sizeof(g[s]); i++) {
            if (g[s][i] && !visit[i]) {
                q.push(i);
                visit[i] = 1;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> v >> e;
    int start, end;
    // init graph...
    for (int i = 1; i <= e; i++) {
        cin >> start >> end;
        g[start][end] = 1;
        g[end][start] = 1;
    }
 
    for (int i = 1; i <= v; i++) {
        if (!visit[i]) {
            bfs(i);
            result++;
        }
    }
 
    cout << result;
    return 0;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2908] 상수  (0) 2019.01.07
[BOJ 10809] 알파벳 찾기  (0) 2019.01.07
[카카오 2019] 코딩테스트 - 무지의 먹방 라이브  (0) 2019.01.07
[BOJ 11004] K번째 수  (0) 2019.01.07
[BOJ 3047] ABC  (0) 2019.01.06
반응형

문제 출처

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


단순 정렬하는 문제이다...

sort함수 사용


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n, k;
vector<int> v;
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    v.resize(n);
 
    for(int i=0; i<n; i++)
        cin>>v[i];
 
    sort(v.begin(), v.end());
    cout<<v[k-1]<<endl;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ_11724] 연결 요소의 개수  (0) 2019.01.07
[카카오 2019] 코딩테스트 - 무지의 먹방 라이브  (0) 2019.01.07
[BOJ 3047] ABC  (0) 2019.01.06
[BOJ 1987] 알파벳  (0) 2019.01.05
[카카오 2019] 코딩테스트 - 오픈채팅방  (0) 2019.01.03
반응형

문제출처

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


정렬을 이용하는 문제


소스코드

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 <string>
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    vector<int> v(3);
    for(int i=0; i<v.size(); i++)
        cin>>v[i];
 
    sort(v.begin(), v.end());
 
    string str;
    cin>>str;
 
    for(int i=0; i<str.length(); i++)
        cout<<v[str[i]-'A']<<" ";
 
    return 0;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[카카오 2019] 코딩테스트 - 무지의 먹방 라이브  (0) 2019.01.07
[BOJ 11004] K번째 수  (0) 2019.01.07
[BOJ 1987] 알파벳  (0) 2019.01.05
[카카오 2019] 코딩테스트 - 오픈채팅방  (0) 2019.01.03
[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
반응형

문제 출처

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


dfs로 순회해주면 된다.

bitmask 대신 visit을 사용해도 되지만 오늘 bitmask를 공부한 관계로 bitmask를 사용해 보았다.

문제자체는 단순 순회니 어렵지 않은 문제


소스코드

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
//
//  main.cpp
//  BOJ_1987
//
//  Created by sw on 05/01/2019.
//  Copyright © 2019 sw. All rights reserved.
//
#include<iostream>
#include<algorithm>
using namespace std;
int r, c;
char map[21][21];
 
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
 
int dfs(int x, int y, int status) {
    int ret = 1;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx < 0 || ny < 0 || nx >= r || ny >= c)
            continue;
        
        int v = 1 << (map[nx][ny] - 'A');
        if (status & v)
            continue;
        
        ret = max(ret, dfs(nx, ny, status | v) + 1);
    }
    return ret;
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> map[i][j];
        }
    }
    cout << dfs(0, 0, 1 << (map[0][0] - 'A'));
    return 0;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 11004] K번째 수  (0) 2019.01.07
[BOJ 3047] ABC  (0) 2019.01.06
[카카오 2019] 코딩테스트 - 오픈채팅방  (0) 2019.01.03
[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
[프로그래머스 42842] 카펫  (2) 2019.01.02
반응형

문제출처

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


간단한 dfs문제이다. xcode에 에러가 있어서 무슨 문제인가 계속 살펴봤는데 그냥 xcode 문제....

dfs호출시 시작 index와 depth를 인자로 넘겨줘서 끝까지 탐색하는 방법이다.


소스코드

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
//
//  main.cpp
//  BOJ_6603
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAX = 13;
int k;
int num[MAX];
int result[MAX];
 
void dfs(int start, int depth) {
    if(depth == 6)
    {
        for(int i=0; i<depth; i++)
        {
            printf("%d ", result[i]);
        }
        printf("\n");
        
        return;
    }
    
    for(int i=start; i<k; i++)
    {
        result[depth]=num[i];
        dfs(i+1, depth+1);
    }
}
int main(int argc, const char * argv[]) {
    
    while(true)
    {
        scanf("%d", &k);
        if(k==0){
            printf("\n");
            break;
        }
        for(int i=0; i<k; i++)
        {
            scanf("%d", &num[i]);
        }
        dfs(0,0);
        printf("\n");
    }
    return 0;
}
 
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 42842] 카펫  (2) 2019.01.02
[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2644] 촌수계산  (0) 2018.12.31
반응형

문제출처

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


DFS로 풀이한 문제 따로 visit배열을 사용하지 않고 dfs를 호출할 때 이미 방문한 곳은 값을 0으로 할당합니다. 때문에 map이 1인 경우만 탐색하면 되며 한개의 단지를 구한 후 dfs가 재호출될때 기존의 단지는 map상에 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
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
//
//  main.cpp
//  BOJ_2667
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 25
 
using namespace std;
 
int n, cnt;
vector<int> section;
int map[MAX][MAX];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
 
void init() {
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            int tmp;
            scanf("%1d", &tmp);
            map[i][j]=tmp;
        }
}
 
void dfs(int x, int y) {
    map[x][y]=0;
    cnt++;
    
    for(int i=0; i<4; i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        
        if(nx>=0 && ny>=0 && nx<n && ny<n && map[nx][ny])
            dfs(nx, ny);
    }
}
 
int main(int argc, const char * argv[]) {
    init();
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(map[i][j])
            {
                cnt=0;
                dfs(i, j);
                section.push_back(cnt);
            }
        }
    }
    
    int len = section.size();
    printf("%d\n", len);
    
    sort(section.begin(), section.end());
    for(int i=0; i<len; i++)
        printf("%d\n", section.at(i));
    
    return 0;
}
 
cs



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 6603] 로또  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2644] 촌수계산  (0) 2018.12.31
[BOJ 2606] 바이러스  (0) 2018.12.28
반응형

문제 출처

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


단순 bfs구현 문제이다.

ret배열이 0이라면 관계가 없으므로 -1을 출력하고 0이 아니면 해당 값을 출력하도록 했다.

bfs / dfs를 언제 사용하는지 감이 잘 안왔었는데 간단히 정리하면


bfs를 이용하는 경우

1. 시작 지점에서 가장 가까운 것을 구하고 싶은 경우

2. 탐색 범위 자체는 넓지만 어느정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있는 경우

3. 탐색 범위가 굉장히 넒으며 dfs를 사용할 때 스택이 대량으로 사용될 경우 이다.


반면 dfs를 이용하는 경우는

1. 모든 경로를 탐색하고 결과를 확인해야 하는 경우

2. 문자열 등을 탐색할 때 '사전 순서로 앞에오는 것'처럼 앞에서 검색해서 찾는 것이 빠를 경우 이다.


즉, 탐색 범위가 넓은 경우와 전체 탐색을 하지 않아도 될 경우는 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
//
//  main.cpp
//  BOJ_2644
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
 
#include<iostream>
#include<queue>
#define MAX 101
 
using namespace std;
int n, src, dest, m, adj[MAX][MAX], ret[MAX];
 
int main(int argc, const char * argv[]) {
    cin >> n >> src >> dest >> m;
    for (int i = 0; i < m; i++) {
        int x = 0, y = 0;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = 1;
    }
    
    queue<int> q;
    q.push(src);
    
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (adj[now][i] == 0 || ret[i] != 0)
                continue;
            ret[i] = ret[now] + 1;
            q.push(i);
        }
    }
    cout << (ret[dest] == 0 ? -1 : ret[dest]) << endl;
    return 0;
}
 
cs





반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2606] 바이러스  (0) 2018.12.28
[BOJ 2583] 영역구하기  (0) 2018.12.28
[TopCoder 전체탐색] 회문(Palindrome)  (0) 2018.12.20

+ Recent posts

티스토리툴바