경우없는 개발 블로그

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):
  • 최적 부분 구조란 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전체 문제의 최적해를 구성할 수 있는 특성입니다. 다시 말해, 전체 문제를 해결하는 최적의 해답이 하위 문제들의 최적해로 이루어져 있다는 것입니다.
  • 예를 들어, 최단 경로 문제에서는 특정 노드까지의 최단 경로가 그 이전 경로들의 최단 경로들로 이루어져 있습니다.

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

const int INF = 1e9;

bool bellmanFord(int start, int n, vector<tuple<int, int, int>>& edges, vector<int>& dist) {
    dist[start] = 0;

    // 모든 간선을 최대 (V-1)번 반복
    for (int i = 0; i < n - 1; i++) {
        for (auto& edge : edges) {
            int u, v, weight;
            tie(u, v, weight) = edge;

            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // 음수 사이클 체크
    for (auto& edge : edges) {
        int u, v, weight;
        tie(u, v, weight) = edge;

        if (dist[u] != INF && dist[u] + weight < dist[v]) {
            return false; // 음수 사이클이 존재
        }
    }

    return true; // 음수 사이클이 없음
}

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

    vector<tuple<int, int, int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    int start;
    cin >> start;

    vector<int> dist(n, INF);
    bool noNegativeCycle = bellmanFord(start, n, edges, dist);

    if (noNegativeCycle) {
        for (int i = 0; i < n; i++) {
            if (dist[i] == INF) {
                cout << "Node " << i << ": Unreachable" << endl;
            } else {
                cout << "Node " << i << ": " << dist[i] << endl;
            }
        }
    } else {
        cout << "Negative cycle detected in the graph." << endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

const int INF = 1e9; // 무한을 나타내기 위해 사용

vector<int> dijkstra(int start, int n, vector<vector<pair<int, int>>>& graph) {
    vector<int> dist(n, INF); // 최단 거리 테이블을 무한으로 초기화
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[start] = 0;
    pq.push({0, start}); // 시작 노드로 가기 위한 비용은 0으로 설정

    while (!pq.empty()) {
        int cost = pq.top().first;    // 현재 노드까지의 비용
        int u = pq.top().second;      // 현재 노드
        pq.pop();

        if (cost > dist[u]) continue; // 이미 처리된 노드라면 무시

        for (auto& edge : graph[u]) {
            int v = edge.first;       // 인접 노드
            int weight = edge.second; // 가중치

            if (dist[u] + weight < dist[v]) { // 더 짧은 경로 발견 시 업데이트
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist; // 각 노드로의 최단 거리 반환
}

int main() {
    int n, m; // n: 노드 개수, m: 간선 개수
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);

    for (int i = 0; i < m; i++) {
        int u, v, w; // u에서 v로 가는 가중치 w인 간선
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w}); // 무방향 그래프일 경우에만 추가
    }

    int start;
    cin >> start; // 시작 노드 입력

    vector<int> shortest_paths = dijkstra(start, n, graph);

    for (int i = 0; i < n; i++) {
        if (shortest_paths[i] == INF)
            cout << "Node " << i << ": Unreachable" << endl;
        else
            cout << "Node " << i << ": " << shortest_paths[i] << endl;
    }

    return 0;
}

자바에서 문자열 처리를 하다 보면, 특정 패턴을 찾기 위해 **정규표현식(Regex)**을 사용하게 됩니다. 그런데 저는 **문자 그대로의 \n**을 찾으려고 할 때 예상치 못한 문제를 겪었습니다. 이 글에서는 제가 겪은 문제와 이를 어떻게 해결했는지 공유하고자 합니다.

문제 상황: \n을 찾으려는데 매칭이 되지 않음

목표: 문자열에서 문자 그대로의 \n (백슬래시와 문자 n)을 찾고 싶었습니다.

원인 분석: 이스케이프 문자의 이중 처리 필요

1. 정규표현식에서의 \n과 \\n

• \n: 정규표현식에서 줄바꿈 문자를 의미합니다.
• \\n: **문자 그대로의 \와 n**을 매칭합니다.
  • 첫 번째 \는 이스케이프 문자로 사용되고, 두 번째 \는 실제 백슬래시를 나타냅니다.

2. 자바 문자열에서도 똑같이 처리 된다

3. 때문에 자바 문자열 -> 정규표현식 처리

자바 문자열이 \\n 으로 입력되고 정규표현식에서는 \n 으로 처리되어서 문자열을 찾기 때문에 

줄바꿈 문자로 취급되기때문에

자바문자열을 \\\\n으로 입력되면 정규표현식으로 \\n으로 인식 -> "\n" 문자를 찾게 됩니다

자바 문자열 리터럴에서의 이스케이프

정규표현식 엔진에서의 해석

가 두번 처리됨을 유의해야된다는 것입니다

때문에 //를 두번 써줘야 합니다

해결 방법: 올바른 이스케이프 처리로 패턴 작성하기

1. 자바 코드에서 패턴을 작성할 때 \\\\n으로 입력

• 자바 문자열에서 \\는 백슬래시(\)를 의미하므로, 정규표현식의 \\n을 표현하려면 \\\\n으로 작성해야 합니다.

2. 코드 예시

public class FindLiteralBackslashN {
    public static void main(String[] args) {
        // 입력 문자열: 문자 그대로의 \n 포함
        String input = "이 문자열에는 \\n 이 포함되어 있습니다.";

        // 정규표현식 패턴: \\n (자바 문자열에서는 \\\\n)
        String regexPattern = "\\\\n";

        // 패턴 컴파일
        Pattern pattern = Pattern.compile(regexPattern);
        Matcher matcher = pattern.matcher(input);

        // 매칭 확인
        if (matcher.find()) {
            System.out.println("문자 그대로의 \\n을 찾았습니다!");
            System.out.println("매칭된 부분: " + matcher.group());
        } else {
            System.out.println("문자 그대로의 \\n을 찾지 못했습니다.");
        }
    }
}​

4. 실행 결과

왜 이렇게 해야 할까?

이스케이프 처리 단계별 이해

1. 자바 문자열 리터럴에서의 이스케이프:
   • "\\\\n"은 자바 문자열에서 "\\n"으로 해석됩니다.
   • 각 \\는 하나의 \로 변환됩니다.
2. 정규표현식 엔진에서의 해석:
   • "\\n"은 정규표현식에서 \n으로 인식됩니다.
   • 하지만 정규표현식에서 \n은 줄바꿈 문자가 아니라 **백슬래시와 문자 n**을 의미합니다.
3. 매칭 과정:
   • 입력 문자열에서 **\**와 **n**이 연속으로 나타나는 부분을 찾아 매칭합니다.

요약 및 정리

• 문자 그대로의 \n을 찾기 위해서는 정규표현식 패턴을 \\n으로 설정해야 합니다.
• 자바 코드에서 이 패턴을 표현하려면 \\\\n으로 작성해야 합니다.
  • 자바 문자열에서 백슬래시를 표현하기 위해 \\를 사용하기 때문입니다.
• 따라서, 자바에서 정규표현식을 사용할 때는 자바 문자열과 정규표현식의 이스케이프 처리를 모두 고려해야 합니다.

결론

자바에서 정규표현식을 사용하여 특정 문자를 찾을 때는 이스케이프 문자의 처리에 주의해야 합니다. 특히, 백슬래시(\)는 자바 문자열과 정규표현식 모두에서 특별한 의미를 가지므로, 이를 올바르게 이스케이프하지 않으면 의도한 대로 동작하지 않을 수 있습니다.

핵심 포인트:

• 정규표현식에서 문자 그대로의 \n을 매칭하려면 \\n을 사용한다.
• 자바 문자열에서 이 정규표현식을 표현하려면 \\\\n으로 작성한다.

이 원리를 이해하면 비슷한 문제를 해결할 때 큰 도움이 될 것입니다.

Tip: 다른 이스케이프 문자를 찾을 때도 동일한 원리가 적용됩니다. 예를 들어, 문자 그대로의 \t를 찾고 싶다면 정규표현식은 \\t, 자바 문자열에서는 "\\\\t"로 작성해야 합니다.

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

#문제 간단 정리

기본적인 dp 문제

#문제 해결 방법

    // 이친수는 1이 두번 나타나지 않음
    // dp[i][j] = i길이의 j로 끝나는 이친수 의 개수 = 

    //dp[i][0] = dp[i-1][0] + dp[i-1][1] 
    // dp[i][1] = dp[i-1][0] 

#전체 코드

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

using namespace std;

int main() {
    long long n;
    cin >> n;
    
    vector<vector<long long>> dp(n+1,vector<long long>(2));
    // 이친수는 1이 두번 나타나지 않음
    // dp[i][j] = i길이의 j로 끝나는 이친수 의 개수 = dp[i][0] = dp[i-1][0] + dp[i-1][1] 
    // dp[i][1] = dp[i-1][0] 

    dp[1][0] = 0;
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
    }

    cout << dp[n][0] + dp[n][1] << '\n';

    return 0;
}

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

#문제 간단 정리

가장 긴 부분수열 찾는문제 

dp 이고 웰노운이다

#문제 해결 방법

웰노운 문제라서 따로 해설을 첨부하지는 않겟다.

#전체 코드

#include <iostream>
#include <vector>

using namespace std;





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

    vector<int> vec(n);

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


    vector<int> dp(n,1);
    int maxlen = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i ; j++) {
            if (vec[i] > vec[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                maxlen = max(dp[i], maxlen);
            }
        }
    }

    cout << maxlen << '\n';

    return 0;
}

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

#문제 번역

문제 설명

소들은 소풍을 가고 싶어 합니다! Farmer John의 K마리 소들은 각각 N개의 목초지 중 한 곳에서 풀을 뜯고 있습니다. 목초지는 1번부터 N번까지 번호가 매겨져 있으며, 일방통행 경로 M개로 연결되어 있습니다(경로는 자기 자신을 연결하는 경우는 없습니다).

소들은 동일한 목초지에서 만나 소풍을 가고 싶어 하지만, 일방통행 경로로 인해 어떤 소들은 특정 목초지로만 갈 수 있을 수도 있습니다. 모든 소들이 도달할 수 있는 목초지가 몇 개인지 찾아서 소들이 만날 수 있는 소풍 장소를 정해주세요.

입력

1번째 줄: 세 개의 정수 K, N, M이 공백으로 구분되어 주어집니다. (1 ≤ K ≤ 100, 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000)

2번째 줄부터 K개의 줄: 각 줄은 소들이 있는 목초지 번호가 하나씩 주어집니다. 이 목초지 번호는 1부터 N까지의 숫자입니다.

K+2번째 줄부터 M+K+1번째 줄: 각 줄에는 두 개의 정수 A와 B가 주어지며, 이는 목초지 A에서 목초지 B로 가는 일방통행 경로가 있음을 나타냅니다. (1 ≤ A, B ≤ N, A ≠ B)

출력

모든 소들이 일방통행 경로를 통해 도달할 수 있는 목초지의 수를 출력하세요.

#문제 간단 정리

그래프 탐색문제 

말 그대로 각 소들이 전부 방문하는 목초지의 개수를 찾아주면 된다

#문제 해결 방법

나는 각 소 들을 2차원 배열로

방문배열로 만들어줬고

방문여부는 dfs로 탐색하였다

그리고 각 목초지에 모든소가 방문하는지 탐색해주면 된다.

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int k, n, m;
vector<vector<int>> graph;
vector<int> cowPos;
vector<vector<bool>> check;

void dfs(int cowNum, int index) {
    for (auto a : graph[index]) {
        if (!check[cowNum][a]) {
            check[cowNum][a] = true;
            dfs(cowNum, a);
        }
    }
}

int main() {
    cin >> k >> n >> m;
    check.resize(k, vector<bool>(n, false));

    for (int i = 0; i < k; i++) {
        int input;
        cin >> input;
        cowPos.push_back(input - 1);
    }

    graph.resize(n);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a - 1].push_back(b - 1);
    }

    for (int i = 0; i < k; i++) {
        int cp = cowPos[i];
        check[i][cp] = true;
        dfs(i, cp);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        bool all_cows_can_reach = true;
        for (int j = 0; j < k; j++) {
            if (!check[j][i]) {
                all_cows_can_reach = false;
                break;
            }
        }
        if (all_cows_can_reach) ans++;
    }

    cout << ans << endl;

    return 0;
}