알고리즘

[알고리즘] 버킷 정렬

[Bucket Sort (버킷 정렬)] 버킷 정렬은 N개의 버킷으로 나눈 뒤, 각 버킷 안에 하나 이상의 값을 저장한다. 예를 들어보어 사과(2개), 배(2개), 망고(3개), 수박(1개) 총 8개의 과일이 있다고 가정해보자. 버킷 정렬에서는 다음과 같이 과일의 정보를 저장한다. 숫자 범위를 기준으로 버킷의 정렬 순서를 정할 수도 있다. 예를 들어 29, 25, 3, 49, 9, 37, 21, 43 이라는 숫자가 있으면 이를 10단위로 나누어 관리할 수 있다. [구현] 두 번째 예시를 기준으로 의사 코드를 작성하면 다음과 같다. function bucketSort(array, k) buckets ← N 크기의 빈 배열을 선언한다. M ← 가장 큰 숫자를 M으로 선언한다. for i = 1 to lengt..

[백준] 14719 빗물 (JAVA)

✉️문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 📝 접근 왼쪽에 있는 기둥의 최대값(LM)과 오른쪽에 있는 기둥의 최대값(RM)을 구한다. LM과 RM의 최소값을 구한다. 최소값 - 현재 인덱스의 높이 🗝 문제풀이 public class Q14719_B { static int[] heights; public static void main(String[] args) { Scanner sc = new Scanner(Sys..

[알고리즘] 최대 공약수, 최소공배수

최대 공약수를 구하는 알고리즘 중 가장 유명한 유클리드 호제법에 대해 알아보자. 유클리드 호제법 a를 b로 나눈 나머지를 r이라고 할 때, GCD(a, b) = GCD(b, r)이다. r이 0일 때의 b가 최대 공약수이다. 위의 정의를 GCD(24, 16)을 통해 알아보자. 1. 24(a)를 16(b)로 나눈다. 24 % 16 = 8(r) 2. 16(b)를 8(r)로 나눈다. 3. 8(b)와 0(r)을 계산해야 하는데 r = 0이므로 이 때의 b값인 8인 최대 공약수가 된다. int gcd(int a, int b) { while ( b != 0) { int r = a % b; a = b; b = r; } return a; } 최소공배수 최소공배수는 LCM이라고 하며 GCD를 응용해서 구할 수 있다. 최소..

[알고리즘] 소수 알고리즘

소수를 구하는 알고리즘을 알아보자. 소수의 정의를 이용한 방법 N이 소수이면 2 ~ (N-1)로 나누어 떨어지지 않는다. 이 경우 2부터 N-1까지 연산이 필요하기 때문에 O(N)의 시간복잡도가 걸린다. 약수의 특징을 이용한 방법 N이 소수가 되려면, 2이상이고, N/2 이하의 자연수로 나누어 떨어지면 안된다. (N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같다) 여전히 O(N)의 시간 복잡도를 갖는다. 약수의 특징을 이용한 방법2 모든 수의 약수는 루트 N을 기준으로 대칭을 이룬다. 루트 N의 값 왼쪽에 있는 값을 기준으로 값 들을 조합해 대칭 오른쪽에 있는 수의 값을 구할 수 있다. O(루트 N)의 시간 복잡도를 가진다. 컴퓨터에서 실수는 근사값을 나타내기 때문에, 루트 N과 같은 경우는 다음 ..

[백준] 17427 약수의 합2 (Java)

✉️문제 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 📝 접근 https://brightmango.tistory.com/345 [알고리즘] 약수 알고리즘 A와 B라는 숫자가 있을 때 A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 이런 약수를 구하는 방법은 3가지가 있다. 모든 자연수로 나누는 방법 : O(n) 말 그래도 1부터 N까지 모든 수로 나누어 brightmango..