백준 알고리즘68 [백준 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. [백준 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. [백준 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. [백준 C++] 1202번: 보석 도둑 1. 문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 2. 알고리즘 분류 자료 구조 그리디 알고리즘 정렬 우선순위 큐 3. 소스 코드 #include #include #include #include #define MAX_N 300000 #define MAX_K 300000 using namespace std; int N, K; pair gems[MAX_N]; int backpac.. 2024. 4. 6. [백준 C++] 14888번: 연산자 끼워넣기 1. 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 2. 알고리즘 분류 브루트포스 알고리즘 백트래킹 3. 소스코드 #include #include #include #define MAX_N 11 using namespace std; int N; int max_val = -1000000000; int min_val = 1000000000; int numbers[MAX_N]; int .. 2024. 4. 6. [백준 C++] 20303번: 할로윈의 양아치 1. 문제 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 자료 구조 그래프 이론 그래프 탐색 분리 집합 배낭 문제 3. 소스 코드 #include #include #include using namespace std; int N, M, K; int candy[30001]; int total_candy[30001]; int.. 2024. 4. 3. 이전 1 2 3 4 5 ··· 7 다음
