전체 글103 [알고리즘] 분할 정복(Divide and Conquer) 1. 정의 - 작은 문제로 분할하여 문제를 해결하는 방법 1) 분할 : 본 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 나누기 2) 정복 : 하위 문제를 각각을 재귀적으로 해결 3) 조합 : 하위 문제들의 답을 합쳐서 본 문제를 해결 2. 상세설명 - 특정 수나 행렬의 거듭제곱을 구할 때 사용 => 시간 복잡도 O(n)에서 O(logN)으로 줄일 수 있음 3. 적용 사례 3-1) 거듭제곱 long long power(long long n, long long m) { long long ret = 1; while (m) { if (m & 1) ret = ret * n % MOD; m = m / 2; n = n * n % MOD; } return ret; } 3-2) 행렬 거듭제곱 long long m.. 2022. 12. 8. [백준 C++] 13172번 : Σ 1. 문제 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 2. 알고리즘 분류 수학 정수론 분할 정복을 이용한 거듭제곱 모듈로 곱셈 역원 페르마의 소정리 3. 소스 코드 #include #define MOD 1000000007 using namespace std; // n^m을 구하는 함수 // 분할 정복을 이용한 거듭제곱 long long power(long long n, long long m) { long long ret = 1; while (m) { if (m & 1) ret = ret * .. 2022. 12. 8. [백준 C++] 12851번 : 숨바꼭질 2 1. 문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 3. 소스 코드 #include #include #define INF 987654321 using namespace std; int dist[200005]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //.. 2022. 12. 4. [백준 C++] 11054번 : 가장 긴 바이토닉 부분 수열 1. 문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 3. 소스 코드 #include #include using namespace std; int N, ans; int arr[1000]; int dp_asc[1000]; int dp_dec[1000]; int dp_bitonic[1000]; void input() { cin >> N; for (int i = 0; i > arr[i]; } voi.. 2022. 12. 2. [백준 C++] 10830번 : 행렬 제곱 1. 문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 알고리즘 분류 수학 분할 정복 분할 정복을 이용한 거듭제곱 선형대수 3. 소스 코드 #include using namespace std; long long N, B; long long matrix[5][5]; long long ans[5][5]; void input() { // N : 행렬의 크기, B : 거듭제곱 횟수 cin >> N >> B; for (int y = 0; y < N; y++).. 2022. 11. 30. [백준 C++] 15652번 : N과 M(5) 1. 문제 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 2. 알고리즘 분류 백트래킹 3. 소스 코드 #include #include #include using namespace std; int N, M; int visited[10];// 사용된 숫자 체크(중복 방지용) vector inputs; vector nums; // 수열을 구하는 함수 // lv : 뽑은 숫자의 갯수 void permutation(int lv) { // M개.. 2022. 11. 29. [백준 C++] 15652번 : N과 M(4) 1. 문제 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 알고리즘 분류 백트래킹 3. 소스 코드 #include #include using namespace std; int N, M; vector nums; // 순열을 구하는 함수 // lv : 뽑은 숫자의 갯수, num : 이전에 뽑았던 수 void permutation(int lv, int num) { // M개의 숫자를 뽑을 경우, 출력 if (lv == M) { // 해당 순열.. 2022. 11. 29. [백준 C++] 15650번 : N과 M(2) 1. 문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 2. 알고리즘 분류 백트래킹 3. 소스 코드 #include #include using namespace std; int N, M; vector nums; // 수열을 구하는 함수(DFS 이용) // lv : 현재 뽑은 숫자의 갯수, num : 이전에 뽑았던 수 void permutation(int lv, int num) { // M개 까지 숫자를 뽑았을 때, 끝내기 if (lv ==.. 2022. 11. 29. [백준 C++] 2407번 : 조합 1. 문제 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 2. 알고리즘 분류 수학 조합론 임의 정밀도 / 큰 수 연산 3. 소스 코드 #include #include using namespace std; // 조합 계산 결과 테이블 string table_combi[105][105]; // 큰 수 더하는 함수 // num1, num2의 수는 거꾸로 저장되어있음 ex) 123 => "321" string add(string num1, string num2) { string ans = ""; int sum = 0; int size = max(num1.size().. 2022. 11. 29. [백준 C++] 9935번 : 문자열 폭발 1. 문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 2. 알고리즘 분류 자료 구조 문자열 스택 3. 소스 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 문자열 입력 string s1, s2, ans = ""; cin >> s1 >> s2; // 각.. 2022. 11. 29. 이전 1 ··· 7 8 9 10 11 다음
