반응형

문제출처

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
반응형

문제출처

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


문제를 읽으면 빨간색은 갈색으로 둘러쌓여있다고 한다. 즉 카펫의 가로,세로가 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
#include <string>
#include <vector>
#include <math.h>
using namespace std;
 
vector<int> solution(int brown, int red) {
    vector<int> answer;
    int sum=brown+red;
    int limit=(int)sqrt(sum);
    
    for(int i=3; i<=limit; i++)
    {
        if(sum % i ==0)
        {
            int tmp = sum/i;
            //전체 카펫 위,아래 row 왼쪽,오른쪽 col을 제외하고 곱하면 red타일의 갯수가 나온다.
            if((tmp-2) * (i-2) == red)
            {
                answer.push_back(tmp);
                answer.push_back(i);
                break;
            }
        }
    }
    return answer;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[카카오 2019] 코딩테스트 - 오픈채팅방  (0) 2019.01.03
[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 6603] 로또  (0) 2018.12.31
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
반응형

문제 출처

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


dfs로 전체 탐색을 하면서 순회가 끝나면 answer값을 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
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visit[200];
 
void dfs(int start, vector<vector<int>> &computers, int n) {
    visit[start]=1;
    for(int i=0; i<n; i++)
    {
        if(!visit[i] && computers[start][i])
            dfs(i, computers, n);
    }
    
}
 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0; i<n; i++)
    {
        if(!visit[i])
        {
            answer++;
            dfs(i, computers, n);
        }
    }
    return answer;
}
 
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
[프로그래머스 42842] 카펫  (2) 2019.01.02
[BOJ 6603] 로또  (0) 2018.12.31
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
반응형

문제출처

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


처음에 어떻게 풀어야 하는지 고민하던 문제다. 전체 numbers를 root로 두고 depth를 1씩 늘려가는 트리형식으로 내려가는 형식으로 풀이했다. 

[1, 1, 1, 1, 1]이 있다면 

첫번째 depth는 1과 -1이 될 것이고 두번째는 1에서 파생된 1+1, 1-1 // -1에서 파생된 -1+1, -1-1 두가지가 될 것이다. 이로 쭉쭉 내려가서 numbers.size()가 5이므로 depth는 5까지 뻗어나갈 수 있는데 이때 target과 현재 depth에서의 합계가 같으면 전역변수 ret을 +1해 준후 return해준다.


소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <string>
#include <vector>
 
using namespace std;
int ret;
 
void dfs(vector<int> &numbers, int target, int sum, int depth) {
    if(depth >= numbers.size()) {
        if(sum==target)
            ret++;
        return;
    }
    dfs(numbers, target, sum+numbers[depth], depth+1);
    dfs(numbers, target, sum-numbers[depth], depth+1);
}
 
int solution(vector<int> numbers, int target) {
    dfs(numbers, target, numbers[0] , 1);
    dfs(numbers, target, numbers[0]*-1, 1);
 
    return ret;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 6603] 로또  (0) 2018.12.31
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[BOJ 2644] 촌수계산  (0) 2018.12.31
[BOJ 2606] 바이러스  (0) 2018.12.28
[BOJ 2583] 영역구하기  (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

티스토리툴바