옛날 블로그

Linde–Buzo–Graykmeans와 이진분류의 강점만 가져왔다고 하는데 실무에서 써본적도 본적도 없다.논문은 돈을 내야 보인다.

왜 equals말고도 hashcode를 구현해야하는지? 아래 아주 잘 설명되어있다. http://anster.tistory.com/160 결론은.equals를 구현하면 안전하게 hashcode도 구현해야한다는것.hashcode대상이 되는것은 immutable(변경불가능)해야 한다는것.

배낭문제는 도둑놈 털어가기 알고리즘과 같다. 배낭이 20Kg짜리를 가져갔는데 이게 왠걸 방에 뭐 비싸보이는게 덕지덕지 있다. 다만 무게와 가치를 잘 따져서 가져가야하는데, 보통은 무게대비 가치가 많은걸 가져가면 되겠지만 만약 이게 100Kg 짜리 다이아몬드라면 잘라서 가져가지는 못하므로 포기한다. 고속터미널에서 파는 싸구려 가방이라 20Kg가 넘으면 찢어진다고 가정하다. 한번 이렇게 있다고 생각해보자. 부피 : 4 5 12 4 100 2 가치 : 7 10 2 4 100 6 문제는 뭔가 비싸보이는것부터 넣어도 안되고 무게대비 비싼걸을 넣어서도 별로 답이 되지 않는다는 것이다. 이럴때는 나머지 공간에 물건들을 싸서 얻을 수 있는 최대의 가치를 리턴하는 함수를 설계한다. 물건을 가져가지 않는경우는 다음과 같다..

다음의 배열이 있다고 치자. int[] array = {1,4,2,5,6,9,141,552}; 그리고 141이라는 숫자를 빠르게 이진탐색으로 찾아가야 한다. 시그니처는 다음과 같이 잡자 public static int binarySearch (int[] array, int key) 다만 이 메서드에 마구 array를 집어넣으면 안되고, 이진탐색의 경우 필수적인 조건이 sort를 해주어야 한다. array는 다음과 같이 간단하게 sort가 가능하다. Arrays.sort(array); 이제 구현을 해보자 public static int binarySearch (int[] array, int key) { int upper = array.length - 1; int lower = 0; while(upper >..

package algo; import java.util.Stack; public class Hanoi { public static void main(String[] args) { int n = 3; Tower[] towers = new Tower[n]; for (int i = n - 1; i >= 0; i--) { towers[0].add(i); } towers[0].moveDisks(n, towers[2], towers[1]); } class Tower { private Stack disks; private int index; public Tower(int i) { disks = new Stack(); index = 1; } public int getIndex() { return index; } pub..

판매원 알고리즘은 시간이 팩토리얼로 걸리기 때문에 들러야 할 도시가 8번이 넘어간다면 굉장히 오래걸리기 때문에, 완전탐색을 해야 하되 8번 이상은 별 다른 기법을 도입해야한다.제일 적은 거리를 이동해 모든 도시를 도는 방법은 어떻게 되는가? 보통은 다시 되돌아오는 경우를 생각하지만 여기서는 출발지와 도착지를 모두 고려한다. 먼저, 다음과 같이 값들이 있다고 친다. final static int x[] = { 0, 14, 25, 50, 20, 2, 100 }; final static int y[] = {1,1,10,70,40,99,100}; x[0], y[0] 은 시작지점이며x[6], y[6] 은 끝지점이다.시작지점과 끝지점이 결정되었다고 했을때, 중간에 어떤 루트를 타야할지 계산해야한다.일단, dista..

P 문제는 결정 문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합이다. 어떤 결정 문제가 주어졌을 때, 다항식(Polynomial) 시간 이내에 그 문제의 답을 YES와 NO 중의 하나로 계산해낼 수 있는 알고리즘이 존재한다면, 그 문제는 P 문제에 해당된다. nnn자리 이하의 수 a와 b가 주어졌을 때, a가 b의 배수인지를 판정하는 것은 유클리드 호제법을 사용하면 nnn에 대한 다항식 시간에 계산할 수 있으므로, 'a는 b의 배수인가?'하는 문제는 P 문제에 해당된다. NP 문제는 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것을 모아 놓은 집합이다. 정확히 말하면, 어떤 결정 문제의 답이 YES일 때, 그 문제의 답이 YES라는 것을 입증하는 힌트가 주어지면, 그 힌트를 사용해서 그 문제의 답..

길찾기 알고리즘은 숫자가 적을경우는 그냥 사실 루프 몇번 돌려서 만들면 되는데, 다만 그 숫자가 굉장히 커질경우 계산이 느려질수 있다. 1 2 4 1 5 5 2 5 2 1 4 5 2 5 2 1 5 6 1 3 4 2 5 1 1 2 5 2 4 1 2 5 1 4 3 4 위와같이 6 X 6 바둑판같은 길이 있다고 하고, 1) 최소경로로 가야하며 2) 밟고 다니는 숫자의 합이 최대인 길을 찾아야 하며 3) 찾는 속도가 좀 빨라야한다. 사실 알고리즘에 있어서 기본은 재귀를 어떻게 잘 돌리냐에 따른건데, 보통사람은 동적프로그래밍을 먼저 생각해내겠지만, 알고리즘을 열심히 푸는 사람들에게는 재귀가 항상 먼저 답으로 다가오는 듯 하다. 위의 경우에서는 다음과 같은 경우로 길을 선택한다고 볼수있는데, - 처음인경우 (즉 1..

조합은 의외로 재미있는 구조이다. 예를들어 지구멸망의 날 수많은 사람들 중 대충 네명만 뽑아서 데려가야 한다고 하자. 순서는 상관없고 그냥 대충 성별상관없이 뽑으면 된다. 그렇다면 조합은 이렇게 된다. 6,000,000,000C4 60억 지구 인구 중, 4명을 뽑는 조합이다. 이를 구하기위해서 고딩때는 60억인 n! 을 팩토리얼 한 숫자를 (r! * (n-r)!) 으로 나눠서 계산하고는 했다. 하지만, 팩토리얼도 상당한 계산의 부하가 걸리는 작업이다. 컴퓨터로 코딩을 하려면 매력이 떨어진다. 다만 실질적으로 고딩때 잘 안써먹던 조합을 구하는 공식이 있다. nCr = n-1Cr-1 + n-1Cr 어차피 손으로 풀려면 팩토리얼 분자 분모 작대기 긋고 해야한다. 다만 컴퓨터로 구하게 될때는 간단한 재귀식을 이..

1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자 1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1 여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다. 1-2-3-4 1-2-4-3 1-3-2-4 1-3-4-2 .... 4-3-2-1 이렇게 숫자를 뒤에서부터 섞으면, 훌륭한 순열의 모든 경우를 구할수 있다. 그렇다면 이를 알고리즘으로 어떻게 구현할 것인가? 은근히 골이 땡겨온다. 출처 : http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/ 이럴때는 위의 그림을 한번 보다. ABC의 알파벳을 재귀적으로 푸는 방법이다. ABC 중 첫번째 알파벳을 뭘로 할..