경우없는 개발 블로그

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

#문제 간단 정리

소수판별 + 구현문제

#문제 해결 방법

우선 숫자가 주어지면 이 숫자로 만들수 있는 조합으로

만들수 있는 소수이니

숫자로 만드는조합 -> dfs 사용

소수판별 -> 에라토스테네스의 체 

이렇게 두가지 구현하면 된다

dfs구현에서 최대길이가 7자리수라 시간복잡도에는 문제 없는 것을 알 수 있다.

#전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

static const int MAX = 10'000'000;
bool primeArr[MAX];    
set<int> primeSet;    

string s;
set<int> madeNumbers;   

void sieveOfEratosthenes() {
    primeArr[0] = false;
    primeArr[1] = false;

    for (int i = 2; i < MAX; i++) {
        primeArr[i] = true;
    }

    for (int i = 2; i * i < MAX; i++) {
        if (primeArr[i]) {
            for (int j = i * i; j < MAX; j += i) {
                primeArr[j] = false;
            }
        }
    }
}


void dfs(string& input, vector<bool>& used, int length) {

    if ((int)input.size() == length) {
  
        int num = stoi(input);
        madeNumbers.insert(num);
        return;
    }


    for (int i = 0; i < (int)s.size(); i++) {
        if (!used[i]) {
            used[i] = true;
            input.push_back(s[i]);

            dfs(input, used, length);

            input.pop_back();
            used[i] = false;
        }
    }
}

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


    sieveOfEratosthenes();


    int t;
    cin >> t;
    while (t--) {
        cin >> s;
        madeNumbers.clear();


        for (int len = 1; len <= (int)s.size(); len++) {
            vector<bool> used(s.size(), false);
            string tmp;
            dfs(tmp, used, len);
        }


        int Pcount = 0;
        for (int num : madeNumbers) {
            if (primeArr[num]) {
                Pcount++;
            }
        }

        cout << Pcount << "\n";
    }
    return 0;
}

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

#문제 간단 정리

분류는 애드혹 + 게임이론으로 되어있는데...

대충 그리디하게 생각해서 풀었다고 생각한다.

#문제 해결 방법

두명다 최선의 방법을 사용하기 때문에

만약 종착역에 도착하기전에 1 (환승역이 있다면) 그 이후에 

0(일반역) 에서 멈춰서 승리하려고 하기 때문에

나는 뒤에서부터 역산해서 누가 이기면 되는지 추정하면 된다고 생각해서

뒤에부터 만약 1이 온다면 1뒤에 0이오면 승리자가 그대로고 (01)

1뒤에 1이 오게 되더라도 바로 자기턴이 돌아오기때문에 상관없다 (11)

다만 2번째역이 환승역이라면 (index 1)  

 바로 환승을해야 되기 때문에 

기존의 승리자가 바뀌게 된다

뭐 대충 이렇게 시뮬레이션해서 풀었다.

#전체 코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int n;

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

    cin >> n;
    vector<int> lines(n);
    
    for (int i = 0; i < n; i++) {
        cin >> lines[i];
    }

    int whoWin = 0; //0 세훈 1 민아
    for (int i = n - 2; i >= 0; i--) {
        if (lines[i] == 0) {

        }
        else if(lines[i]== 1) {

            if (i == 1) {
                if (whoWin == 1) whoWin = 0;
                else whoWin = 1;
                i--;
            }
            else if (lines[i - 1] == 0) {
                if (whoWin == 1) whoWin = 1;
                else whoWin = 0;
                i--;
            }
            else if (lines[i - 1] == 1) {
                if (whoWin == 1) whoWin = 1;
                else whoWin = 0;
                i--;
            }
        }
    }

    if (whoWin==0) {
        cout << "mnx" << '\n';
    }
    else {
        cout << "alsdkffhgk" << '\n';
    }

    return 0;
}

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

#문제 간단 정리

투 포인터를 사용하자

#문제 해결 방법

일단 정렬을 해주게 되면

우측에는 나도리가 많고 좌측에는 적기때문에

조건문1)

우측에 나도리가 기준치보다 적다면 좌측의 나도리를 왼쪽의 나도리를 사용해서

채워주는게 유리 

조건문2)

우측의 나도리가 기준치보다 많고

좌측의 나도리가 기준치보다 적다면

당연히 좌측의 나도리를 사용해서 우측의 나도리를 기준치만큼 채워주면된다

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n, k, t;
    cin >> n >> k >> t;

    vector<int> vec(n);

    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }

    sort(vec.begin(), vec.end());

    int left = 0;
    int right = vec.size()-1;
    long long count = 0;

         
    while (left < right) {
        

        if (vec[right] == k) {
            right--;
            if (left >= right) {
                break;
            }
        }
        else if (vec[right] < k) {

            int temp = k - vec[right];
            
            if (temp > vec[left]) {
                count += vec[left];   
                vec[right] += vec[left];
                vec[left] = 0;
                left++;
            }
            else if (temp < vec[left]) {
                vec[left] -= temp;
                vec[right] += temp;
                right--;
                count += temp;
            }
            else if (temp == vec[left]) { 
                vec[left] = 0;
                vec[right] += temp;
                left++;
                right--;
                count += temp;
            }
            
        }


        if(vec[left] < k && vec[right] > k) {

            int temp = k - vec[left];
            int temp2 = vec[right] - k;

            if (vec[right] - temp >= k) {
                vec[right] -= temp;
                vec[left] += temp;
                count += temp;
                left++;
            }
            else {
                vec[right] -= temp2;
                vec[left] += temp2;
                count += temp2;
                right--;
            }
    
        }
        else if (vec[left] == k || vec[left] == 0) {
            left++;
        }


    }



    for (auto a : vec) {
        if (a != k && a!=0) {
            cout << "NO" << '\n';
            return 0;
        }
    }
    if (count <= t) {
        ;
        cout << "YES" << '\n';
    }
    else {
        cout << "NO" << '\n';
    }
    return 0;
}

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

#문제 간단 정리

브루트포스 구현 + gcd

#문제 해결 방법

두 점을 골라서 gcd로 정수점의 개수들을 계산해주자

#전체 코드

#include <iostream>
#include <numeric> 
using namespace std;

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

    int N, M, K;
    cin >> N >> M >> K;

    int ans = 0;

    for (int x1 = 0; x1 <= N; x1++) {
        for (int y1 = 0; y1 <= M; y1++) {
            for (int x2 = 0; x2 <= N; x2++) {
                for (int y2 = 0; y2 <= M; y2++) {
                    // 같은 점이면 무시
                    if (x1 == x2 && y1 == y2) continue;

                    // (x1,y1) < (x2,y2) 조건을 통해 중복 방지
                    if (x1 > x2 || (x1 == x2 && y1 > y2)) continue;

                    int dx = x2 - x1;
                    int dy = y2 - y1;

                    int g = gcd(abs(dx), abs(dy));
                    // 선분 위 격자점 개수: g + 1
                    if (g + 1 == K) {
                        ans++;
                    }
                }
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

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

#문제 간단 정리

그래프를 이용한 탐색 문제

#문제 해결 방법

맵을 벗어나지 않는다고 주어져 있으니

사이클이 발생할수 밖에 없고 사이클의 개수를 판별해 주면 된다.

끝점 혹은 사이클을 판별하면 되는데

dfs 를 사용하지만 중복탐색이 안되도록 주의해야 한다

#전체 코드

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

int n, m;
vector<vector<char>> board;
vector<vector<int>> state;
// state: 0 = not visited, 1 = visiting, 2 = done

int presentCount;

int dmap(char dir) {
    if (dir == 'N') return 0;
    if (dir == 'S') return 1;
    if (dir == 'E') return 2;
    if (dir == 'W') return 3;
    return -1;
}


int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, 1,-1 };

void dfs(int y, int x) {
    state[y][x] = 1; 
    int dir = dmap(board[y][x]);
    int ny = y + dy[dir];
    int nx = x + dx[dir];

    if (state[ny][nx] == 0) {
        // 아직 방문 안한 칸이면 DFS 진행
        dfs(ny, nx);
    }
    else if (state[ny][nx] == 1) {
        // 현재 경로 상에 있는 노드를 다시 방문 → 사이클 발생
        presentCount++;
    }
    // 탐색 완료 처리
    state[y][x] = 2;
}

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

    cin >> n >> m;
    board.resize(n, vector<char>(m));
    state.resize(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        string input;
        cin >> input;
        for (int j = 0; j < m; j++) {
            board[i][j] = input[j];
        }
    }

    presentCount = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (state[i][j] == 0) {
                dfs(i, j);
            }
        }
    }

    cout << presentCount << "\n";
    return 0;
}

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

#문제 간단 정리

가능한 틱택토 모양인지 판별하라는 문제

#문제 해결 방법

워낙 3x3 이라 작기 때문에

브루트포스로 해결하면 된다

x가 이겻는지 o가 이겼는지 확인하고 돌의 개수를 확인하자

#전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <limits>

using namespace std;

int n;

bool checkLine(vector<vector<char>>& board, char c) {
    // c로 이루어진 3연속이 있는지 확인
    for (int i = 0; i < 3; i++) {
        // 행 체크
        if (board[i][0] == c && board[i][1] == c && board[i][2] == c) return true;
        // 열 체크
        if (board[0][i] == c && board[1][i] == c && board[2][i] == c) return true;
    }
    // 대각선 체크
    if (board[0][0] == c && board[1][1] == c && board[2][2] == c) return true;
    if (board[0][2] == c && board[1][1] == c && board[2][0] == c) return true;

    return false;
}

bool isValid(vector<vector<char>>& board) {
    int OCount = 0;
    int XCount = 0;
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 3; c++) {
            if (board[r][c] == 'O') OCount++;
            else if (board[r][c] == 'X') XCount++;
        }
    }

    // 말의 개수 조건
    if (!(XCount == OCount || XCount == OCount + 1)) {
        return false;
    }

    bool XWin = checkLine(board, 'X');
    bool OWin = checkLine(board, 'O');

    // 둘 다 이긴 경우
    if (XWin && OWin) {
        return false;
    }

    // X가 이긴 경우: XCount는 OCount + 1 이어야 함.
    if (XWin && (XCount != OCount + 1)) {
        return false;
    }

    // O가 이긴 경우: XCount == OCount 이어야 함.
    if (OWin && (XCount != OCount)) {
        return false;
    }

    // 승자가 없는 경우 말의 개수 조건은 이미 위에서 통과함.
    return true;
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
    
        vector<vector<char>> board(3, vector<char>(3));
        for (int r = 0; r < 3; r++) {
            string input;
            cin >> input;
            for (int c = 0; c < 3; c++) {
                board[r][c] = input[c];
            }
        }

        cout << (isValid(board) ? "yes" : "no") << "\n";
    }

    return 0;
}

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

#문제 간단 정리

CCW + 수학 문제

#문제 해결 방법

우선 관찰을 하면 p1 p2 두 점 사이에 선분이

홀수개면 둘 다 채굴 불가

짝수개면 둘 다 채굴 가능인 것을 알 수 있다.

때문에 두 점 사이에 선분이 몇개가 있는지 확인하면 되는데

CCW 를 활용하기 위해서 각 좌표들을 삼각함수를 사용해 극좌표를 직교좌표로 변경해준다

그런데 tan로 y좌표를 구하면 무한대가 되버리니

sin 으로 y좌표를 구해주고

각 선분에 대해서 p1 p2 에 대해서 ccw로 교차 판정을 해주면 된다

삼각함수 변경하는 부분에서 실수 오차가 날수 있으니 주의해 줘야된다.

#전체 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long double ld;

#define M_PI 3.14159265358979323846

int ccw(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3) {
    ld crossProduct = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);

    if (crossProduct > 0) {
        return 1; 
    } else if (crossProduct < 0) {
        return -1; 
    } else {
        return 0;
    }
}

// 메인 함수
int main() {
    int n;
    vector<pair<pair<ld, ld>, pair<ld, ld>>> lines;

    cin >> n;

    for (int i = 0; i < n; i++) {
        ld a, b;
        cin >> a >> b;
        ld radianA = (a * M_PI) / 1800.0;
        ld radianB = (b * M_PI) / 1800.0;
        ld transX1 = cos(radianA) * 1000;
        ld transY1 = sin(radianA) * 1000;
        ld transX2 = cos(radianB) * 1000;
        ld transY2 = sin(radianB) * 1000;
        lines.push_back({{transX1, transY1}, {transX2, transY2}});
    }

    int crossCount = 0;

    ld p1, p2, p1Length, p2Length;

    cin >> p1 >> p1Length >> p2 >> p2Length;

    ld radianP1 = (p1 * M_PI) / 1800.0;
    ld radianP2 = (p2 * M_PI) / 1800.0;
    ld p1X = cos(radianP1) * p1Length;
    ld p1Y = sin(radianP1) * p1Length;
    ld p2X = cos(radianP2) * p2Length;
    ld p2Y = sin(radianP2) * p2Length;

    for (int i = 0; i < lines.size(); i++) {
        ld x1 = lines[i].first.first, y1 = lines[i].first.second;
        ld x2 = lines[i].second.first, y2 = lines[i].second.second;

        int thirdCCW = ccw(x1, y1, x2, y2, p1X, p1Y);
        int fourthCCW = ccw(x1, y1, x2, y2, p2X, p2Y);

        if (thirdCCW == 0 || fourthCCW == 0) {
            continue;
        }

        if (thirdCCW * fourthCCW < 0) {
            crossCount++;
        }
    }

    cout << ((crossCount % 2) == 0 ? "YES" : "NO");

    return 0;
}

#include <iostream>
using namespace std;

// CCW 함수: 세 점의 방향성을 판단합니다.
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    // 벡터 AB와 벡터 AC의 외적 계산
    int crossProduct = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);

    // 방향성 판단
    if (crossProduct > 0) {
        return 1; // 반시계 방향 (Counter ClockWise)
    } else if (crossProduct < 0) {
        return -1; // 시계 방향 (ClockWise)
    } else {
        return 0; // 일직선 상 (Collinear)
    }
}

// 메인 함수
int main() {
    // 테스트 데이터 입력
    int x1, y1, x2, y2, x3, y3;
    cout << "세 점의 좌표를 입력하세요 (x1 y1 x2 y2 x3 y3): ";
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    // CCW 결과 확인
    int result = ccw(x1, y1, x2, y2, x3, y3);

    // 결과 출력
    if (result == 1) {
        cout << "반시계 방향 (Counter ClockWise)" << endl;
    } else if (result == -1) {
        cout << "시계 방향 (ClockWise)" << endl;
    } else {
        cout << "세 점이 일직선 상에 있습니다 (Collinear)" << endl;
    }

    return 0;
}

기본적으로 세개의 점이면 두개의 벡터를 만들수 있는데

이 두개의 벡터를 단위벡터로 사용하는 행렬식을 만들어서 이 행렬식이 0인지 음수인지 양수인지로

시계 반시계 일직선을 알 수 있다  

https://www.youtube.com/watch?v=15VOaSeHYeY&pp=ygUQI-2cmOyWtOynhOqzoeyEoA%3D%3D

행렬식에 관해서 이 강의를 한번 시청해봐도 좋을것이다.

나는 행렬식으로 ccw를 이해했기때문에 행렬식에대한 gpt 설명을 첨부한다 

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

#문제 간단 정리

#문제 해결 방법

이 문제에서 중요한건

그래프 문제로 바꿔서 생각하는 것이다

일단 전달되는 것에서 그래프를 착안 할 수 있는데

전달되는걸 간선으로 처리한다고 하면

진입차수가 0인 소들은 농부가 직접 전해줄 수 밖에 없다

때문에 그래프 탐색으로 진입차수가 0인 소들의 진입들을 처리해주면

진입차수가 1 이상인 소들이 남아있을텐데

진입차수가 1인데 방문이 안됫다는 이유는 

서로 거리가 같아서 주고 받기 때문에

• 노드 A는 노드 B에게 공을 전달하고,
• 노드 B는 노드 A에게 공을 전달합니다.

와 같은 상황이 생기기 때문이다

즉 이렇게 진입차수가 1이상인 것들의 방문을 처리하면서 필요한 공 개수를 체크해 주면된다

결론적으로 그래프로 바꿔서 생각한 후에 진입차수에 대해서 생각해보면 된다

#전체 코드

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

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> cows(n); // {소의 위치, 소의 원래 인덱스}
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cows[i] = { x, i };
    }

    sort(cows.begin(), cows.end()); // 소의 위치를 기준으로 정렬

    vector<int> to(n);       // 각 소가 공을 전달할 소의 인덱스
    vector<int> indegree(n); // 각 소의 진입 차수

    for (int i = 0; i < n; i++) {
        int left_dist = INT_MAX;
        int right_dist = INT_MAX;

        if (i > 0) {
            left_dist = cows[i].first - cows[i - 1].first;
        }
        if (i < n - 1) {
            right_dist = cows[i + 1].first - cows[i].first;
        }

        if (left_dist <= right_dist) {
            // 왼쪽 소에게 전달
            to[i] = i - 1;
        }
        else {
            // 오른쪽 소에게 전달
            to[i] = i + 1;
        }

        // 공을 받는 소의 진입 차수 증가
        indegree[to[i]]++;
    }

    // 초기 공을 받아야 하는 소의 수 계산
    int balls = 0;
    vector<bool> visited(n, false);

    // 진입 차수가 0인 소들을 방문하여 도달할 수 있는 모든 소들을 방문 표시
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            balls++;
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                curr = to[curr];
            }
        }
    }

    // 아직 방문하지 않은 소들을 탐색하여 사이클을 찾음
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            balls++; // 사이클마다 공 하나 추가
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                curr = to[curr];
            }
        }
    }

    cout << balls << endl;

    return 0;
}

• 중복 부분 문제 (Overlapping Subproblems):
  • 동적 프로그래밍 문제는 동일한 하위 문제를 여러 번 반복해서 푸는 특성이 있습니다. 예를 들어 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같은 점화식을 사용할 때, F(n-1)과 F(n-2)를 반복적으로 계산하는 경우가 많습니다.
  • DP에서는 이러한 중복 계산을 **메모이제이션 (Memoization)**이나 탑다운/바텀업 접근법으로 저장해 두고, 동일한 하위 문제가 다시 등장하면 저장된 값을 사용하여 계산을 줄입니다. 이를 통해 시간 복잡도를 줄여 효율성을 높입니다.
• 최적 부분 구조 (Optimal Substructure):
  • 최적 부분 구조란 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전체 문제의 최적해를 구성할 수 있는 특성입니다. 다시 말해, 전체 문제를 해결하는 최적의 해답이 하위 문제들의 최적해로 이루어져 있다는 것입니다.
  • 예를 들어, 최단 경로 문제에서는 특정 노드까지의 최단 경로가 그 이전 경로들의 최단 경로들로 이루어져 있습니다.