알고리즘/유형정리

[알고리즘] 카데인 알고리즘

카데인 알고리즘 DP(Dynamic Programming)기법 중 하나로 연속적인 수의 나열에서 최대합 또는 곱을 구하는데 사용된다. 아이디어 [-2, 3, -1, 2]의 숫자가 있다. 이 배열에서 최대 부분합을 구해보자. [-2, 3, -1, 2]의 최대 부분합을 구하기 위해서는 [-2, 3, -1]의 최대 부분합을 알아야 한다. 이를 알기 위해서는 [-2, 3]의 최대 부분합을 알아야 한다. 마지막으로 [-2]의 최대 부분합을 알아야 한다. 이렇게 큰 집합을 작은 부분 집합으로 나누어서 풀이해 정복하는 DP 기법을 이용한다. 슈도 코드 function kadaneAlgorithm(nums) { var curSum = 0, max = INT_MIN // i = 1 부터 nums.length - 1까지 ..

[알고리즘] 버킷 정렬

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

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

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

[알고리즘] 약수 알고리즘

A와 B라는 숫자가 있을 때 A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 이런 약수를 구하는 방법은 3가지가 있다. 모든 자연수로 나누는 방법 : O(n) 말 그래도 1부터 N까지 모든 수로 나누어 보는 방법이다. 10이라는 숫자의 약수를 알기 위해 10번의 나눗셈 연산이 필요하다. 약수가 되는 성질을 이용한 방법 : O(√n) C가 A의 약수라면, A/C도 A의 약수가 된다. 즉 1 ~ √n 까지 구하면 된다. 배수의 성질을 이용한 방법 약수인 수보다 약수가 아닌 수가 더 많이 존재한다. 따라서 배수의 성질을 이용하면 약수만 빠르게 구할 수 있다. 알고리즘 문제 풀이에서는 주로 이 알고리즘이 사용된다. 다음 그림과 함께 6을 기준으로 어떤 성질을 가지고 있는지 확인해보자. 6이하의 자연수 ..

[알고리즘] 동전 교환 알고리즘

동전 교환 알고리즘 최소의 갯수로 거스름돈을 주는 방법에 대해 알아보자. 그리디 알고리즘 동전교환 문제를 풀기 위해 그리디 알고리즘을 사용할 수 있다. 하지만 그리디 알고리즘은 가장 적은 동전 수의 최적해를 항상 찾는 것은 아니다. 예를 들어보자, 동전의 종류가 [1, 3, 4] 이렇게 존재하고 9원을 거스름돈으로 준다고 하면, 그리디 알고리즘은 4원 1개, 3원 1개, 1원 2개를 선택할 것이다. 하지만 3원 3개를 거스름돈으로 주는 방식이 가장 적은 동전의 개수를 이용한 최적해이다. 그렇다면 항상 최적해를 찾기 위해 어떤 알고리즘을 이용해야 할까? DFS DFS 알고리즘을 이용할 수 있다. 위와 같이 [1,3,4] 동전 종류가 있고, 9원을 거스름돈으로 거슬러 준다고 해보자. 각 코인마다 3개의 가지..