문제 간단 정리

정렬문제 아마도 내장함수를 사용하지 않는다면 n logN의 시간복잡도를 갖는 정렬로 풀어야한다.

문제 해결 방법

sort 내장함수 사용 ><

전체 코드

#include<vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> vec;
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        vec.push_back(input);
    }
    sort(vec.begin(), vec.end());

    for (int a : vec) {
        cout << a << "\n";
    }
}

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

 

2003번: 수들의 합 2

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

문제 간단 정리

 

문제 해결 방법

https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-14246%EB%B2%88-K%EB%B3%B4%EB%8B%A4-%ED%81%B0-%EA%B5%AC%EA%B0%84-C 참고

전체 코드

#include<vector>
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll N, M;
    vector<ll> cnt;
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        ll input;
        cin >> input;
        cnt.push_back(input);

    }
    cnt.push_back(0); //인덱스 때문에 하나 추가



    ll count = 0;
    ll start = 0; ll end=0;
    ll sum = cnt[start];

    while (1) {

        if (sum > M) { //합이 클때

            sum -= cnt[start];

            if (start == end) {
                end++;
                sum += cnt[end];
            }
            start++;

        }
        else if (sum < M) { //합이 적을때

            end++;
            sum += cnt[end];
            
        }
        else if (sum == M) {
            count++;
            sum += cnt[++end];
        }
        if (end == N) break;

    }

    cout << count;
}

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

 

14246번: K보다 큰 구간

$n$개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 $[i,j]$ ($i≤j)$의 합이 $k$보다 큰 모든 쌍 $(i, j)$의 개수를 출력하시오.

www.acmicpc.net

문제 간단 정리

구간합으로도 될 것 같다. 하지만 투 포인터로 풀어보자 

만약 12345 이고 K가 5일때

현재 123을 합한상태라면 4 5 는 더할 필요 없이 +3만 해주면 된다. 

이를 유의해서 풀

문제 해결 방법

투 포인터를 이용해서 풀어보자..

인덱스를 조심해야된다

전체 코드

#include<vector>
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll N, M;
    vector<ll> cnt;
    cin >> N ;

    for (int i = 0; i < N; i++) {
        ll input;
        cin >> input;
        cnt.push_back(input);

    }
    cnt.push_back(0); //인덱스 때문에 하나 추가

    cin >> M;


    ll count = 0;
    ll start = 0; ll end=0;
    ll sum = cnt[start];

    while (1) {

        if (sum > M) { //합이 클때

            sum -= cnt[start];
            count += N - end;

            
            if (start == end) {
                end++;
                sum += cnt[end];
            }
            start++;

        }
        else if (sum <= M) { //합이 적을때

            end++;
            sum += cnt[end];
            
        }
        if (end == N) break;

    }

    cout << count;
}

 

문제 간단 정리

'' 생략

문제 해결 방법

이 문제는 섬과 섬 사이의 연결 관계를 파악해야 하는 그래프 관련 문제입니다. 이를 효율적으로 파악하기 위해 Union-Find 알고리즘을 사용합니다.

Union-Find는 그래프의 연결 요소를 식별하고 관리하기 위한 알고리즘입니다. Union-Find 알고리즘에서 'union' 연산은 두 집합을 하나로 합치고, 'find' 연산은 특정 원소가 어떤 집합에 속하는지를 찾는 데 사용됩니다.

본 문제에서는 다리 하나가 무너져 서로 왕복할 수 없는 섬들이 생겼습니다. 이때 두 섬을 다시 다리로 이어서 모든 섬이 왕복 가능하도록 해야 합니다. 이를 위해 먼저 주어진 섬 간 연결 정보를 이용해 각 섬의 부모 노드 정보를 업데이트합니다. 이렇게 하면 어떤 섬이 어떤 섬과 연결되어 있는지를 빠르게 알 수 있습니다.

Union-Find 알고리즘을 적용한 코드는 다음과 같습니다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;
int n, m;
int parent[1000001];

int getParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin.tie(NULL);

    

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= N - 2; i++) {
        int a, b;
        cin >> a >> b;
        unionParent(a, b);
       
    }
    for (int i2 = 1; i2 <= N - 1; i2++) {
        int A = i2;
        for (int j = i2 + 1; j <= N; j++) {
            int B = j;
            A = getParent(A);
            B = getParent(B);
            if (A != B) {
                cout << A << " " << B;
                return 0;
            }

        }
    }
    

    return 0;

    
}

 

 

문제 간단 정리

구현문제이다

각 블럭들을 돌아가면서 조사하면 되는 간단한 구현문제지만

어떻게 구현하냐에 따라서 시간이 달라질것이다.

나는 그냥 모든 블럭들을 조회하는 무식한 방법으로 풀었다.

이렇게 풀면 오류도 많고 틀릴 가능성이 높으니

아마 각 블럭 모양을 만들고 회전시키는 방법이 가장 바람직하지 않을까 싶다

https://stack07142.tistory.com/299 예시

 

문제 해결 방법

#include<queue>
#include<deque>
#include <iostream>

using namespace std;

int main() {
    int arr[100][100];


    int count = 1;

    while (1) {
        int N; cin >> N;
        if (!N) break;
        //i 세로 j 가로

        int temp = 0;
        int max = -987654321;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> arr[i][j];
            }
        }

        // ㅡ
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - 3; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3];
                if (temp > max) max = temp;
            }
        }
        // ㅣ
        for (int i = 0; i < N - 3; i++) {
            for (int j = 0; j < N; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 3][j];
                if (temp > max) max = temp;
            }
        }

        //ㅓ
        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i + 1][j] + arr[i + 1][j + 1] + arr[i][j + 1] + arr[i + 2][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅗ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i + 1][j] + arr[i + 1][j + 1] + arr[i][j + 1] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }
        //ㅜ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅏ
        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅁ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1];
                if (temp > max) max = temp;
            }
        }
        //ㅁㅁ
        //  ㅁㅁ
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }

        //  ㅁ
        //ㅁㅁ
        //ㅁ

        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j+1] + arr[i + 1][j+1] + arr[i + 1][j] + arr[i +2][j];
                if (temp > max) max = temp;
            }
        }



        //ㅁㅁㅁ
        //    ㅁ

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }
        //  ㅁ
        //  ㅁ
        //ㅁㅁ

        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j+1] + arr[i + 2][j];
                if (temp > max) max = temp;
            }
        }

        //ㅁ
        //ㅁㅁㅁ

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 2; j++) {
                temp = 0;
                temp = arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
                if (temp > max) max = temp;
            }
        }

        //ㅁㅁ
        //ㅁ
        //ㅁ

        for (int i = 0; i < N - 2; i++) {
            for (int j = 0; j < N - 1; j++) {
                temp = 0;
                temp = arr[i][j + 1] + arr[i][j] + arr[i + 1][j] + arr[i + 2][j];
                if (temp > max) max = temp;
            }
        }

        cout << count << ". " << max << endl;

        count++;
    }
    


    
}

전체 코드

 

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

 

4920번: 테트리스 게임

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓

www.acmicpc.net

 

 

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

 

11687번: 팩토리얼 0의 개수

첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.

www.acmicpc.net

 

#문제 간단 정리

이하생략

 

#문제 해결 방법

끝의 0의 개수는 2*5의 개수로 정해지고,

2는 2의배수만큼 5는 5의 배수만큼 존재하기 때문에 2가 항상 5보다 많다

때문에 5의 개수만 세주면 0의 개수와 같다

 

이분탐색의 범위는 m*5! 이 무조건 m개의 5의개수보다 많은 5를 가지므로

right를 m*5로 설정해주면 된다.

 

또한 포함된 5의 개수는 5부터 5의제곱수들을 차례대로 나눈 몫을 구하면 5의 개수를 구하는

함수를 만들 수 있다.

 

#전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;


//5가 들어간 개수를 찾는 함수
int findFive(int a) {
    int count = 0;

    for (int i = 5; i <= a; i *= 5) {
        count += (a / i);
    }
    return count;
}

int main() {

    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    //0의 개수는 5의 개수와 동일
    //제곱이 나오는 경우는 숫자가 건너뛰어짐
    int input;
    cin >> input;

    int left = 1;
    int right = input*5;
    int target = input;
    int result = 0;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (findFive(mid) == target) {
            right = mid -1;
        }
        else if (findFive(mid) > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    
    if (findFive(left) == target) {
        cout << left;
    }
    else {
        cout << -1;
    }
    
    return 0;
}

<코드>

#define _CRT_SECURE_NO_WARNINGS 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;


int main() {

    int N, K;
    cin >> N >> K;
    int arr[2][7] = { { 0,0 },
                    {0,0,0,0,0,0,0} };

    int S, Y;
    for (int i = 0; i < N; i++) {
        cin >> S >> Y;

        arr[S][Y]++;

  
    }
    int cnt = 0;

    for (int j = 0; j <= 1; j++) {
        for (int k = 1; k <= 6; k++) {
            while (arr[j][k] > 0) {
                arr[j][k] -= K;
                cnt++;

            }
        }
    }

    cout << cnt;

    
    return 0;
}

 

 

 

성별, 학년별로 배열을 만들어줘서

각 배열 돌면서 방 인원수만큼 빼면서 카운트하면 최소 방 개수가 금방 나옵니다!

 

딱히 다른 조건 생각할게 없어서 쉬운문제였네요

'[백준] > C++' 카테고리의 다른 글

백준 4920번 테트리스 게임 [C++]  (0) 2023.07.19
백준 11687번 팩토리얼 0의 개수 [C++]  (0) 2023.07.08
백준 9012번 괄호 [C++]  (0) 2023.06.25
백준 10845번 큐 [C++]  (0) 2023.06.25
백준16396번 선 그리기 [C++]  (0) 2023.06.25

 

<코드>

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    //닫는거만 세주면 됩니다
    //여는 괄호에서 닫는 거 개수만큼 차감해주고 마이너스가 된다면 VPS가 아니죠
    int n;
    cin >> n;

    while (n--) {
        string input;
        cin >> input;
        int vpsCount = 0;
        bool minus = false;

        for (int i = 0; i < input.size(); i++) {

            if (input[i] == '(') {
                vpsCount++;
            }
            else {
                vpsCount--;
            }
            if (vpsCount < 0) {
                cout << "NO" << "\n";
                minus = true;
                break;
            }
        }

        if (minus == false) {
            if (vpsCount != 0) {
                cout << "NO" << "\n";
            }
            else {
                cout << "YES" << "\n";
            }
        }
    }
    
    return 0;
}

주석에 써놓은대로 스택을 굳이 안쓰고 

닫는 개수만 세주면 되겠죠

여는 괄호에서 닫는괄호를 차감해주고 음수가 된다면 닫는괄호가 더 많은거니

vps가 아니라고 볼 수 있습니다.

'[백준] > C++' 카테고리의 다른 글

백준 11687번 팩토리얼 0의 개수 [C++]  (0) 2023.07.08
백준 13300번 방 배정 [C++]  (0) 2023.06.25
백준 10845번 큐 [C++]  (0) 2023.06.25
백준16396번 선 그리기 [C++]  (0) 2023.06.25
백준 1316번 그룹 단어 체커 [C++]  (0) 2023.06.25

[

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    queue<int> cnt;

    while (n--) {
        string input;
        cin >> input;

        if (input == "push") {
            int input2;
            cin >> input2;
            cnt.push(input2);
        }
        if (input == "pop") {
            if (!cnt.empty()) {
                cout << cnt.front() << "\n";
                cnt.pop();
            } 
            else {
                cout << -1 << "\n";
            }
        }
        else if (input == "size") {
            cout << cnt.size() << "\n";
        }
        else if (input == "empty") {
            if (cnt.empty()) {
                cout << 1 << "\n";
            }
            else {
                cout << 0 << "\n";
            }
        }
        else if (input == "front") {
            if (!cnt.empty()) {
                cout << cnt.front() << "\n";
            }
            else {
                cout << -1 <<"\n";
            }
        }
        else if (input == "back") {
            if (!cnt.empty()) {
                cout << cnt.back() << "\n";
            }
            else {
                cout << -1 << "\n";
            }
        }
    }

    return 0;
}

 

라이브러리 연결해서 풀면 간단한 문제였습니다.

'[백준] > C++' 카테고리의 다른 글

백준 13300번 방 배정 [C++]  (0) 2023.06.25
백준 9012번 괄호 [C++]  (0) 2023.06.25
백준16396번 선 그리기 [C++]  (0) 2023.06.25
백준 1316번 그룹 단어 체커 [C++]  (0) 2023.06.25
백준 11365번 !밀비 급일 [C++]  (0) 2023.06.25

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int arr[10001] = {
        0,
    }; // 좌표의 길이

    int N; // 테스트 케이스
    cin >> N;
    int a, b;

    for (int i = 0; i < N; i++) { // 입력된 작대기만큼 배열 활성화
        cin >> a >> b;
        for (int j = a; j < b; j++) { // a 에서 b 범위에 신경쓸것
            arr[j] = 1;
        }
    }

    int cnt = 0;
    for (int k = 1; k <= 10001; k++) { // 작대기 길이 세주기

        if (arr[k] == 1) {
            cnt++;
        }
    }
    cout << cnt;
}

배열 초기화랑 작대기 길이에 주의, 정점의 개수를 세면 안됩니다

 

'[백준] > C++' 카테고리의 다른 글

백준 9012번 괄호 [C++]  (0) 2023.06.25
백준 10845번 큐 [C++]  (0) 2023.06.25
백준 1316번 그룹 단어 체커 [C++]  (0) 2023.06.25
백준 11365번 !밀비 급일 [C++]  (0) 2023.06.25
백준 5585번 거스름돈 [C++]  (0) 2023.06.25

+ Recent posts