푸으름

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 ≤..

Algorithm 공부 #07 - 정렬(병합 정렬과 기수 정렬) 병합 정렬(Merge Sort) ● 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 ● 시간 복잡도는 O(nlogn) 백준 2751번 수 정렬하기2 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net ※ N의 최대 범위가 1,000,0000이므로 O(nlogn)의 병합 정렬을 사용해서 문제 풀기 ※ ● 병합 정렬 함수 슈도 코드 병합 정렬(..