본문 바로가기

백준 알고리즘/백준 CLASS 537

[백준 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.
[백준 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++] 10942번: 팰린드림? 1. 문제https://www.acmicpc.net/problem/10942 10942번: 팰린드롬?총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.www.acmicpc.net 2. 알고리즘 분류다이나믹 프로그래밍 3. 소스코드#include #include #include using namespace std;vector v;int dp[2003][2003];// 팰린드롬인지 확인하는 알고리즘bool is_palindrome(int start, int end) { // 시작 문자열과 끝 문자열이 같고, 시작점과 끝점 문자열을 제외했을 때, 그 문자열이 팰린드롬일 경우, True if (v[start] =.. 2023. 9. 28.
[백준 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.

티스토리툴바