전체 글103 [백준 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. [알고리즘] 누적 합 1. 문제 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 2024. 4. 11. [백준 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. 문제 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 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.a.. 2024. 4. 6. [백준 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. [알고리즘] BFS(너비 우선 탐색) 1. Breadth First Search (BFS, 너비 우선 탐색1. 완전 탐색 알고리즘 - 모든 경우의 수를 탐색하는 알고리즘2. 시작점에서 가까운 점부터 탐색하는 방식 - 개미굴에 물을 부어서 물이 점점 안 쪽으로 스며들어가는 방식과 비슷하다. 2. 장점1) 출발노드에서 목표 노드까지의 최단 길이 경로를 보장한다. 3. 단점1) 경로가 매우 길 경우에는 탐색 기지가 급격히 증가하여 많은 기억 공간을 필요로 한다. 4. 구현Queue를 통해 구현아래 3가지 구조로 나눌 수 있다.1) 시작점 셋팅2) 현재 방문 노드를 Queue에서 pop하기3) 다음으로 방문할 노드 Queue에 삽입#include #include #include ;using namespace std;bool visited[11];v.. 2024. 4. 3. 이전 1 2 3 4 5 6 ··· 11 다음
