전체 글27 10. Backtracking ㅣ Knapsack 문제 Backtracking ? 기존에 알아보았던 Divide＆conquer, Dynamic programming 그리고 나중에 알아볼 Greedy 등의 알고리즘은 문제를 효율적으로 풀기 위해 사용했지만, Backtracking은 효율성보단 정확성에 조금 더 초점에 둔 알고리즘이다. Knapsack 문제 ? 여러 물건의 무게와 가격이 주어지고, 배낭에 담을 수 있는 총 용량(크기 또는 무게) 제한 K가 있다면, 배낭 용량 제한 K를 넘지않도록 물건을 골라 배낭에 담는 문제 ☆ 목표 ❗ :선택한 물건의 가격(이익)의 합이 최대가 되도록 선택 Knapsack 문제의 여러가지 버전 1. fractional knapsack 문제 선택한 물건의 일부분을 배낭에 넣을 수 있는 문제. 가루처럼, 물건을 나눠 담을 수 있다.. 2021. 8. 18. 9. Backtracking ㅣ Subset sum 문제 Backtracking ? 기존에 알아보았던 Divide＆conquer, Dynamic programming 그리고 나중에 알아볼 Greedy 등의 알고리즘은 문제를 효율적으로 풀기 위해 사용했지만, Backtracking은 효율성보단 정확성에 조금 더 초점에 둔 알고리즘이다. Backtracking은 해를 찾는 도중 해가 아니어서 막히면, 이전으로 되돌아가서 다시 해를 찾아가는 기법인데, 미로찾기 예제를 들어서 조금 더 자세히 설명해보겠다. ㆍn x n 미로를 나타내는 이차원배열 M 설정. ㆍM[i][j] = 1 이면 길이고, 0이면 장애물이라고 가정. ㆍ오로지 길로만 가야하며, 아래쪽과 오른쪽에 이웃한 길로만 갈 수 있다고 가정. ㆍM[0][0]에서 출발해 M[n-1][n-1]로 도착해야 탈출 성공!.. 2021. 8. 12. 8. Dynamic Programming(동적 계획법) ㅣ최장공통부문자열(LCS) 문제 Dynamic Programming (동적 계획법) ? Divide＆conquer(분할정복)와 유사하게, 문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법이다. 차이점은 큰 문제의 해답이 작은 문제의 해답들의 식으로 표현되는데, 그 답을 필요할 때마다 재귀적으로 얻는 것이 아니라, 분할된 문제의 해답을 기록해 놓은 후 재사용한다! → ★시간 단축에 매우 유리 최장공통부문자열(LCS) 문제 by Dynamic Programming ○ 최장공통부문자열(LCS) 문제 ? → 대표적인 유명한 DP문제로, 두 문자열 X, Y의 공통 부문자열 중에서 길이가 가장 긴 것을 찾는 문제 ❕ 부문자열(subsequence)는 문자열에서 몇 개를 지우고 남은 문자의 열을 의미한다. ex) X = ABCBBDA 일때,.. 2021. 8. 8. 7. Dynamic Programming(동적 계획법) ㅣ행렬 곱셈 문제 Dynamic Programming (동적 계획법) ? Divide＆conquer(분할정복)와 유사하게, 문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법이다. 차이점은 큰 문제의 해답이 작은 문제의 해답들의 식으로 표현되는데, 그 답을 필요할 때마다 재귀적으로 얻는 것이 아니라, 분할된 문제의 해답을 기록해 놓은 후 재사용한다! → ★시간 단축에 매우 유리 행렬 곱셈 문제 by Dynamic Programming ○ 행렬 곱셈 문제 ? → n개의 행렬의 곱셈을 곱하는데 드는 최소 비용(곱셈에 필요한 총 기본 연산의 횟수)의 최소를 구하는 문제 ○ 어떤 순서로 행렬 곱셈을 하느냐에 따라 기본 연산의 횟수가 크게 달라진다. → a x b 행렬과 b x c 행렬의 곱셈을 위해 필요한 기본연산(두 수의.. 2021. 8. 6. 이전 1 2 3 4 ··· 7 다음
