반응형 알고리즘 문제풀이101 [Backjoon] 11727번 문제 - 2xn 타일링 2 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다. 풀이경우의 수 문제이다. 우선 2Xn 직사각형에서 n이 1일때 부터 생각해보면 경우의 수는 1가지 이다.n이 2일 때 타일을 채우는 경우의 수는 3가지이다. n이 3일때부터 앞에서 구해진 2x1과 2x2를 기반으로 생각할수 있는데, 2x1타일로 먼저 채울 경우와 2x2타일로 먼저 채우는 경우의 수로 나뉜다.위의 그림 처럼 모든 경우의 수를 고려 했을 때 중복되는 경우의 수를 빼면 타일의 경우의 수가 나오는 것이다. 즉 2x3타일을 채우기 위해서는2x3-2x1으로 채워졌다는 가정하에 2x2만 더 채우면 되므로 2x2의 경우의 수 만큼 더해주면되고2x3-2x2으로 채.. 2017. 6. 12. [Backjoon] 2581번 문제 - 소수 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오.예를 들어 M=60, N=100이 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최소값은 61이 된다. 풀이 이중 반복문으로 소수를 구한 다음순회하여 모든 소수를 더하고sort 내장 함수로 정렬하여 가장 처음 값을 출력한다. 12345678910111213141516171819202122232425262728293031323334353637383940import java.util.ArrayList;import java.util.Collections;import java... 2017. 6. 11. [알고리즘] 동적 계획법(Dynamic Programming) - 6 동적 계획법(Dynamic Programming) - 6 이번 시간에는 동적 계획법의 또다른 고전 중에 Knapsack Algorithm에 대해 알아보자Knapsack은 배낭을 가리키는 말인데 배낭 알고리즘 이라고도 한다.이 알고리즘에는 재미있는 이야기가 숨어있는데, 도둑이 상점에 물건을 훔치기 위해 배낭 하나를 들고 왔다고 했을 때,가지고 나갈수있는 무게가 한정적이지만 최대의 비용을 낼 수있게 해야한다. 각각의 물건 마다 무게와 가격이 다 다르다.따라서 n개의 아이템과 배낭의 용량 W가 주어질 때배냥의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합을 구해야 한다.. 예를 들어 위의 그림에서 {1,2,5}는 가격의 합이 35,{3,4}는 가격의 합이 40,{3,5}는 가격의 합이46 이지만 배낭의.. 2017. 6. 10. [알고리즘] 동적 계획법(Dynamic Programming) - 5 동적 계획법(Dynamic Programming) - 5 이번 시간에는 Longest Common Subsequence를 알아보자Longest Common Subsequence는 줄여서 LCS라고 부르는데, 약어로 부르는것은 그만큼 유명하다는 뜻이다.입력으로 2개의 문자열이 주어지며, bcdb는 문자열 의 subsequence이다.또한 는 문자열 와 의 common subsequence(공통 부분 문자열)이다. 우리가 고려해야할 부분은 LCS인데, 입력으로 2개의 문자열이 주어졌을때, common subsequence중에서 가장 긴것을 찾으면 된다.예를 들어, 는 와 의 LCS가 되는 것이다. 그렇다면 위의 그림에서 x라는 문자열과 y라는 문자열이 입력으로 주어진 문자열이며,z가 우리가 원하는 최적해라고.. 2017. 6. 9. 이전 1 ··· 7 8 9 10 11 12 13 ··· 26 다음 반응형
