본문 바로가기

백준 알고리즘66

[백준 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.
[백준 C++] 2623번: 음악프로그램 1. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 위상 정렬 3. 소스 코드 Key Point) 1. 순서가 정해져 있는 일련의 수열을 차례대로 출력하는 문제는 '위상 정렬' 알고리즘을 사용한다. #include #include #include using namespace std; int N, M; int arr[1001]; int inDegree[1001]; int visited[1.. 2023. 10. 3.
[백준 C++] 2473번: 세 용액 1. 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2. 알고리즘 분류 정렬 이분 탐색 두 포인터 3. 소스 코드 Key Point) 1. 투 포인터 알고리즘을 활용하기 위해 정렬한다. 2. 3개의 값을 비교할 때는 하나를 정해 놓고 2개의 값을 '투 포인터' 알고리즘을 통해 계산한다. #include #include #include using namespace std; long long solutions[5000].. 2023. 10. 3.
[백준 C++] 2342번: Dance Dance Revolution 1. 문제 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 3. 소스 코드 Key Point) 1. 왼쪽 발로 움직이는 경우와 오른쪽 발로 움직이는 경우 모두 탐색한다. 2. 왼쪽 발로 움직일 때 드는 힘과 오른쪽 발로 움직일 때 드는 힘 중 작은 값을 선택한다. #include #include #include #define INF 987654321; using names.. 2023. 10. 3.
[백준 C++] 2252번: 줄 세우기 1. 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 위상 정렬 3. 소스 코드 Key Point) 1. 그래프를 이용하여 학생 순서를 정리한다. 2. '위상 정렬'을 사용하여 그래프 순서대로 값을 정렬한다. #include #include #include #define MAX_N 32001 using namespace std; int N, M; int visite.. 2023. 10. 3.
[백준 C++] 2143번: 두 배열의 합 1. 문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 2. 알고리즘 분류 자료 구조 이분 탐색 누적 합 3. 소스 코드 Key Point) 1. 두 A, B의 배열의 누적 합들을 모두 구한다. 2. B를 오름차순으로 정렬한 후, 이진 탐색을 하면 빠르게 해답을 찾을 수 있다. #include #include #include using namespace std;.. 2023. 10. 3.
[백준 C++] 1644번: 소수의 연속합 1. 문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 2. 알고리즘 분류 수학 정수론 두 포인터 소수 판정 에라토스테네스의 체 3. 소스 코드 Key Point) 1. 소수를 찾는 문제는 '에라토스테네스의 체'를 활용하면 빠르게 구할 수 있다. 2. 연속 부분 수열 문제는 '두 포인터'를 활용하면 빠르게 구할 수 있다. #include #include using namespace std; bool is_prime[4000006]; vector prime_num; int main() { ios_base::sync_with_stdio(false); cin.tie.. 2023. 10. 3.
[백준 C++] 1005번: ACM Craft 1. 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 그래프 이론 위상 정렬 3. 소스 코드 Key Point) 1. 순서가 정해져 있는 일련의 작업을 차례대로 수행할 때는 '위상 정렬' 알고리즘을 활용한다. 2. '위상 정렬' 알고리즘을 통해 탐색하면서 최대로 걸리는 시간을 갱신해 나간다. #include #include #include #include using namespace std; i.. 2023. 10. 2.

티스토리툴바