WannaBeDeveloper

2098번: 외판원 순회 www.acmicpc.net 이 문제는 Traveling Salesman Problem(TSP)라 불리는, NP-complete 문제들 중 대표적인 문제로, 각 간선에 비용이 주어진 완전 그래프에서 모든 점을 한 번씩만 지나는 사이클 중 비용의 합의 최솟값을 구하는 문제이다. 위에서 말했듯이 이 문제는 NP-complete에 속해서 polynomial time 안에 해결하는 알고리즘이 알려진 게 없다. 그래서 입력의 크기가 작은 경우에만 적절한 시간 내에 해결이 가능하다. 이 문제는 이전의 할 일 정하기 1 문제처럼 DFS와 dynamic programming을 이용하면 상대적으로 효율적인 알고리즘을 만들 수 있다. 백준 1311번 : 할 일 정하기 1 in Python 1311..

1311번: 할 일 정하기 1 www.acmicpc.net 이 문제는 N명의 사람에게 N개의 일을 하나씩 담당하게 할 때 모든 일을 하는데 필요한 비용의 최솟값을 구하는 문제이다. 만약 단순히 모든 경우의 수를 고려해 일을 배분한다고 하면 N!가지의 경우의 수를 모두 고려해야 하므로 총 걸리는 시간은 O(N^N)으로 매우 비효율적이다. 그래서 이 문제는 dynamic programming을 활용해 보다 효율적인 알고리즘을 생각할 필요가 있다. 즉, 이전에 계산한 결과를 저장할 배열을 만들 필요가 있는데, 이 계산 결과라 함은 일을 맡긴 사람의 수 i와 각 사람마다 맡긴 일의 집합 S에 대해 가능한 비용 중 최솟값을 의미한다. 예를 들어 N = 6일 때 4명의 사람에게 1, 3, 4, 6이라는 일을 맡겼다..

11723번: 집합 www.acmicpc.net 이 문제는 공집합이 주어졌을 때 여러 연산을 수행하는 프로그램을 만드는 문제이다. 만약 연산의 수가 적은 경우에는 길이가 20인 배열을 만들어서 각 연산을 구현하면 되지만, 연산의 수가 최대 300만 번까지 주어지기 때문에 이를 시간 내에 구현하려면 다른 방식으로 집합을 나타내야 한다. 그래서 여기서는 비트 자료형을 사용해 집합을 나타낸다. 예를 들어 1~20까지 들어갈 수 있는 집합에 3, 5, 7, 9가 들어있으면 이 집합을 비트 표현으로 00000000000101010100로 나타낸다. 즉, 비트 자료형의 각 자리수가 1인 경우 집합 내에 자리수에 해당하는 수가 들어있다는 것을 의미한다. 이렇게 집합을 표현하면 위 문제에서 주어지는 연산을 O(1) 시..