알고리즘
-
알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem) 공부하기알고리즘 2020. 11. 15. 00:33
이전에는 동적계획법을 이용하여 0-1 knapsack 문제에 대해 다루었다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 이번 포스팅은 좀 더 효율적인 0-1 knapsack problem 알고리즘에 대해 알아본다. 기존의 0-1 knapsack problem은 상태공간트리에서 되추적을 이용하였다. 이 문제는 최댓값을 구하는 최적화 문제이기때문에 검색이 완전히 끝나기 전까지는 마디가 해답을 포함하고 있는지 알지 못한다...
-
알고리즘: 해밀턴 회로문제(Hamiltonian Circuit Problem)(Backtracking 문제)알고리즘 2020. 11. 12. 19:17
해밀턴 회로문제(HCP)를 알아보기전에 외판원 문제(TSP)에 대해 간단히 알아보자 이전에 외판원 문제(TSP)에 대해 포스팅했었다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) 외판원이 출장시간을 줄이기 위해 거주하고 있는 도시에서 출발하여 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아온다고 했을 때 가장 짧은 여행길을 seungjuitmemo.tistory.com 외판원 문제(TSP)의 경우 가장 빠른 방법으로 20개의 도시를 모두 돌고 돌아오는데 걸리는 시간을 계산하면 약 45초가 소요된다. (brute force를 이용하면 19!으로 3800년이상 걸린다) 이번에는..
-
알고리즘: 그래프 색칠하기(m-coloring)(Backtracking 문제)알고리즘 2020. 11. 12. 17:55
m-coloring 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 같지 않도록 m개의 다른 색으로 칠하는 방법을 찾는 문제다. 예를 들어, 이 그래프에서는 두 가지 색으로 문제를 푸는 것은 불가능하다. 세가지 색을 이용하면 6가지의 해답을 얻을 수 있다 그래프 색칠하기의 주요 응용분야는 지도 색칠하기이다. (이외에도 GSM에서 주파수 할당문제, Aircraft scheduling, final exam timetable등에 사용된다) 여기서 우리는 지도를 평면그래프(planar graph)로 나타낼 수 있는데 평면그래프란 두 개의 이음선이 서로 교차하지 않도록 그린 그래프를 말한다. 다음은 왼쪽의 지도를 평면그래프로 나타낸 것이다. (만약 v1과 v5를 연결하거나 v2와 v4를 연결한다면 평면 그래..
-
알고리즘: 부분집합의 합(sum of subset) 공부하기!(Backtracking 문제)알고리즘 2020. 11. 9. 23:46
부분집합의 합 구하기 문제에서는 양의 정수(무게) wi가 n개와 양의 정수 W가 있다. 합이 W가 되는 정수의 부분집합을 모두 찾는 것이 목표다. 전에 다루었던 knapsack문제와 유사하지만 부분집합의 합 구하기 문제에서는 조건을 만족하는 모든 집합을 찾는다는 점에서 다르다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 예를 들어보자 n = 3, W =6 w1 = 2, w2 = 4, w3 = 5 이라 할때 각 노드들의..
-
알고리즘: 몬테칼로 알고리즘을 이용한 효율성 추적!알고리즘 2020. 11. 9. 23:17
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자) 되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 seungjuitmemo.tistory.com 이 전의 포스팅에서 되추적 알고리즘의 효율성에 대해서 문제 삼았고 이를 해결하지 못했다. 되추적 알고리즘이 어떤 특정 사례를 얼마나 효율적으로 처리하는지에 대한 추정치가 있다면 그 사례에 대해서 그 알고리즘을 사용하는게 타당한 지 결정할 수 있다. 몬테칼로 알고리즘은 확률 알고리즘이기 때문에 표본공간의 무작위 표본의 평균치를 가지고 표본공간에서 정의된 무작위..
-
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자)알고리즘 2020. 11. 9. 20:11
되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것이다. 즉, 어떤 여왕말끼리도 같은 행이나 열, 대각선상에 위치할 수 없다. 이 문제에서 순서는 여왕말을 둘 n개의 각각 다른 위치이고, 집합은 서양 장기판에서 말을 둘 수 있는 n제곱개의 위치들이 되고, 기준은 어떤 여왕말도 서로 잡아 먹히지 말아야 한다는 것이다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. DFS에 대해 간단히 설명하면 부모의 노드에서 내려갈 수 있는 자식노드까지 내려가고 그 이후의 자식 노드가 없다면 다시 부모노드로 돌아가면서..
-
알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)알고리즘 2020. 11. 6. 14:42
탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 설정해서 구하기 때문에 과잉이라 볼 수 있다. 반면 탐욕 알고리즘은 항상 최적인 해를 만들어 주지 않는다. 그래서 보통 반례를 통해 최적의 해를 갖지 않는다는 것을 증명한다. 이 두 방법의 차이점을 확실하게 이해하기 위해서 0-1배낭 채우기와 배낭 빈틈없이 채우기라고 하는 두가지 문제를 살펴본다. 우선 결론적으로 말하면 배낭 빈틈없이 채우기 문제는 탐욕 알고리즘을 이용해서 풀 수 있지만 0-1배낭채우기를 풀 수 없으며 대신 동적계획법을 이용해서 완벽하게 풀 수 있다. < 0-1배낭채우기 문제(0-1 knapsack prob..
-
알고리즘: 스케줄짜기(Scheduling)공부하기! (시스템 내부시간 최소화, 마감시간이 있는 스케줄짜기)알고리즘 2020. 11. 6. 13:08
어떤 미용사에게 여러가지를 서비스를 받으려고 기다리는 손님이 있다고 하자. 서비스에 걸리는 시간은 모두 다르고 미용사는 얼마나 걸릴지 알고 있다. 손님들이 기다리는 시간을 최소가 되도록 손님을 서비스하는 것을 스케줄 짜기(sheduling)이라 하며 기다리고 머리하는데 걸리는 시간을 시스템 내부시간(time in the system)이라 한다. 그리고 마감시간이 정해진 경우(scheduling with deadlines)가 있는데 각 작업을 끝내는데 같은 시간이 걸리지만 각 작업과 관련된 보상을 최대로 얻기 위해서 마감시간을 고려해야하는 경우다. 이렇게 스케줄짜기는 시스템 내부시간(time in the system)과 마감시간이 있는 스케줄짜기(scheduling with deadlines)로 나뉘며 이..