[BOJ] C++연습하기! 백준 문제집 (by jihwan0319)

C++ 기본 문법 공부할 겸 백준 문제들을 C++로 풀어보려고 한다.

 

여태 백준은 파이썬, C로만 풀었는데 학교에서 자꾸 C++을 써서.. 강제 공부

 

 

처음 알고리즘 공부할 때나 코테 입문할 때는 파이썬이 압도적으로 쉽겠지만..

런타임 이슈도 그렇고 자료도 더 풍부해서 시간날 때 C++로도 공부해둬야 하겠다 싶어서..

하게 됐다는 이야기.

 

 

아무튼!

그래서 백준 사이트에서 jihwan0319님이 편집한

<C++연습하기!> 문제집을 C++로 풀어보았다.

 

https://www.acmicpc.net/workbook/view/10119

문제집: c++연습하기! (jihwan0319)

이 문제집에는 1000, 1001, 1008, 10998, 1026, 2659, 2693, 15970, 15975, 20186번 문제가 수록되어 있다.

 

 

---

 

1000. A+B

 

첫째 줄에 A와 B가 주어진다. (0 < A, B < 10)

=> 첫째 줄에 A+B를 출력한다.

 

기본적인 입출력을 위해 <iostream> 헤더 파일을 include 해야 한다.
C++에서는 같은 이름을 가진 함수라도 namespace가 다르면 다른 함수가 된다.

따라서 함수를 쓸 때 (namespace)::(function)꼴로 쓰던지, 아니면 main 함수 밖에 using namespace (namespace);를 해주어 특정 namespace에서만 함수를 쓰는 것으로 애초에 정의해버릴 수도 있다. 그러나 이는 해당 namespace에 이름이 겹치는 함수를 만들 경우 오류를 일으키므로 권장되지 않는 방식이다.

(지금 이런 쉬운 문제들을 풀 때는 상관없다.)

 

입력을 위해 std의 cin을 쓴다.

int user_input;
std::cin >> user_input;

이렇게 사용하면 입력받은 값을 user_input이라는 정수형 데이터값으로 저장하게 된다.
출력을 위해서는 std의 cout를 쓴다.

std::cout << /* 출력할 것 */ << /* 출력할 것 */ << ... << /* 출력할 것 */;

이렇게 하면 왼쪽에서부터 출력된다.

 

따라서 1000번 문제는 다음과 같이 풀 수 있다.

#include <iostream>

int main() {
    int A, B;
    std::cin >> A >> B;
    std::cout << A + B;
    return 0;
}

 

세상 간단한 코드지만 아무튼 python에 비해 짧은 런타임을 확인할 수 있다. 1ms도 안 걸렸군!

 

---

 

1001. A-B

 

1000번을 그냥 뺄셈으로 수정하면 된다.

 

 

---

1008. A/B

 

첫째 줄에 A/B를 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-9 이하이면 정답이다.

 

[틀린 답]

#include <iostream>

int main() {
    double A;
    double B;
    std::cin >> A >> B;
    std::cout << A / B;
    return 0;
}

이 코드를 돌려서 1 / 3 연산을 수행해보면 0.333333을 출력한다.

자료형을 double로 설정해주었음에도, 기본적으로 std::cout의 기본 정밀도가 6이라 소숫점 6번째 자리까지만 출력된다.ㄴ

 

따라서 다음과 같이 출력 소숫점 자리수를 설정해주어야 한다.

 

 

[맞는 답]

#include <iostream>

int main() {
    double A;
    double B;
    std::cin >> A >> B;
    std::cout << std::fixed;
    std::cout.precision(9);
    std::cout << A / B;
    return 0;
}

cout.precision(n)은 소수부와 정수부를 합해 n자리를 출력하겠다는 의미가 된다.

우리는 '소수부'에 대해 9자리 제한을 걸어야 하므로 앞에 std::cout << std::fixed를 추가해주었다.

 

---

 

10998. AxB

 

정수x정수 답은 무조건 정수이므로 앞선 덧셈, 뺄셈 문제처럼 풀어주면 된다.

 

#include <iostream>

int main() {
    int A, B;
    std::cin >> A >> B;
    std::cout << A * B;
    return 0;
}

 

---

 

1026. 보물

 

1xN 크기의 배열 두 줄(A, B)을 입력 받아서, A는 내림차순 정렬, B는 오름차순 정렬한 뒤 요소끼리 곱한 값의 sum을 구하는 문제다. 살짝 까다로운 부분은 'B는 재배열하지 않고' 해야한다는 거다. 즉 B의 오름차순에 배치에 맞게 A를 내림차순이 되도록 정렬한 뒤 곱해야한다는 거다.

이 문제는 사실 그냥 B를 재배열해버려도 정답처리 된다고 한다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, x;
    cin >> N;
    int s = 0;
    vector<int> A, B, C;
    for (int i=0; i<N; i++) {
        cin >> x;
        A.push_back(x);
    }
    for (int i=0; i<N; i++) {
        cin >> x;
        B.push_back(x);
    }
    C = B;
    sort(A.begin(),A.end());
    sort(C.rbegin(),C.rend());
    for (int i=0; i<N; i++) {
        s = s + A[i]*C[i];
    }
    cout << s;
}

 

cin은 공백이 있으면 공백 앞까지만 값을 입력받는다.

따라서 벡터 입력시 정수 사이에 공백(스페이스)을 입력하는 순간 해당 정수가 벡터로 삽입되고 for문이 돌아가 다시 cin으로 입력받을 차례가 온다. 이때 앞서 입력한 공백은 버퍼에 저장되지 않는다.

 

아무튼 그냥 B 벡터를 C에 복사해버리고 C를 내림차순 정렬해 A의 오름차순 정렬과 요소끼리 곱해버렸다.

 

 

 

이 문제를 풀면서 벡터 개념을 다시 정립하고자 C++에서 리스트와 벡터의 차이를 아래 포스트에 정리했다.

https://yoomimi.tistory.com/entry/C-%EB%A6%AC%EC%8A%A4%ED%8A%B8list%EC%99%80-%EB%B2%A1%ED%84%B0vector%EC%9D%98-%EC%B0%A8%EC%9D%B4

[C++] 리스트(list)와 벡터(vector)의 차이

 

---

 

2659. 십자카드

 

 

일단 clock 벡터에 시계수를 작은 수 부터 죄다 넣고,

입력 받은 수를 시계수가 되도록 정렬한 후

그 수가 clock 벡터에서 몇번째에 있는지 찾아야 하겠다고 생각했다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int a, b, c, d, m;
    vector<int> v, clock;
    cin >> a >> b >> c >> d;
    v.push_back(1000*a + 100*b + 10*c +d);
    v.push_back(1000*b + 100*c + 10*d +a);
    v.push_back(1000*c + 100*d + 10*a +b);
    v.push_back(1000*d + 100*a + 10*b +c);
    m = *min_element(v.begin(), v.end()); //입력받은 수의 시계수 값
    for (int i=0; i<9; i++){
        for (int j=0; j<9; j++){
            for (int k=0; k<9; k++){
                for (int l=0; l<9; l++){
                    if ((i<=j)&(i<=k)&(i<=l)&(((i+1)*10+j+1)<=((k+1)*10+l+1))&((l+1 + (k+1)*10 + (j+1)*100 + (i+1)*1000)<=(k+1 + (j+1)*10 + (i+1)*100 + (l+1)*1000))){
                        clock.push_back(l+1 + (k+1)*10 + (j+1)*100 + (i+1)*1000);
                    }
                }
            }
        }
    }
    cout << find(clock.begin(), clock.end(), m) - clock.begin() + 1;
}

일단 입력받은 수를 시계수로 만드는 건 그냥 abcd, bcda, cdab, dabc 네 가지를 전부 벡터에 넣어보고

min 값을 뽑았다. 그렇게 일단 입력받은 수의 시계수 값을 m에 저장한다.

 

그리고 시계수 벡터 clock은,

위 방식대로 수 하나씩  abcd, bcda, cdab, dabc를 해보고 시계수만 뽑아내볼까하다가

다른 조건을 찾아서 그냥 모든 시계수를 포함하는 벡터를 만들어보고자 했다.

하나 찾으려는 건데 전체 시계수 벡터를 만드니까 런타임도 더 길게 걸리긴 하겠다..

 

시계수가 되려면 결국 네자리수 ijkl (편의상 10^n 빼고 씀)에 대해

1) i가 i, j , k, l 중 가장 작은 수여야 하고

2) ij <= kl 이어야 하고

3) ijkl <= lijk 이어야 한다.

 

조건 생각해보는데 30분은 걸린 것 같다. ((머쓱타드))

 

아무튼 그래서 네자리수의 각 자리가 1부터 9까지 이루어져있어야 하므로 자리수마다 반복문을 썼고,

시계수이기 위한 조건은 그냥 if문 안에 손수 적었다.

그렇게 clock 벡터에 넣어주면 어차피 반복문이 작은수부터 돌아가니 오름차순 정렬된다.

 

인덱스는 0부터 시작이므로 +1을 해서 몇번째 시계수인지 찾게 했다.

 

---

 

15970. N번째 큰 수

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, x;
    cin >> N;
    for (int i=0; i<N; i++){
        vector<int> v;
        for (int j=0; j<10; j++){
            cin >> x;
            v.push_back(x);
            }
        sort(v.rbegin(),v.rend());
        cout << v[2] << endl;
    }
}

 

그냥 벡터에 입력받고 내림차순 정렬한 뒤 index 2 값에 해당하는 요소를 출력하면 된다.

다만 처음 할 때 마지막에 endl을 안붙였다가 오류가 났었다. 주의!

 

---

 

15970. 화살표 그리기

 

 

2차원 벡터로 N개 점들의 (위치, 색깔)을 입력받고,

위치가 i인 한 점에 대해 색깔이 같은 점 j들과의 거리를 check에 저장한 다음,

check의 최솟값을 sum에 저장해주는 식으로 코드를 짰다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, x;
    cin >> N;
    int sum=0;
    vector<vector<int>> v;
    for (int i=0; i<N; i++){
        vector<int> v2;
        cin >> x;
        v2.push_back(x);
        cin >> x;
        v2.push_back(x);
        v.push_back(v2);
    }
    for (int i=0; i<N; i++){
        vector<int> check;
        for (int j=0; j<N; j++){
            if ((i!=j)&(v[i][1]==v[j][1])){
                check.push_back(abs(v[i][0]-v[j][0]));
            }
        }
        if (!check.empty()){sum = sum + *min_element(check.begin(),check.end());}
    }
    cout << sum;
}

 

i에 대해 j점들을 체크할 때 자기 자신은 체크하지 않도록 i!=j 라는 조건을 걸어주는 것 정도가 핵심이라 할 수 있겠다.

처음에 이거 빼먹었다가 sum이 0나와서 오잉? 했다..ㅎㅎ

 

 

---

 

15970. 화살표 그리기

 

 

위의 문제와 차이점이 있다면..

점이 10만개가 있을 때도 제한 시간 1초 안에 동작해야 한다.

위의 문제에서 쓴 코드를 그대로 넣었더니 21점을 받았다.

 

이 문제의 코드는 다음과 같이 작성했다.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    iostream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N;
    cin >> N;
    long long int sum = 0;
    unordered_map<int, vector<int>> v;

    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        v[y].push_back(x);
    }

    for (auto& entry : v) {
        vector<int>& xValues = entry.second;
        sort(xValues.begin(), xValues.end());
        if (xValues.size() > 1) {
            for (vector<int>::size_type i = 1; i < xValues.size() - 1; i++) {sum += min(xValues[i] - xValues[i - 1], xValues[i + 1] - xValues[i]);}
            sum += xValues[1] - xValues[0] + xValues[xValues.size() - 1] - xValues[xValues.size() - 2];
        }
    }

    cout << sum;
}

 

sum을 꼭 long long int로 설정하자.. 그냥 int로 했다가 계속 21점 나와서 애 먹었다ㅠㅠ

 

우선 unordered_map<int, vector<int>>로 v를 선언했다. 그리고 x, y를 입력 받아 v[y].push_back(x)로 v에 값을 넣어주었는데, 이는 int형 y 좌표 값을 키로, 해당 y 좌표에 대응되는 x 좌표들을 vector<int> 형태로 저장하는 자료구조다.

 

따라서 색깔로 위치 값들을 저장하는 것이다.

 

for (auto& entry : yCoordinates)은 C++11 이후부터 지원하는 range-based for loop 라고 한다.

v의 각 요소(entry)들에 대해 반복하겠다는 뜻이다.
auto 키워드를 사용하여 컴파일러가 변수의 타입을 추론하게 하고, &는 참조를 의미한다는데, 안써주면 오류가 난다.

 

vector<int>& xValues = entry.second;은 entry.second에 해당하는 vector<int>를 xValues라는 이름의 참조로 접근하는 것이다. 이렇게 하면 각 색깔마다 for문이 반복되고, for문 안에서 해당 색깔에 해당하는 위치 값들만을 가지고 문제를 해결할 수 있다.

 

위치 값들을 정렬한 후 좌/우와 뺀 값 중 min을 sum에 합하게 했다.

[i], [i-1], [i+1]을 가지고 for문을 돌리기 위해 맨 앞과 맨 끝의 값들(xValues[0], xValues[xValues.size()-1])은 따로 계산했다.

 

 

---

 

20186. 수 고르기

 

 

 처음에 문제를 읽고 이게 무슨 소리야? 싶었는데, 이해가 되고 나니

그냥 제일 큰 수 K개 더한 다음 0+1+2+..+(K-1)를 빼면 되는 문제였다.

 

생각한대로 코드를 작성했다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    iostream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, K, x;
    cin >> N >> K;
    vector<int> v;
    for (int i=0; i<N; i++) {
        cin >> x;
        v.push_back(x);
    }
    sort(v.rbegin(), v.rend());
    int sum = 0;
    for (int i=0; i<K; i++) {sum += v[i] - i;}
    cout << sum;
}

 

더하고 빼는 것도 v[i] - i로 한번에 처리해주니 간단했다.

 

끝!!

 

다했다!!