알고리즘15 [백준 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. BFS(너비 우선 탐색) 문제 모음집 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmi.. 2024. 4. 3. [알고리즘] DFS (깊이 우선 탐색) 1. DFS 문제 모음집https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주www.acmicpc.nethttps://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을www.acmicpc.nethttps://www.acmicpc.net/.. 2024. 4. 3. [알고리즘] 배낭 문제 1. 배낭 문제 알고리즘 문제 모음집 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$,.. 2024. 4. 3. 이전 1 2 다음
