![]()
https://www.acmicpc.net/problem/4347 #문제 간단 정리 가능한 틱택토 모양인지 판별하라는 문제 #문제 해결 방법 워낙 3x3 이라 작기 때문에브루트포스로 해결하면 된다 x가 이겻는지 o가 이겼는지 확인하고 돌의 개수를 확인하자 #전체 코드 #include #include #include #include using namespace std;int n;bool checkLine(vector>& board, char c) { // c로 이루어진 3연속이 있는지 확인 for (int i = 0; i >& board) { int OCount = 0; int XCount = 0; for (int r = 0; r > n; for (int i = 0; i ..
![]()
https://www.acmicpc.net/problem/32823 #문제 간단 정리CCW + 수학 문제 #문제 해결 방법 우선 관찰을 하면 p1 p2 두 점 사이에 선분이홀수개면 둘 다 채굴 불가짝수개면 둘 다 채굴 가능인 것을 알 수 있다. 때문에 두 점 사이에 선분이 몇개가 있는지 확인하면 되는데 CCW 를 활용하기 위해서 각 좌표들을 삼각함수를 사용해 극좌표를 직교좌표로 변경해준다 그런데 tan로 y좌표를 구하면 무한대가 되버리니sin 으로 y좌표를 구해주고 각 선분에 대해서 p1 p2 에 대해서 ccw로 교차 판정을 해주면 된다 삼각함수 변경하는 부분에서 실수 오차가 날수 있으니 주의해 줘야된다. #전체 코드#include #include #include using namespace std;..
#include 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 > x1 >> y1 >> x2 >> y2 >> x3 >> y3; // CCW 결과 확인 int result = ccw(x1,..
![]()
https://www.acmicpc.net/problem/15752 #문제 간단 정리 #문제 해결 방법 이 문제에서 중요한건 그래프 문제로 바꿔서 생각하는 것이다 일단 전달되는 것에서 그래프를 착안 할 수 있는데전달되는걸 간선으로 처리한다고 하면 진입차수가 0인 소들은 농부가 직접 전해줄 수 밖에 없다때문에 그래프 탐색으로 진입차수가 0인 소들의 진입들을 처리해주면 진입차수가 1 이상인 소들이 남아있을텐데진입차수가 1인데 방문이 안됫다는 이유는 서로 거리가 같아서 주고 받기 때문에 노드 A는 노드 B에게 공을 전달하고,노드 B는 노드 A에게 공을 전달합니다.와 같은 상황이 생기기 때문이다 즉 이렇게 진입차수가 1이상인 것들의 방문을 처리하면서 필요한 공 개수를 체크해 주면된다 결론적으로 그래프로 바..
중복 부분 문제 (Overlapping Subproblems):동적 프로그래밍 문제는 동일한 하위 문제를 여러 번 반복해서 푸는 특성이 있습니다. 예를 들어 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같은 점화식을 사용할 때, F(n-1)과 F(n-2)를 반복적으로 계산하는 경우가 많습니다.DP에서는 이러한 중복 계산을 **메모이제이션 (Memoization)**이나 탑다운/바텀업 접근법으로 저장해 두고, 동일한 하위 문제가 다시 등장하면 저장된 값을 사용하여 계산을 줄입니다. 이를 통해 시간 복잡도를 줄여 효율성을 높입니다.최적 부분 구조 (Optimal Substructure):최적 부분 구조란 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전..
#include #include #include using namespace std;const int INF = 1e9;bool bellmanFord(int start, int n, vector>& edges, vector& dist) { dist[start] = 0; // 모든 간선을 최대 (V-1)번 반복 for (int i = 0; i > n >> m; vector> edges; for (int i = 0; i > u >> v >> w; edges.push_back({u, v, w}); } int start; cin >> start; vector dist(n, INF); bool noNegativeCycle = bellmanFord(..
#include #include #include #include using namespace std;const int INF = 1e9; // 무한을 나타내기 위해 사용vector dijkstra(int start, int n, vector>>& graph) { vector dist(n, INF); // 최단 거리 테이블을 무한으로 초기화 priority_queue, vector>, greater> pq; dist[start] = 0; pq.push({0, start}); // 시작 노드로 가기 위한 비용은 0으로 설정 while (!pq.empty()) { int cost = pq.top().first; // 현재 노드까지의 비용 int u = ..
자바에서 문자열 처리를 하다 보면, 특정 패턴을 찾기 위해 **정규표현식(Regex)**을 사용하게 됩니다. 그런데 저는 **문자 그대로의 \n**을 찾으려고 할 때 예상치 못한 문제를 겪었습니다. 이 글에서는 제가 겪은 문제와 이를 어떻게 해결했는지 공유하고자 합니다.문제 상황: \n을 찾으려는데 매칭이 되지 않음목표: 문자열에서 문자 그대로의 \n (백슬래시와 문자 n)을 찾고 싶었습니다.원인 분석: 이스케이프 문자의 이중 처리 필요1. 정규표현식에서의 \n과 \\n\n: 정규표현식에서 줄바꿈 문자를 의미합니다.\\n: **문자 그대로의 \와 n**을 매칭합니다.첫 번째 \는 이스케이프 문자로 사용되고, 두 번째 \는 실제 백슬래시를 나타냅니다. 2. 자바 문자열에서도 똑같이 처리 된다 3. 때문에 ..
![]()
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 #include #include using namespace std;int main() { long long n; cin >> n; vector> dp(n+1,vector(2)); // 이친수는 1이 두번 나타나지 않음 // dp[i][j] = i길이의 j로 끝나는 이친수 의 ..
![]()
https://www.acmicpc.net/problem/7861 #문제 간단 정리가장 긴 부분수열 찾는문제 dp 이고 웰노운이다 #문제 해결 방법웰노운 문제라서 따로 해설을 첨부하지는 않겟다. #전체 코드#include #include using namespace std;int main() { int n; cin >> n; vector vec(n); for (int i = 0; i > vec[i]; } vector dp(n,1); int maxlen = 1; for (int i = 0; i vec[j] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; maxlen = m..
