반응형

문제출처

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


소스코드

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
#include <stdio.h>
#include <queue>
#define MAX 1000
using namespace std;
struct tomatoInfo {
    int cy, cx, time;
};
int n, m;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
int map[MAX][MAX];
bool visit[MAX][MAX];
queue<tomatoInfo> q;
 
void init() {
    scanf("%d %d", &n, &m);
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            scanf("%d", &map[y][x]);
            if (map[y][x] == 1) {
                q.push({y, x, 0});
                visit[y][x]=1;
            }
        }
    }
}
 
bool isOutOfBoundMap(int y, int x) {
    if (x<0 || y<0 || x>=n || y>=m) {
        return true;
    }
    return false;
}
 
bool checkMap() {
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            if (map[y][x]==0) {
                return false;
            }
        }
    }
    return true;
}
 
void bfs() {
    int t;
    while (!q.empty()) {
        int y = q.front().cy;
        int x = q.front().cx;    
        t = q.front().time;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if (isOutOfBoundMap(ny, nx) || visit[ny][nx]) {
                continue;
            }
            if (map[ny][nx] == 0 && !visit[ny][nx]) {
                q.push({ny, nx, t+1});
                map[ny][nx]=1;
                visit[ny][nx]=1;
            }
        }
    }
    
    checkMap()==1 ? printf("%d", t) : printf("-1");    
}
int main() {
    init();
    bfs();
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[SWEA 2805] 농작물 수확하기  (0) 2019.07.23
[SWEA 5162] 두가지 빵의 딜레마  (0) 2019.07.23
[BOJ 1206] DFS와 BFS  (0) 2019.07.05
[BOJ 1120]문자열  (0) 2019.07.03
[BOJ 5585] 거스름돈  (0) 2019.07.03
반응형

문제출처

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


소스코드

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
#include <iostream>
#include <queue>
#include <cstring>
#define MAX 1000
using namespace std;
int n, m, v;
int map[MAX][MAX];
bool visit[MAX];
 
void init() {
    cin>>n>>m>>v;
    int s,e;
    for (int i=0; i<m; i++) {
        cin>>s>>e;
        map[s][e]=1;
        map[e][s]=1;
    }
}
 
void dfs(int s) {
    visit[s]=1;
    cout<<s<<" ";
    for (int i=0; i<=n; i++) {
        if (!visit[i] && map[s][i] == 1) {
            dfs(i);
        }
    }
}
 
void bfs(int s) {
    queue<int> q;
    q.push(s);
    visit[s]=1;
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout<<cur<<" ";
        for (int i=0; i<=n; i++) {
            if (!visit[i] && map[cur][i] == 1) {
                q.push(i);
                visit[i]=1;
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    init();
    dfs(v);
    memset(visit, 0, sizeof(visit));
    cout<<"\n";
    bfs(v);
    return 0;
}
 
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[SWEA 5162] 두가지 빵의 딜레마  (0) 2019.07.23
[BOJ 7576] 토마토  (0) 2019.07.05
[BOJ 1120]문자열  (0) 2019.07.03
[BOJ 5585] 거스름돈  (0) 2019.07.03
[BOJ 4948] 베르트랑 공준  (0) 2019.07.03
반응형

문제출처

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


처음에는 x문자열과 y문자열을 최대한 맞춰가면서 풀이해야 한다고 생각해서 많이 어려움을 느꼈다.

하지만 결국 앞이던 뒤던 y문자열과 비슷한 최적의 경우를 찾는 것이기 때문에 구현 대상에서 제외하고

x문자열과 y문자열의 차이값을 찾아가면서 구현했다.


예를 들어 설명하면 다음과 같다.

x가 adaabc

y가 aababbc 인경우를 생각해보면 문자열의 길이 차이는 1만큼 난다.


이때, y[0]부터 y[5]까지와 x를 비교해서 차이값, y[1]부터 y[6]까지와 x를 비교해서 차이값의 최솟값을 출력해주면 되는 문제이다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <string>
#define MAX 987654321
using namespace std;
int min(int a, int b) {
    return a>=b ? b : a;
}
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string x,y;
    int ans=MAX;
    cin>>x>>y;
    for (int i=0; i<= y.size() - x.size(); i++) {
        int cnt = 0;
        int yIdx=i;
        for (int j=0; j < x.size(); j++, yIdx++) {
            if (x[j] == y[yIdx]) continue;
            cnt++;
        }
        ans = min(ans, cnt);
    }
    cout<<ans;
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 7576] 토마토  (0) 2019.07.05
[BOJ 1206] DFS와 BFS  (0) 2019.07.05
[BOJ 5585] 거스름돈  (0) 2019.07.03
[BOJ 4948] 베르트랑 공준  (0) 2019.07.03
[BOJ 10872] 팩토리얼  (0) 2019.07.03
반응형

문제 출처

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


소스코드


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;
// 단순 반복문 문제
// greedy algorithm
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int coins[] = {500, 100, 50, 10, 5, 1};
    int nCost, ans=0;
    cin>>nCost;
    int nRemainder = 1000 - nCost;
    for (int i=0; i<6; i++) {
        while (nRemainder - coins[i] >= 0) {
            nRemainder -= coins[i];
            ans++;
            if (nRemainder == 0) {
                break;
            }
        }
    }
    cout<<ans;
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1206] DFS와 BFS  (0) 2019.07.05
[BOJ 1120]문자열  (0) 2019.07.03
[BOJ 4948] 베르트랑 공준  (0) 2019.07.03
[BOJ 10872] 팩토리얼  (0) 2019.07.03
[프로그래머스 12936] 줄 서는 방법  (0) 2019.04.23
반응형

문제출처

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


소스코드

 반복문을 돌때마다 소수를 구하는것은 비효율적이라 생각하여 먼저 에라토스테네스체를 이용하여 범위안의 소수를 모두 구하고 반복문에서는 소수인 것만 판별하여 소수의 갯수를 출력.


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.h>
#define MAX 246913
using namespace std;
 
/**
* n <= 123456 까지의 자연수 이므로 123456 * 2까지의 소수를 에라토스테네스체로 
* 먼저 구해 저장하고 while문을 돌면서 0이 나올때까지 그 값을 사용하는 방식으로 풀이. 
*/
bool isPrime[MAX];
 
void eratosthenes() {
    memset(isPrime, 1, sizeof(bool) * MAX);
    for (int i=2; i<=MAX; i++) {
        if (isPrime[i]) {
            for (int j=i*2; j<=MAX; j+=i) {
                isPrime[j] = 0;
            }
        }
    }
} 
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    eratosthenes();
    while(true) {
        int ans=0;
        cin>>n;
        if (n==0) {
            break;
        }
        for (int i=n+1; i<=2*n; i++) {
            if (isPrime[i]) {
                ans++;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1120]문자열  (0) 2019.07.03
[BOJ 5585] 거스름돈  (0) 2019.07.03
[BOJ 10872] 팩토리얼  (0) 2019.07.03
[프로그래머스 12936] 줄 서는 방법  (0) 2019.04.23
[프로그래머스 42840] 모의고사(완전탐색)  (0) 2019.04.23
반응형

문제출처

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


소스코드


첫번째 바로 푼 방법이데 재귀를 이용하여 풀었는데 당연히 시간초과가 났다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int fac(int n) {
    if (n==1) {
        return 1;
    }
    return n*fac(n-1);    
}
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    cout<<fac(n);
    return 0;
}
cs


이후 일반적인 반복문으로 풀이하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
 
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, ans=1;
    cin>>n;
    for (int i=1; i<=n; i++) {
        ans *= i;
    }
    cout<<ans;
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 5585] 거스름돈  (0) 2019.07.03
[BOJ 4948] 베르트랑 공준  (0) 2019.07.03
[프로그래머스 12936] 줄 서는 방법  (0) 2019.04.23
[프로그래머스 42840] 모의고사(완전탐색)  (0) 2019.04.23
[BOJ 1655] 가운데를 말해요  (0) 2019.04.16
반응형

문제출처

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



소스코드


효율성 - 시간초과

(next_permutation은 모든 순열을 다 보면서 세기때문에 시간복잡도가 O(n!)이다....


1
2
3
4
5
6
7
8
9
10
11
12
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> solution(int n, long long k) {
    vector<int> answer(n, 0);
    for(int i=0; i<n; i++) answer[i] = i+1;
    for(int i=0; i<k-1; i++) next_permutation(answer.begin(), answer.end());
  
    return answer;
}
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
#include <vector>
using namespace std;
 
long long makeFactorial(long long n) {
    long long ret=1;
    for(long long i=1; i<=n; i++) ret*=i;
    return ret;
}
 
vector<int> solution(int n, long long k) {
    vector<int> answer;
    vector<int> v(n,0);
    for(int i=0; i<n; i++) v[i] = i+1;
    
    int num=n;
    int quotient;
    long long remain;
    long long fac;
    while(num>0) {
        num--;
        fac=makeFactorial(num);
        remain = k % fac;
        quotient = (int)(k / fac);
        
        if(remain==0) {
            quotient--;
            answer.push_back(v[quotient]);
            v.erase(v.begin()+quotient);
            break;
        }
        
        answer.push_back(v[quotient]);
        v.erase(v.begin()+quotient);
        k=remain;
    }
    
    for(int i=v.size()-1; i>=0; i--) {
        answer.push_back(v[i]);
        v.erase(v.begin()+i);
    }
    
    return answer;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 4948] 베르트랑 공준  (0) 2019.07.03
[BOJ 10872] 팩토리얼  (0) 2019.07.03
[프로그래머스 42840] 모의고사(완전탐색)  (0) 2019.04.23
[BOJ 1655] 가운데를 말해요  (0) 2019.04.16
[BOJ 1157] 단어공부  (0) 2019.04.15
반응형

문제출처

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


문제풀이

배열을 이용해 수포자가 찍는 방식을 입력하고 mod연산을 통해 정답갯수를 알아내는 문제


소스코드


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
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> supoja1={1,2,3,4,5}; // 5
    vector<int> supoja2={2,1,2,3,2,4,2,5}; // 8
    vector<int> supoja3={3,3,1,1,2,2,4,4,5,5}; // 10
 
    int cnt1=0, cnt2=0, cnt3=0;
    int idx1=0, idx2=0, idx3=0;
 
    for(int i=0; i<answers.size(); i++) {
        idx1=i%5, idx2=i%8, idx3=i%10;
        (answers[i] == supoja1[idx1]) ? ++cnt1 : cnt1;
        (answers[i] == supoja2[idx2]) ? ++cnt2 : cnt2;
        (answers[i] == supoja3[idx3]) ? ++cnt3 : cnt3;
    }
 
    int maxCnt = max(cnt1, max(cnt2, cnt3));
    if(maxCnt == cnt1) answer.push_back(1);
    if(maxCnt == cnt2) answer.push_back(2);
    if(maxCnt == cnt3) answer.push_back(3);
 
    return answer;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 10872] 팩토리얼  (0) 2019.07.03
[프로그래머스 12936] 줄 서는 방법  (0) 2019.04.23
[BOJ 1655] 가운데를 말해요  (0) 2019.04.16
[BOJ 1157] 단어공부  (0) 2019.04.15
[BOJ 2675] 문자열 반복  (0) 2019.04.15
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
8
9
10
11
/**
 * priority_queue<자료형, 구현체(container), 비교 연산자(compare 함수)>로 정의
 * priority_queue<int, vector<int>, greater<int> > pq;
 * 자료형은 int형이고 값의 저장방식은 vector<int>이며 최소값을 먼저 내놓는다.
 * greater가 최소값을 내뱉고 less가 최대값을 내뱉음
 *
 * 중간값 구하기 알고리즘
 * 최대 힙의 크기 = 최소힙의 크기  or  최소힙의 크기 + 1
 * 최대 힙의 root(최대값) <= 최소힙의 root(최소값)
 * 위 2가지 규칙이 맞지 않는다면 최대힙, 최소힙의 top을 swap한다.
 */
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
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    priority_queue<int, vector<int>, less<int> > max_heap;
    priority_queue<int, vector<int>, greater<int> > min_heap;
 
    int n, num;
    cin>>n;
    while(n--) {
        cin>>num;
        if(max_heap.empty() && min_heap.empty()) max_heap.push(num);
        else if(max_heap.size() == min_heap.size()) max_heap.push(num);
        else min_heap.push(num);
 
        if(!max_heap.empty() && !min_heap.empty() && max_heap.top() > min_heap.top()) {
            int tmp=max_heap.top();
            max_heap.pop();
            max_heap.push(min_heap.top());
            min_heap.pop();
            min_heap.push(tmp);
        }
        cout<<max_heap.top()<<"\n";
    }
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 12936] 줄 서는 방법  (0) 2019.04.23
[프로그래머스 42840] 모의고사(완전탐색)  (0) 2019.04.23
[BOJ 1157] 단어공부  (0) 2019.04.15
[BOJ 2675] 문자열 반복  (0) 2019.04.15
[BOJ 13458] 시험감독  (0) 2019.04.15
반응형

문제출처

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


문제풀이

문자열을 입력받고 알파벳개수(26)개의 int형 배열을 선언한 뒤 반복문을 통해 갯수를 세어주면 되는

간단한 문제입니다. ASCII 값을 알고 있는지 확인하는 문제


소스코드

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 <cstdio>
#include <cstring>
int main() {
    char s[1000001];
    int cnt[26];
    scanf("%s", &s);
    memset(cnt, 0, sizeof(cnt));
    int len = strlen(s);
    for(int i=0; i<len; i++) {
        if(s[i] >= 'a' && s[i] <= 'z') s[i]-='a'-'A';
        cnt[s[i]-'A']++;
    }
 
    int max=0, idx=-1;
    for(int i=0; i<len; i++) {
        if(max<cnt[s[i]-'A']) {
            max=cnt[s[i]-'A'];
            idx=i;
        }
    }
 
    int duplicateCnt=0;
    for(int i=0; i<26; i++) {
        if(max==cnt[i]) duplicateCnt++;
    }
    if(duplicateCnt==1) printf("%c\n", s[idx]);
    else printf("?\n");
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 42840] 모의고사(완전탐색)  (0) 2019.04.23
[BOJ 1655] 가운데를 말해요  (0) 2019.04.16
[BOJ 2675] 문자열 반복  (0) 2019.04.15
[BOJ 13458] 시험감독  (0) 2019.04.15
[BOJ 1057] 토너먼트  (0) 2019.04.15

+ Recent posts

티스토리툴바