알고리즘15 [기타] 주어진 수열에서 선택한 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. 에라토스테네스의 체 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. [백준 C++] 20529번: 가장 가까운 세 사람의 심리적 거리 1. 문제 https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 2. 알고리즘 분류 수학 브루트포스 알고리즘 비둘기집 원리 3. 소스 코드 #include #include #include using namespace std; int compareMBTI(string mbti1, string mbti2, string mbti3) { int res = 0; // MBTI 4가지 척도를 비교하면서 다를 경우 거리 1씩 더하기 for (int i = 0; i < 4; i++) { if (mbti1[i] != mbti2[i]) res++; if (mbt.. 2023. 6. 7. [백준 C++] 18110번: solved.ac 1. 문제 https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 2. 알고리즘 분류 수학 구현 정렬 3. 소스 코드 #include #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int res = 0; // 난이도 의.. 2023. 6. 5. [알고리즘] 분할 정복(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 다음
