알고리즘16 [알고리즘] 배낭 문제 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. [기타] 주어진 수열에서 선택한 3개의 값의 합이 0에 가장 가깝게 선택하는 방법 1. 유사 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2. 소스 코드 Key Point) 1. 투 포인터 알고리즘을 활용하기 위해 정렬한다. 2. 3개의 값을 비교할 때는 하나를 정해 놓고 2개의 값을 '투 포인터' 알고리즘을 통해 계산한다. #include #include #include using namespace std; long long arr[5000]; long long ans[3]; int main(.. 2023. 10. 3. 투 포인터(Two Pointer) 알고리즘 1. 개요 1. '부분 연속 수열' 관련된 알고리즘 2. 리스트에 순차적으로 접근해야 할 때 2 개의 점의 위치를 기록하면서 처리하는 알고리즘 3. 시간 복잡도 = O(N) 2. 투 포인터 대표 예제 위의 수열에서 연속 부분 수열의 합이 5가 되는 부분 수열을 구하시오. 3. 알고리즘 동작 원리 4. 소스 코드 (C++) #include using namespace std; int main(){ int N, M, arr[10000]; cin >> N >> M; for(int i=0; i> arr[i]; } int answer = 0, sum = 0, s = 0, e = 0; while(s= M){ sum -= arr[s]; s++; }else{ sum += arr[e]; e++; } if(sum == M.. 2023. 10. 3. 에라토스테네스의 체 1. 개요 1. 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 2. 시간 복잡도 = O(n) 2. 방법 step 1) 숫자 1 ~ 100 쓰기 step 2) 소수도, 합성수도 아닌 유일한 자연수 1을 제거 step 3) 2를 제외한 2의 배수를 제거 step 4) 3을 제외한 3의 배수를 제거 step 5) 4는 뛰어넘고, 5의 배수를 제거 step 6) 위의 방법과 동일하게 제거해나간다. 3. 소스 코드 #include constexpr int MAX=1000001; bool prime[MAX]; void eratosthenes(){ memset(prime, false, MAX);//배열을 초기화한다. prime[2]=true;//2는 소수다. prime[3]=true;//3은 소수.. 2023. 10. 3. [알고리즘] 위상 정렬(Topological Sorting) 1. 개요 및 대표 문제 1. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘 2. 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 수행 3. 시간 복잡도 = O(V + E) 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. 위상 정렬의 대표 예시 위의 이미지처럼 작업의 순서가 정해져 있을 때 작업을 정렬해주는 알고리즘이 바로 '위상 정렬'이다. .. 2023. 10. 2. [알고리즘] 분할 정복(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. 이전 1 2 다음
