알고리즘
-
[알고리즘] Traveling Salesperson problem (외판원 문제) - by Dynamic Programmingcase Computer : 2010. 11. 10. 16:01
알고리즘 시간에 가장 많이 예기하는 알고리즘 중에 하나가 이 문제가 아닐까 싶다. 문제는 회사원이 A도시부터 시작하여 모든 도시를 한번씩한 거처서 다시 A도시로 들어오는 방법이다. 그리고 그과정은 최적이어야 한다. 이 문제를 알고리즘을 이해하는것 그다시 어렵지 않다. 하지만 알고리즘을 직접 코드화 하는게 상당히 까다롭다. 많은 사람들이 집합을 어떻게 표현해야되나에 대해 고민한다. 그냥생각하기에는 배열? 정도가 생각나지만 배열로 하기에는 무리가 있다. 여기에서 유한 집합을 표현한다고 한다면 비트로 표현하는게 좋지 않을까 한다. 일단 비트로 표현하는 방법과 비트연산을 알아야 한다 이방법은 인터넷에 많이 나와있다. 비트연산자 혹은 논리연산자라고 검색하면 나온다 그래도 못찾겠다면 http://winapi.co...
-
[알고리즘] ACM - 소인수 분해 문제case Computer : 2010. 10. 17. 19:26
조건.. 1. 곱해서 자신이 되는 인수들의 집합의 경우의 수를 찾아 출력하고 인수들의 집합을 출력한다.(1과 자기자신 제외) 2. 인수들의 집합이 출력될때는 사전식으로 정렬(오름차순)되어 출력한다. 3. 중복되는 집합 경우(3X4, 4X3)은 경우의 수를 한가지로 둔다. main code void Factorize() { // 1은 인수에서 제외하므로 2부터 시작 // 끝은 해당 수의 제곱근까지만 카운트 for(int i=2; i = Factors[Fac_index-1]) || (Fac_index == 0)) { // 나눈몫을 다음 배열에 넣음 // 인수는 원래 값을 대체함. // 배열에는 인수들이 들어간다. (오름차순으로) Factors[Fac_index+1] = Factors[Fac_index]/i;..