![]()
문제가 영어라 내가 이해한? 영어대로 해석해보겠다. 문제 가방이 있고 물건이 있다. 가방에는 최대 2개의 물건을 담을 수있다. 가방의 용량을 넘어서는 물건을 담을 수 없다. 입력 첫 번째 입력은 물건의 개수 두 번째 입력은 가방의 용량 문제 해석 물건의 무게가 큰 순서대로 정렬함. 가방의 개수가 최소화되는 방법은 가장 큰 거를 우선 담고, 그 빈자리에 담을 수 있는 가장 작은 무게를 담는다. 만약 담았다면 담았던 물건은 제외시켜준다. 코드 #include #include #include using namespace std; int big(int i, int j) { return i > j; } int N, W, totweight = 0; vector profit; vectorinclude; int Cou..
![]()
문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100 이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 문제 해석 소수는 1과 자기 자신만을 약수로 가지는 특정한 숫자이다. 반복문을 돌려서 1과 자기자신을 제외한 수를 나눠서 나머지가 0이면 그 수는 소수가 아닐 것이다. 코드 /* 주어진 N개 중에서 소수가 몇개인지 찾아서 출력하는 프로그램을 작성하시오 입력 첫줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000이하의 자연수 소스의 개수를 출력 소수..
![]()
문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 출력 첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다. 예제 입력 1 2 4 2 예제 출력 1 8 예제 입력 2 1 2 예제 출력 2 4 예제 입력 3 6 3 4 2 12 6 8 예제 출력 3 24 예제 입력 4 14 14 26456 2 28 13228 3307 7 23149 8 ..
![]()
알고리즘에 도전해보는 방식 2가지 1. 문제를 푸는 더 효율적인 알고리즘을 설계하기 2. 더 효율적인 알고리즘 개발이 불가능함을 증명하기 계산 복잡도는 주어진 문제를 풀 수 있는 가능한 모든 알고리즘에 대한 연구이다. 문제를 푸는 모든 알고리즘의 효율성(복잡도)의 하한을 구하는 것이다. 과연 이 알고리즘이 최선일까? 더 효율적인 알고리즘은 없는가?를 연구하는 것 Finding the Largest Key : Problem : Find the largest key in the arrays of size n, indexed from 1 to n Outputs : variable large, whose value is the largest key in S. void find_largest(int n, vect..
![]()
저번 게시물에서는 외판원 순회 문제를 동적 계획법을 이용해서 풀어보았다. 이번에는 Branch & Bound(분기한정법)을 이용해서 풀 예정이다. 문제의 목표는 동일하게 출발점에서 모든 노드를 각 한 번씩 방문하고 다시 출발점으로 되돌아오는 최소한의 비용을 가지는 경로를 찾는 것이다. 최고 우선 검색을 사용하기 위해서 각 마디의 한계값을 구할 수 있어야 한다. 0-1 배낭 채우기 문제에서는 총무게가 W를 넘지 않도록 하면서 이익을 최대로 하는 게 목표였기 때문에, 주어진 마디에서부터 뻗어나가서 얻을 수 있는 이익의 상한을 계산하였다. 그리고 어떤 마디에서 당시 최대 이익보다 한계값이 큰 경우에 그 마디를 유망하다고 판단했다. 외판원 문제에서는 주어진 마디에서부터 뻗어나가서 얻을 수 있는 여행경로 길이의 ..
![]()
문제 목표 n개의 도시로 판매 출장을 계획하고 있는 외판원이 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아오는 가장 짧은 여행길을 찾는 것. --> 최단 경로 문제 --> 출발한 도시로 다시 돌아오는 부분에서 해밀턴 회로와 동일한 개념. 이 문제는 weighted, directed graph이다. 각 도시에서 도시로 가는 비용이 있고, 방향이 정해져 있다.(여기서 비용은 음이 아닌 정수로 가정한다) 만약 v1을 출발점으로 잡는다면 가능한 경로와 그에 비용은 아래와 같다. [v1->v2->v3->v4->v1] = 22 [v1->v3->v2->v4->v1] = 26 [v1->v3->v4->v2->v1] = 21 v1에서 출발할때의 최적의 경로는 [v1->v3->v4->v2->v1]이고 그 비용은 2..
![]()
되추적 알고리즘을 이용한 0-1 배낭 채우기를 앞에서 해보았다. 이번에는 분기한정을 이용한 0-1 배낭 채우기를 해보겠다. 되추적 알고리즘과 어떤 차이가 있는지를 중점으로 보면 될 것이다. -앞선 문제와 동일하게 n= 보석의 개수 W= 배낭의 용량 n=4, W=13 p(profit)=[40,30,50,10], w(weight)=[2,5,10,5], p/w(단위 무게별 이익)=[20,6,5,2] 1. 앞선 0-1 배낭 채우기 문제와 같이 무게별 이익이 큰 순서대로 재 정렬한다. 2. 되추적 알고리즘과 상태 공간 트리를 구성한다. 3. 트리는 (profit, totweight, bound)로 이루어진다. profit은 내가 가방에 담은 이익 totweight은 내가 가방에 담은 무게 bound는 내가 탐색한..
![]()
Branch & Bound(분기 한정) 알고리즘은 Backtracking(되추적) 알고리즘을 개선한 알고리즘이다. 차이점 트리횡단방법에 구애받지 않음. 최적화 문제를 푸는데 만 쓰인다. 분기 한정 알고리즘은 어떤 마디가 유망한 지를 결정하기 위해서 그 마디에서 한계값을 계산한다. 이 한계값은 그 마디 아래로 확장하여 구할 수 있는 해답 값의 한계(Bound)를 나타낸다. 그 한계값이 찾은 최고 해답 값보다 더 좋지 않으면 그 마디는 유망하지 않다.(nonpromisin), 그 한계값이 찾은 최고 해답 값보다 더 좋으면 유망하다.(promising) 분기 한정 알고리즘은 마디들의 한계값을 비교하여 그중에서 가장 좋은 한계값을 가진 마디의 자식 마디를 방문한다.(유망도가 높은 자식을 방문함). --> 되추적..
![]()
문제 n * m 체스보드에서 기사의 여행 문제를 해결하는 백트래킹 알고리즘을 구현하시오. Knight's Tour 문제는 해밀턴 경로(path)와 해밀턴 회로(circuit, cycle)를 찾는 문제로 구분할 수 있다. 해밀턴 회로는 출발 정점과 무관하게 회로의 수를 구할 수 있고, 해밀턴 경로는 출발 정점에 따라 가능한 경로의 수가 달라짐에 유의하시오. 입력 첫 번째 줄에 체스보드의 크기 n(행의 크기)과 m(열의 크기)이 주어진다. 두 번째 줄에 출발 정점의 개수 T가 주어진다. 이후로 T개의 출발정점이 i(row), j(col)의 쌍으로 주어진다. 출력 첫 번째 줄에 해밀턴 회로의 개수를 출력한다. 두 번째 줄부터 입력에서 주어진 출발정점 각각에 대해 해밀턴 경로의 수를 한 줄에 하나씩 출력한다. ..
