백트래킹3 [알고리즘] 배낭 알고리즘 (fractional 배낭, 0-1 배낭) 분할 가능한(fractional) 배낭 알고리즘 문제 도둑은 W만큼 들 수 있는 가방을 가지고 있다. W를 초과하는 보석을 담을 경우 가방이 찢어져 버리고 만다. 무게가 w고 가치가 v인 N개의 보석이 존재할 때 도둑이 훔칠 수 있는 보석의 최대 가치를 구하라. (보석은 분할 가능하다.) 그리디 알고리즘을 다룰 때 가장 자주 나오는 문제이다. 브루트포스를 사용해 훔칠 수 있는 보석의 모든 조합을 구할 수 있겠지만 N개의 보석의 모든 조합을 구하려면 O(2^N)의 시간이 걸릴 것이다. (보석을 훔친다 || 안 훔친다.) * N개 따라서 그리디하게 접근하면 효율적으로 해결할 수 있다. 무게 대비 가치가 높은 것부터 가방을 채우면 되지 않을까? N개의 보석을 v/w가 높은 순으로 정렬 후 W만큼까지만 훔쳤을 .. 2023. 4. 29. [백준] 10971번: 외판원 순회 2 | C++ https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 외판원 순회 알고리즘 - 가중치가 양의 정수이고 N이 작을 경우 (Sliver 2) 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.. 2022. 12. 25. [백준] 18430번: 무기 공학 | C++ https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 틀린 이유 안 쓰려다가 날 너무 괴롭혀서 쓴다... 1. 처음 접근 때는 백트랙킹 메서드 안에 for 문을 두 개 돌렸었다. 인수로 x, y 좌표를 입력 받고 인수에서 시작하는 for 문 두 개.... (이것이 근본적으로 틀린 접근이었다.) 아무튼 처음 틀린 이유는 (1) for 문을 돌릴 때 p,q,x,y 변수를 아예 틀리게 써서 틀렸다. → 오타를 인지 못했다는 뜻 2. 오타.. 2022. 12. 19. 이전 1 다음
