알고리즘16 [알고리즘] 파스칼 삼각형을 활용한 조합 계산 1. 파스칼 삼각형 2. 소스 코드(C++)int Combination[53][53];// 조합 계산 함수int cal_combination(int n, int r) { if (Combination[n][r]) return Combination[n][r]; // 이전에 계산해놓은 값이 있으면, 바로 반환 else if (n == r || r == 0) Combination[n][r] = 1; // n=r 이거나, r = 0일 때, 1 반환 else { Combination[n][r] = cal_combination(n - 1, r) + cal_combination(n - 1, r - 1) % MOD; // nCr = n-1Cr + n-1Cr -1 } return Combination[n][r];} 2024. 9. 5. [백준 C++] 1799번: 비숍 1. 문제https://www.acmicpc.net/problem/1799 2. 알고리즘 분류백트래킹 3. 소스 코드#include #include #define MAX_N 10using namespace std;int n, ans;int map[MAX_N][MAX_N];bool is_visited_upward_right[2 * MAX_N];bool is_visited_downward_right[2 * MAX_N];// DFS 알고리즘void dfs(int diagonal_index, int bishop_cnt) { /* 우상향의 대각선의 index를 모두 탐색했을 경우, * 우상향의 대각선의 갯수 = 2 * (맵의 크기) - 1 * n = 5 => 대각선의 갯수 = 9개 * 1 2 3 4 5 * .. 2024. 5. 15. [알고리즘] 다이나믹 프로그래밍(DP, Dynamic Programming) 1. 문제https://www.acmicpc.net/problem/1509 2024. 5. 4. [알고리즘] CCW(Counter ClockWise) 기하 알고리즘 1. 개요1. 세 점의 방향관계를 알 수 있는 알고리즘 2. 외적http://www.findmean.com/%EC%88%98%ED%95%99/%EB%B2%A1%ED%84%B0/%EB%B2%A1%ED%84%B0%EC%9D%98-%EC%99%B8%EC%A0%81/ 링크 참조외적의 기하학적 표현정리하자면)1. 반시계방향이면 윗 방향인 (+) 값이 나온다.2. 시계방향이면 아랫 방향인 (-) 값이 나온다.3. 동일한 방향이면 0 값이 나온다.계산식은 아래와 같다.https://snowfleur.tistory.com/98 참조 3. 소스 코드// CCW(Counter ClockWise) 알고리즘int ccw(pair p1, pair p2, pair p3){ // 외적 계산 long long temp = p1.fi.. 2024. 5. 1. [알고리즘] 이진 탐색(이분 탐색, Binary Search) 1. 개요1. O(logN) 시간 복잡도로 해당 배열에서 특정 값을 찾는 알고리즘 2. 알고리즘 코드vector ans;// 이진 탐색 알고리즘int binary_search(int n){ int low = 0; int high = ans.size() - 1; int ret = MAX_N; while (low = n) { ret = min(ret, mid); high = mid - 1; } else low = mid + 1; } return ret;} 3. 문제https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가.. 2024. 4. 14. [알고리즘] 분리 집합(Union-Find) 1. 개요 1. 각 노드들을 그룹을 지을 때 사용하는 알고리즘 2. 알고리즘 코드 int parent[MAX_G]; int Find(int a) { int pA = parent[a]; if (pA == a) return a; return parent[a] = Find(pA); } void Union(int a, int b) { int pA = Find(a); int pB = Find(b); if (pA 2024. 4. 14. [알고리즘] 누적 합 1. 문제 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 2024. 4. 11. [알고리즘] 그리디 알고리즘 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 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.a.. 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 2 다음
