helloahram

배낭 문제 Knapscak Problem 최대 K 의 무게를 담을 수 있는 배낭 각기 다른 가치 V 를 가지고 W 의 무게인 N 개의 물건을 배낭에 최대한 가치가 높은 물건들로 담을 수 있는 조합을 찾는 문제  만약 n개의 물건이 있을 때, 가능한 모든 조합을 만들기 위해서는 2^n개의 경우를 시도해 보아야 하고그렇게 된다면 시간 복잡도는 O(2^n) 이기 때문에 Brute Force 는 적합하지 않다  배낭 문제는 물건을 쪼갤 수 있는 Fraction Knapsack Problem 과물건을 쪼갤 수 없는 0-1 Knapsack Problem 으로 나뉜다   부분 배낭 문제 Fraction Knapsack Problem 물건을 쪼개서 넣을 수 있다 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는..

1. 문제두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다예를 들어, ACAYKP 와 CAPCAK 의 LCS 는 ACAK 가 된다 2. 요구사항시간 제한 0.1초메모리 제한 256MB 3. 알고리즘 분류* 다이나믹 프로그래밍* 문자열 4. 접근 방식 ㄷㅎ님이 기깔나게 설명해 주신 LCS 알고리즘을 이용하여 풀었다 LCS 알고리즘 정리한 내용 문제에서 문자열 A "ACATKP" 과 문자열 B "CAPCAK" 을 비교한 내용을 표로 정리하면 아래와 같다  0ACAYKP00000000C0011111A0112222P0112223C0122223A0123333K0123344 0 인 행렬을 추가한 이유는 비교 과정에서 대각선 +1 과 왼쪽/ 위쪽 비교를 위해서 추가했고,그렇기 때..

1. 문제계단에 쓰여 있는 점수가 주어질 때 점수의 최댓값 구하기1. 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다3. 마지막 도착 계단은 반드시 밟아야 한다2. 요구 사항* 계단의 개수는 300 이하의 자연수 * 계단에 쓰여 있는 점수는 10,000 이하의 자연수 3. 알고리즘 분류* 다이나믹 프로그래밍 4. 접근 방식계단을 올라가는 것만 생각하지 말고, 이미 올라간 상태에서 이전에 내가 어떤 계단을 밟고 올라올지를 생각하는 방식으로 접근한다1) 직전 계단 (n-1) 을 밟고 올라온 경우는 세번 연속 계단을 오를 수 없으므로 그 이전 계단은 n-3 번째 계단이다2) 두 칸 전 (n-2) 계단을 밟고 올라온 경우  i 번째 계단까지 올라왔을 때까지의..

1. 문제2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오 2. 요구사항시간 제한 1초메모리 제한 256 MB1 3. 알고리즘 분류* 다이나믹 프로그래밍4. 접근 방식이것도 n = 7 까지 모든 경우의 수를 계산해 봤는데 아니나 다를까 피보나치였고n= 1 는 1, n = 2 는 2 를 초기값으로, n = 3 이상은 n-1 과 n-2 합으로 계산했다4. 코드 구현# 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 # 10,007 로 나눈 나머지를 출력한다 # 1

1. 문제n 이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), 0  2. 알고리즘 분류* 수학* 다이나믹 프로그래밍 3. 접근 방식n 이 90까지라서 재귀로 풀면 시간 초과가 뜬다는 말을 듣고,어제 공부했던 Dynamic Programming 의 메모이제이션을 활용하여 구현해 보았다메모이제이션 - 이전 결과 값을 저장하여 중복 계산을 피하는 것  4. 코드 구현 def fibo(n): if n