푸으름

Algorithm 공부 #12 - 정수론(유클리드 호제법과 확장 유클리드 호제법) 유클리드 호제법(최대 공약수 구하기) ● 큰 수를 작은 수로 나누는 MOD연산 ● 앞 단계에서 나왔던 작은 수와 나머지를 다시 MOD연산 ● 이렇게 반복하면서 나머지가 0이 되면 그 순간의 작은 수를 최대 공약수로 선택 ex) 270과 192 270 mod 192 = 78 192 mod 78 = 36 78 mod 36 = 6 36 mod 6 = 0 => 0이 되는 순간 6을 return, 즉 270과 192의 최대공약수는 6 백준 1934번 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수..

Algorithm 공부 #11 - 정수론(소수 구하기&오일러 피) 소수 구하기(에라토스테네스의 체 원리) ● 구하고자 하는 소수의 범위만큼 1차원 배열을 생성 ● 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 숫자의 배수들을 배열에서 모두 지우기 ● 처음으로 선택된 숫자들은 지우지 않고 반복문을 N의 제곱근까지만 돌림 ● 시간 복잡도는 O(Nlog(logN)) 백준 1929번 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ※ N의 범위가 1,000,..

Algorithm 공부 #10 - 그리디 알고리즘 그리디 알고리즘(Greedy Algorithm) ● 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘 ● 동적 계획법보다 구현하기 쉽고 시간복잡도가 우수함 ● 하지만 항상 최선의 해를 보장하지 못하기 때문에 전제 조건을 잘 살펴보아야 함 백준 11047번 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net ※..

Algorithm 공부 #09 - 탐색(이진 탐색) 이진 탐색(Binary Search) ● 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘 ● 구현 및 원리가 비교적 간단하고 시간 복잡도는 O(logn) ● 탐색 방법 1. 현재 데이터셋에서 중앙값 찾기 2. target이 중앙값보다 작다면 end=middle-1 3. target이 중앙값보다 크다면 start=middle+1 4. target==중앙값일 때 데이터 탐색을 종료 백준 1920번 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤..