![]()
저번 게시물에서는 외판원 순회 문제를 동적 계획법을 이용해서 풀어보았다. 이번에는 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)의 쌍으로 주어진다. 출력 첫 번째 줄에 해밀턴 회로의 개수를 출력한다. 두 번째 줄부터 입력에서 주어진 출발정점 각각에 대해 해밀턴 경로의 수를 한 줄에 하나씩 출력한다. ..
![]()
문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbers return [6, 10, ..
![]()
문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다. x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다. 다음은 6 x 6 크기 행렬의 예시입니다. 이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은..
![]()
문제 설명 개발자를 희망하는 조르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야 하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리 1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 예를 들어, 5개의 대기실을 본 조르디는 각 대기실에서 응시자들이 거리두기를 잘 지키고 있는지 알고 싶어 졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실 별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실 별로 거리두..
![]()
문제 교재와 강의자료를 참고하여 0-1 배낭 문제를 해결하는 Algorithm 5.7을 완성하시오. 단, 문제의 입력은 단위무게당 이익순으로 정렬되어 있지 않음에 유의하시오. 또한, 알고리즘의 출력은 알고리즘의 실행 단계별로 상태 공간 트리의 각 노드에서의 상태를 출력해야 함에 주의하시오. 입력 첫번째 줄에 아이템의 개수 n과 배낭의 무게 W가 주어진다. 두 번째 줄에 n개의 아이템 무게 w [i]가 주어진다. 세 번째 줄에 n개의 아이템 이익 p [i]가 주어진다. 출력 첫 번째 줄부터 한 줄에 하나씩 상태공간트리를 방문하는 노드의 상태를 출력하시오. 노드 상태는 다음과 같은 순서로 출력한다. i weight profit bound maxprofit 상태를 출력하는 순서는 Algorithm 5.7의 노..
