C++64 [백준 C++] 1509번: 팰린드롬 분할 1. 문제https://www.acmicpc.net/problem/1509 2. 알고리즘 분류다이나믹 프로그래밍 3. 소스코드#include #include #include #define MAX_LEN 2501#define INF 2134567890using namespace std;bool dp[MAX_LEN][MAX_LEN];string str;int str_len, result[MAX_LEN];// 팰린드롬인지 확인하는 알고리즘bool is_palindrome(int start, int end) { // end 값이 문자열 길이를 넘어갔을 경우, False if (end > str_len) return false; // 시작 문자열과 끝 문자열이 같고, 시작점과 끝점 문자열을 제외했을 때, 그 문.. 2024. 5. 4. [백준 C++] 1208번: 부분수열의 합 2 1. 문제https://www.acmicpc.net/problem/1208 2. 알고리즘 분류이분 탐색중간에서 만나기 3. 소스 코드#include #include #define MAX_N 40using namespace std;int N, S;int arr[MAX_N];map sum2cnt;long long cnt;// 오른쪽 부분수열의 모든 경우의 수 계산void rightSeq(int mid, int sum) { // 수열의 끝까지 도달했을 경우, if (mid == N) { sum2cnt[sum]++; // 부분수열의 합을 저장 return; } rightSeq(mid + 1, sum + arr[mid]); // 해당 index의 수열의 값을 더했을 경우, rightSeq(mid + 1, su.. 2024. 5. 1. [백준 C++] 17387번: 선분 교차 2 1. 문제https://www.acmicpc.net/problem/17387 2. 알고리즘 분류기하학많은 조건 분기선분 교차 판정 3. 소스 코드#include #include using namespace std;pair A;pair B;pair C;pair D;// CCW(Counter ClockWise) 알고리즘int ccw(pair p1, pair p2, pair p3){ // 외적 계산 long long temp = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second; temp -= p1.second * p2.first + p2.second * p3.first + p3.second * p1.first; if (temp > 0) r.. 2024. 5. 1. [백준 C++] 16946번: 벽 부수고 이동하기 4 1. 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 3. 소스 코드 #include #include #include #include #define MAX_N 1000 #define MAX_M 1000 using namespace std; int N, M; int dy[4] = {-1, 0, 1, 0}; int dx[4] = { 0, 1, 0.. 2024. 4. 14. [알고리즘] 이진 탐색(이분 탐색, Binary Search) 1. 개요1. O(logN) 시간 복잡도로 해당 배열에서 특정 값을 찾는 알고리즘 2. 알고리즘 코드vector ans;// 이진 탐색 알고리즘int binary_search(int n){ int low = 0; int high = ans.size() - 1; int ret = MAX_N; while (low = n) { ret = min(ret, mid); high = mid - 1; } else low = mid + 1; } return ret;} 3. 문제https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가.. 2024. 4. 14. [백준 C++] 12015번: 가장 긴 증가하는 부분 수열 2 1. 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 2. 알고리즘 분류 이분 탐색 가장 긴 증가하는부분 수열 3. 소스 코드 #include #include #include #define MAX_N 1000001 using namespace std; int nums[MAX_N]; vector ans; // 이진 탐색 알고리즘 int binary_search(int n) { int low = 0; int high = ans.size() -.. 2024. 4. 14. [알고리즘] 분리 집합(Union-Find) 1. 개요 1. 각 노드들을 그룹을 지을 때 사용하는 알고리즘 2. 알고리즘 코드 int parent[MAX_G]; int Find(int a) { int pA = parent[a]; if (pA == a) return a; return parent[a] = Find(pA); } void Union(int a, int b) { int pA = Find(a); int pB = Find(b); if (pA 2024. 4. 14. [백준 C++] 10775번: 공항 1. 문제 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 2. 알고리즘 분류 자료 구조 그리디 알고리즘 분리 집합 3. 소스 코드 #include #define MAX_G 100005 using namespace std; int G, P; int g[MAX_G]; int airport[MAX_G]; int parent[MAX_G]; int Find(int a) { int pA = parent[a]; if (p.. 2024. 4. 14. [백준 C++] 9527번: 1의 개수 세기 1. 문제 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 2. 알고리즘 분류 수학 누적 합 비트마스킹 3. 소스 코드 #include #define MAX 55 using namespace std; long long A, B; long long power[MAX]; // 1 ~ x까지 모든 수의 1의 개수의 합 계산 함수 long long calculate(long long x) { long long ret = x &.. 2024. 4. 11. [백준 C++] 1766번: 문제집 1. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 2. 알고리즘 분류 자료 구조 그래프 이론 우선순위 큐 위상 정렬 방향 비순환 그래프 3. 소스 코드 #include #include #include #include #define MAX_N 32001 using namespace std; int N, M; int visited[MAX_N]; int inDegree[MAX_N]; vector graph[MA.. 2024. 4. 11. 이전 1 2 3 4 5 ··· 7 다음
