백준76 [백준 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. [알고리즘] DFS (깊이 우선 탐색) 1. Depth First Search (DFS, 깊이 우선 탐색)1. 완전 탐색 알고리즘 - 모든 경우의 수를 탐색하는 알고리즘2. 한 루트로 최대한 깊이 탐색하는 방식 - 트리나 그래프에서 한 루트로 쭉 탐색하다가 끝에 도달하면 다시 이전으로 돌아와서 다른 루트로 가는 방식 - 미로 찾기에서 한 방향으로 쭉 가다가 막히면, 다시 이전 분기점으로 돌아와서 다른 방향으로 가보면서 모든 루트를 탐색하는 방식 2. 장점1) 저장 공간의 수요가 비교적 적다. - 현 경로상의 노드들만 기억하면 되므로2) 목표 노드가 깊은 단계에 있을 경우, 해를 빨리 구할 수 있다. 3. 단점1) 해가 없는 경로에 깊이 빠질 가능성이 있다. - 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못했다면, 다른 경로를.. 2024. 4. 3. [알고리즘] 배낭 문제 1. 배낭 문제 알고리즘 문제 모음집 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 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$,.. 2024. 4. 3. [백준 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. [백준 C++] 11049번: 행렬 곱셈 순서 1. 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 3. 소스 코드 #include #include #define INF 987654321 using namespace std; pair matrix[501]; int dp[501][501]; int main() { // N : 행렬의 갯수 입력 int N, r, c, A, B, C; cin >> N; // 행렬 입력 for (int i .. 2023. 12. 9. [백준 C++] 9466번: 텀 프로젝트 1. 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 깊이 우선 탐색 3. 소스 코드 #include #include using namespace std; int ans; int choice[100001]; bool visited[100001]; bool done[100001]; void dfs(int cur) { visited[cur] = true; int next = choice[cur]; if .. 2023. 12. 3. [백준 C++] 7579번: 앱 1. 문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 배낭 문제 3. 소스 코드 #include #include using namespace std; int memory_table[101]; int cost_table[101]; int dp[101][10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // N : 앱의.. 2023. 12. 3. [백준 C++] 4386번: 별자리 만들기 1. 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 최소 스패닝 트리 3. 소스 코드 #include #include #include #include #include using namespace std; int n, parent[101]; vector stars; vector graph; // 부모를 찾는 함수 int Find(int x) { return parent[x] == x ? x : parent[x.. 2023. 10. 22. 이전 1 2 3 4 5 6 ··· 8 다음
