백준 C++33 [백준 C++] 20040번: 사이클 게임 1. 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 2. 알고리즘 분류 자료 구조 분리 집합 3. 소스 코드 Key Point) 1. 사이클 여부를 확인하는 문제는 Union-Find를 활용한다. 2. a와 b의 parent가 같으면, 사이클이다. #include using namespace std; int parent[500005]; int Find(int a) { if (a == parent[a]) return a; else r.. 2023. 10. 2. [백준 C++] 17404번: RGB거리 2 1. 문제 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 3. 소스 코드 Key Point) 1. 다이나믹 프로그래밍을 통해 최소 비용을 구해 나간다. 2. 빨강 or 파랑 or 초록 시작으로 총 3가지 경우의 수를 각자 계산해 나간다. #include #include using namespace std; #define MAX 987654321; int rgb[1000][3].. 2023. 10. 2. [백준 C++] 9252번: LCS 2 1. 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 3. 소스코드 #include #include using namespace std; int dp[1003][1003]; string str1, str2; string str_tmp; void dfs(int y, int x) { if (dp[y][x] == 0) return;// LCS 테이블 값이 0.. 2023. 9. 28. [백준 C++] 2239번 스도쿠 1. 문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 2. 알고리즘 분류 구현 백트래킹 3. 소스 코드 #include #include using namespace std; int map[9][9], blank_cnt; bool is_end = false; vector blank; // 가로 방향으로 해당 값이 들어갈 수 있는지 확인하는 함수 int check_horizontal(int y, int val) { for (int x =.. 2023. 9. 28. [백준 C++] 1806번 : 부분합 1. 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 2. 알고리즘 분류 누적 합 두 포인터 3. 소스 코드 #include #include #include #define INF 987654321 using namespace std; int main() { // N : 수열의 갯수, S : 최소 누적합 입력 int N, S; vector sequence; scanf("%d %d", &N, &S); // 수열 입력 for (i.. 2023. 9. 14. [백준 C++] 1647번: 도시 분할 계획 1. 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 최소 스패팅트리 3. 소스 코드 #include #include #include #include using namespace std; int N, M, ans, max_cost; int parent[100005]; vector edges; int Find(int x) { if (parent[x] == x) return.. 2023. 9. 12. [백준 C++] 12100번 : 2048 (Easy) 1. 문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2. 알고리즘 분류 구현 브루트포스 알고리즘 시뮬레이션 백트래킹 3. 소스 코드 #include #include #define INF 987654321 using namespace std; int N; int map[20][20]; int map_origin[20][20]; int ans = -INF; vector path;// 이동 방향 void init_.. 2023. 9. 12. [백준 C++] 1197번: 최소 스패닝 트리 1. 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 최소 스패닝 트리 3. 소스 코드 #include #include #include #include using namespace std; int parent[10005]; bool is_cycle; vector graph; // 부모를 찾는 함수 int find_parent(int x) { if (parent[.. 2023. 6. 10. [백준 C++] 27172번: 수 나누기 게임 1. 문제 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 2. 알고리즘 분류 수학 프루트포스 알고리즘 정수론 소수 판정 에라토스테네스의 체 3. 소스 코드 #include #include #include using namespace std; vector numbers; int scores[1000006]; int cards[1000006]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); co.. 2023. 6. 10. [백준 C++] 21736번: 헌내기는 친구가 필요해 1. 문제 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 3. 소스 코드 #include #include using namespace std; int N, M; int res = 0; char map[601][601]; // map 정보 int visited[601][601]; // 방문 여부 체크 pair I_pos; // 도연이 위치 // 방향 배열(.. 2023. 6. 5. 이전 1 2 3 4 다음
