개발자꿀꿀이

문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자..

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 풀이 하나씩 수열을 직접 선택하면서 하는 경우도 있겠지만, 이렇게 하는경우에는 시간이 오래걸린다. 비트마스킹을 이용해서 수열을 만들 수 있다. 만약 n 이 5라면 00001 ~ 11111 까지로 표현된 2진수를 이용해서 생각해보면 5번째 4번째 3번째 2번째 1번째 0 0 0 0 1 위와 같은 방식으로 생각하면된다. 00001 이라면 1번째 숫자만 선택하는 것이다. 00011 이면 1번째 2번째 숫자를 선택하여 이 둘의 합을 구하면 된다. 이렇게 하면 5가지의 숫자를 조합 할 수 있는 모든 경우의 수를 쉽게 판단할 수 있다. 이것일 코드로 표현..