개발자꿀꿀이

문제 외판원 순회 문제는 영어로 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가지의 숫자를 조합 할 수 있는 모든 경우의 수를 쉽게 판단할 수 있다. 이것일 코드로 표현..

문제 연세대학교 수강신청 기간이 시작되었다. 많은 친구들은 비어 있는 시간에 어떤 과목을 추가로 신청할 수 있는지를 궁금해 한다. 이 친구들이 비어 있는 시간에 추가로 신청할 수 있는 과목의 후보 개수를 구해보자. 후보 개수를 세는 것이므로 현재 내 시간표에서 신청할 수 있는 과목끼리 시간이 겹치더라도 모두 세어야 한다. 즉, 월요일 1, 2, 3, 4, 5교시 시간이 비어 있고 한 과목의 시간이 월요일 1, 2, 3, 4교시이고 나머지 한 과목의 시간이 월요일 2, 3, 4, 5교시라면 2과목 모두 후보가 될 수 있다. 풀이 비트 마스크를 이용하여 풀이를 하였다. 예제를 보면서 풀이를하면 3 4 1 2 3 4 6 5 6 7 8 9 10 4 11 21 31 41 5 8 1 2 3 4 5 6 7 8 7 1..