어려운 문제는 아니지만


auto 를 처음 써봤다. 신기하군


C++ 11 버전부터 사용 가능한 기능이라네요.


나머지 코드는 그렇게 어렵지 않습니다.


vector와 sort()




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 <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main(){
    int n, x, y;
    vector<pair<int, int>> v;
    
    scanf("%d", &n);
    while(n--){
        scanf("%d %d", &x, &y);
        v.push_back(make_pair(x, y));
    }
    sort(v.begin(), v.end());
    
    for(auto lt : v){
        printf("%d %d\n", lt.first, lt.second);
    }
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[4355번] 서로소 - 오일러 파이 함수[C++]  (0) 2017.08.31
[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27

http://min92.tistory.com/70


오일러 파이 함수를 통해서 풀면

파이는 1~n까지의 수 중에서 n과 서로소인 수의 갯수이다.




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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <iostream>
#include <math.h>
 
using namespace std;
 
int prime[50];
int primeCopy[50];
 
int primeCopy2[50];
int primeCopyPower[50];
 
void function(int firstInputNumber)
{
    int i, primeIndex, inputNumber;
    int x;
    primeIndex = 0;
    inputNumber = firstInputNumber;
    
    //소인수분해
    for(i = 2; i < inputNumber; i++)
    {
        if(inputNumber % i == 0)
        {
            prime[primeIndex] = i;
            primeIndex++;
            inputNumber /= i;
            i = 1;
        }
    }
    
    x = inputNumber;
    
    i = 0;
    
    while(firstInputNumber != x)
    {
        x = x * prime[i];
        i++;
    }
    prime[i] = inputNumber;
    
    //primeCopy에는 소인수분해해서 최소공배수들이 모임
    for(int j = 0; j <= i; j++){
        primeCopy[j] = prime[j];
    }
    
    //primeCopy2에는 소인수분해해서 최소공배수가 중복되지 않게 넣음
    //primeCopyPower에는 각자의 최소공배수가 몇 개씩 있는지를 넣음
    int k = 0;
    for(int j = 0; primeCopy[j] != 0; j++){
        if(j != 0){
            if(primeCopy[j] == primeCopy[j-1]){
                primeCopyPower[k]++;
            }else{
                k++;
                primeCopyPower[k]++;
                primeCopy2[k] = primeCopy[j];
            }
        }
        else{
            primeCopyPower[k]++;
            primeCopy2[k] = primeCopy[j];
        }
    }
}
 
int main(){
    int N;
    int result = 1;
    
    while(1){
        cin >> N;
        if(N == 0) break;
        
        //initialization
        for(int k = 0; k < 50; k++){
            prime[k] = 0;
            primeCopy[k] = 0;
            primeCopy2[k] = 0;
            primeCopyPower[k] = 0;
            result = 1;
        }
        
        function(N);
        
        //오일러의 파이 함수 정리
        for(int j = 0; primeCopy2[j] != 0; j++){
            result *= pow(primeCopy2[j], primeCopyPower[j]) - pow(primeCopy2[j], primeCopyPower[j]-1);
        }
        printf("%d\n", result);
    }
    
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11650번] 좌표 정렬하기 - sort [C++]  (0) 2017.09.19
[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27

https://www.acmicpc.net/blog/view/27


위 자료를 참고하면 CCW 알고리즘에 대해 자세히 설명되어 있다.


간단히 설명하면 CCW 알고리즘은 점 3개의 방향이 시계방향인지 반시계방향인지 일직선인지를 판단하는 알고리즘이다.


그래서 CCW는 세 점으로 이루어진 삼각형의 면적을 통해서 판단한다.


넓이가 0보다 크면 반시계방향,

넓이가 0보다 작으면 시계방향,

넓이가 0이면 일직선


방법은 첫번째 점부터 (x1, y1)으로 두고 벡터의 외적을 통해 넓이를 구한다.


필자는 빨리 풀려고 직관적으로 풀었으나 point라는 자료형을 사용하면 좀더 깔끔해진다.





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
#include <iostream>
 
using namespace std;
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3){
    int temp = x1*y2 + x2*y3 + x3*y1;
    temp = temp - y1*x2 - y2*x3 - y3*x1;
    
    if(temp > 0){
        return 1;
    }else if(temp < 0){
        return -1;
    }else {
        return 0;
    }
}
 
int main(){
    int x1,x2,x3,y1,y2,y3;
    
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    
    cout << ccw(x1, y1, x2, y2, x3, y3) << endl;
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11650번] 좌표 정렬하기 - sort [C++]  (0) 2017.09.19
[4355번] 서로소 - 오일러 파이 함수[C++]  (0) 2017.08.31
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27

이 문제는 동적계획법을 이용한 기본적인 문제로 처음 동적계획법을 접한다면 쉽지 않을 수 있다.

동적계획법이란 문제를 서브 문제로 나누어서 그것을 결합하여 결론에 도달하는 방법이다.

연산횟수를 줄이는 데 목표를 가지고 있다.

이 문제는 Bottom-up방법(동적계획법)을 이용하였다.

다른 방법도 무수히 존재하는 문제이다.

예외를 찾기가 힘든데 만약 어려움을 겪고 있다면

1793을 넣어보자.ㅎㅎ


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 <algorithm>
 
using namespace std;
 
int output = 0;
int dp[1000001];
 
int main(){
    int N;
    cin >> N;
    
    dp[1] = 0;
    for(int i = 2; i <= N; i++){
        dp[i] = dp[i-1] + 1;
        if(i%2 == 0){
            dp[i] = min(dp[i/2]+1, dp[i-1]+1);
        }
        if(i%3 == 0){
            dp[i] = min(dp[i/3]+1, dp[i-1]+1);
        }
    }
           
    cout << dp[N];
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[4355번] 서로소 - 오일러 파이 함수[C++]  (0) 2017.08.31
[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27

이 문제는 분할정복법으로 푸는 문제로 분할정복법이란 큰 문제를 작은 문제로 나누어 처리하는 방식(Top-down)으로

보통 재귀를 이용한 방법이 일반적이다.

이 문제를 좀 오래동안 풀었는데 그 이유는 for문에 j를 써야하는데 i라고 써서 눈이 나쁜 필자는 이걸 찾는데 일주일이 걸렸다고 한다...
이 문제와 비슷한 문제로는 쿼드트리가 있다.



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
#include <iostream>
 
using namespace std;
 
int output[3];  // -1 0 1
int arr[2187][2187];
 
void paper(int x, int y, int N){
    int first = arr[x][y];
    bool flag = true;
    
    for(int i = x; i < x + N; i++){
        for(int j = y; j < y + N; j++){
            if(arr[i][j] != first){
                flag = false;
                break;
            }
        }
    }
    
    if(flag) {
        output[first + 1]++;
    }
    else {
        for(int a = x; a < x + N; a += N/3 ){
            for(int b = y; b < y + N; b += N/3){
                paper(a, b, N/3);
            }
        }
    }
}
 
int main(){
    int N;
    
    cin >> N;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> arr[i][j];
        }
    }
    
    paper(0, 0, N);
    
    for(int i = 0; i < 3; i++){
        cout << output[i] << endl;
    }
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15

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


이 문제는 일단 한수라는 개념을 알아야한다. 한수란 각 자리수가 등차수열이 되어야 한다. 예를 들면, 234, 357 등으로 각 자리수가 등차수열만 만족시키면 된다. 여기서 문제는 100이하는 어떻게 해야하는가인데, 결론은 100이하의 수는 무조건 한수이다. 예를 들면, 25, 36, 29 등 무조건 한수의 조건을 만족시킨다. 이 개념만 알고 시작하면 어려운 문제는 아니다. 일단 직관적으로 풀었다. 더 좋은 방법도 충분히 많이 있을 것이라 생각이 드는 문제이다.


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 <iostream>
 
using namespace std;
 
int han(int input, int count) {
    if (input < 100)
        return count += input;
    else if (input == 1000)
        han(input - 1, count);
    else {
        if ((input / 100 - (input % 100) / 10) == (input % 100) / 10 - (input % 10) / 1)
            count++;
        han(input - 1, count);
    }
}
 
int main() {
    int N;
    int count = 0;
    cin >> N;
 
    cout << han(N, count);
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15

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


간단히 정렬하는 문제로 좀 특이한 점이 있다면 단어 길이 sorting를 신경써야한다는 점이다.


처음 든 생각은 length 와 string을 구조체에 넣고 계산할까 하다가


string 타입과 sort함수를 사용하면 코드가 간결해질 것 같은 느낌적인 느낌이 들어서 이들을 이용하였다.


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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
bool compare(const string& a, const string& b){
    if(a.length() == b.length())
        return (a < b);
    else
        return a.length() < b.length();
}
 
int main() {
    int N;
    string input[20001];
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
        cin >> input[i];
    
    sort(input, input + N, compare);
 
    for(int i = 0; i < N; i++){
        if(input[i] == input[i-1] && i != 0)
            continue;
        cout << input[i] << endl;
    }
    
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13

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


문제는 간단하고 어렵지는 않지만 fgets()와 EOF에 대해 알 수 있는 문제이다.

배열의 크기를 101로 잡게 되면 틀린다!

getchar()를 이용해서 하나씩 받아와도 무관하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
 
using namespace std;
 
char input[102];
int main() {
    while(fgets(input, 102, stdin)) {
        int small = 0, capital = 0, num = 0, space = 0;
        for (int i = 0; input[i]; i++) {
            if ('a' <= input[i] && input[i] <= 'z') //small letter
                small++;
            else if ('A' <= input[i] && input[i] <= 'Z') //capital letter
                capital++;
            else if ('0' <= input[i] && input[i] <= '9') //number
                num++;
            else if (input[i] == ' ') //space
                space++;
        }
        printf("%d %d %d %d\n", small, capital, num, space);
    }
    return 0;
}
cs



<Amazing Code From https://www.acmicpc.net/source/4430326>


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
int a,A,n,s;
char c;
int main() {
    while(~(c=getchar())) {
        if(c>='a' && c<='z') a++;
        if(c>='A' && c<='Z') A++;
        if(c>='0' && c<='9') n++;
        if(c==' ') s++;
        if(c=='\n') printf("%d %d %d %d\n", a,A,n,s), a=A=n=s=0;
    }
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13

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


어려운 문제는 아니고 아이디어만 있다면 간단하게 해결할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
 
using namespace std;
int alpha[27];
int main() {
    string input;
    cin >> input;
    for (int i = 0; i < 26; i++)
        alpha[i] = -1;
    for (int i = 0; i < input.length(); i++)
        if(alpha[input[i] - 97] == -1)
            alpha[input[i] - 97] = i;
    for (int j = 0; j < 26; j++)
        cout << alpha[j] << " ";
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13

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


이 문제는 간단한 문제로 배열을 생각하지 못한다면 노가다로 빠질 위험이 있다.(알파벳의 개수는 26개다.)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
 
using namespace std;
 
int alpha[37];
int main() {
    string input;
    cin >> input;
    for (int i = 0; i < input.length(); i++)
        alpha[input[i] - 97]++;
    for (int j = 0; j < 26; j++)
        cout << alpha[j] << " ";
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06

+ Recent posts

티스토리툴바