반응형

문제 출처

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://programmers.co.kr/learn/courses/30/lessons/42891


효율성 테스트가 있는 문제이다. 

전체 탐색을 하면 효율성 테스트에서 통과하지 못한다. idea는 정렬을 통해 가장 작은 값의 시간을 한번에 빼는 방법을 사용하였다.


소스코드

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 <algorithm>
 
using namespace std;
 
bool comp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}
 
int solution(vector<int> food_times, long long k) {
    vector<pair<int, int>> food;
    int size = food_times.size();
    for(int i=0; i<size; i++)
        food.push_back(make_pair(food_times.at(i), i+1));
    
    sort(food.begin(), food.end());
    
    int time=0;
    for(vector<pair<int, int>>::iterator it=food.begin(); it!=food.end(); it++, size--) {
        long long leadTime = (long long)(it->first - time) * size;
        if(leadTime == 0)
            continue;
        
        if(leadTime <= k) {
            k-=leadTime;
            time=it->first;
        } else {
            k%=size;
            sort(it, food.end(), comp);
            return (it+k)->second;
        }       
    }
    return -1;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 10809] 알파벳 찾기  (0) 2019.01.07
[BOJ_11724] 연결 요소의 개수  (0) 2019.01.07
[BOJ 11004] K번째 수  (0) 2019.01.07
[BOJ 3047] ABC  (0) 2019.01.06
[BOJ 1987] 알파벳  (0) 2019.01.05
반응형

문제 출처

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.welcomekakao.com/learn/courses/30/lessons/42888


닉네임은 중복이 가능하므로 Set이 아니라 Map을 사용하였습니다.

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
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
 
public class Solution
{
    public String[] solution(String[] record) {
        Map<String, String> idMap = new HashMap<>();
        List<String[]> tmp = new LinkedList<>();
 
        for (String records : record)
        {
            String[] keyWord = records.split(" ");
            if (keyWord[0].equals("Enter"))
            {
                idMap.put(keyWord[1], keyWord[2]);
                tmp.add(keyWord);
            } else if (keyWord[0].equals("Change"))
            {
                idMap.put(keyWord[1], keyWord[2]);
            } else
            {
                tmp.add(keyWord);
            }
        }
 
        String[] answer = new String[tmp.size()];
        int idx = 0;
        for (String[] keyWords : tmp)
        {
            String nickName = idMap.get(keyWords[1]);
            if (keyWords[0].equals("Enter"))
                answer[idx++] = nickName + "님이 들어왔습니다.";
            else
                answer[idx++] = nickName + "님이 나갔습니다.";
        }
        return answer;
    }
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 3047] ABC  (0) 2019.01.06
[BOJ 1987] 알파벳  (0) 2019.01.05
[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
[프로그래머스 42842] 카펫  (2) 2019.01.02
[프로그래머스 43162] 네트워크  (0) 2019.01.01
반응형

문제 출처

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

정답률 : 55.57%


sorting문제이다. 정렬을 활용하는 법을 확인하는 듯 하다. 역시 앞쪽이라 문제를 급하게 안읽고 차근차근 읽어나가면 쉽게 풀 수 있는 문제다.

전체사용자 수를 구하고 stages를 돌면서 몇명의 사용자가 도달했는지 카운트합니다. 다음으로 이 값과 stages를 참조하여 실패율을 계산하고 내림차순으로 정렬하면 되는 문제입니다.


소스코드

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 <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool compare(pair<double, int> a, pair<double, int> b)
{
    // 실패율이 같다면 스테이지 번호가 작은것!
    if(a.first == b.first)
        return a.second < b.second;
    
    // 실패율이 큰것이 앞!
    return a.first > b.first;
}
 
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    int users[501]={0};
    int userSize = stages.size();
    vector<pair<double, int>> failure;
    
    // 각각의 스테이지에 도달한 유저수
    for(vector<int>::iterator it = stages.begin(); it!=stages.end(); it++)
        users[*it-1]++;
    
    for(int i=0; i<N; i++)
    {
        if(users[i] == 0)
            failure.push_back(make_pair(0, i+1));
        else
        {
            failure.push_back(make_pair((double)users[i]/userSize, i+1));
            userSize -= users[i];
        }
    }
    
    sort(failure.begin(), failure.end(), compare);
    
    for(vector<pair<double, int>>::iterator it = failure.begin(); it!=failure.end(); it++)
        answer.push_back(it->second);
 
    return answer;
}
 
cs



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1987] 알파벳  (0) 2019.01.05
[카카오 2019] 코딩테스트 - 오픈채팅방  (0) 2019.01.03
[프로그래머스 42842] 카펫  (2) 2019.01.02
[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 6603] 로또  (0) 2018.12.31

+ Recent posts

티스토리툴바