1. 문제 어떤 수열이 왼쪽에서 오른쪽으로 순서대로 나열된다. 3,2,6,4,5,1.... 만약 이러한 나열된 순서를 유지하면서, 크기가 점진적으로 커지면서, 가장 긴 부분수열은 어떻게 찾을 수 있을까 이러한 부분수열은 연속적으로 고를 필요는 없다. 예를 들어 위 수열에서 3,4,5는 크기가 점점 커지는 부분수열이다. 2. 완전 검색 단순하게 완전 탐색을 수행해서 찾아낼 수도 있다 주어진 수열의 모든 부분집합을 구한다. 부분집합의 원소들이 증가하는 수열인지 검사한다. 증가하는 수열일때, 부분수열의 길이의 최댓값을 갱신한다. 당연히, 부분집합의 크기가 긴 것부터 조사하면, 처음으로 찾게되는 증가수열이 가장 긴 증가수열일 것이다. #완전탐색으로 최장증가 부분수열 찾기 s = [3,2,6,4,5,1] n = ..
1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건의 무게 합은 W를 초과할 수 없고 각각의 물건은 1개씩만 존재한다 그리고 물건을 쪼개서 담을 수 없다고 가정한다. 이러한 문제는 0-1 knapsack 문제라 부르고 물건을 쪼개서 담을 수 있는 경우도 물론 있는데 fractional knapsack 문제라고 부른다. 2. 해법 - 완전탐색 조금 생각해보면, 존재하는 물건들의 집합 S에서, 일부를 골라 가방에 담는 문제이므로, 집합 S에서 모든 부분집합을 구하고, 가치들의 합을 조사한다 이때, 가방의 용량을 넘지 않으면 가치의 합을 구하고..
1. 문제 1952. [모의 SW 역량테스트] 수영장 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1일 이용권, 1달 이용권, 3달 이용권, 1년 이용권을 사용하여 주어진 1월~12월까지 수영장 이용 계획을 최소 비용으로 이용하고 싶을때, 그러한 최소 비용을 찾는 문제 2. 풀이 다이나믹 프로그래밍을 연습할 수 있는 아주 좋은 문제다 dp[i]를 1~i번째 달까지 사용한 최소 요금으로 정의하자 각각의 i번째 달에 사용할 수 있는 경우의 수는 무엇일까? 1) 1일 이용권을 모두 사용하는 경우 예를 들어 3월에 2일 사용했는데, 2일을 1일 이용권 2번으로 사용할 수 있다 2) ..
1. 문제 17175번: 피보나치는 지겨웡~ (acmicpc.net) 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 피보나치 함수의 호출 횟수를 구하는 문제 2. 풀이 재귀 함수의 호출 횟수를 곧이 곧대로 구하면 풀 수 없다 def fibonacci(n): global cnt cnt += 1 if n < 2: return n return fibonacci(n-2)+fibonacci(n-1) 중간에 cnt를 넣어가지고 cnt를 구하면 함수의 호출횟수가 되는데 n이 조금만 커져도 도저히 시간안에 함수가 끝나질 않..
1. 문제1 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 나선형으로 정삼각형을 만들었을때, 정삼각형의 가장 긴 변의 길이를 구하는 방법은? 2. 풀이1 이런 문제는 그냥 몇개 나열해보면서 규칙을 찾으면 되겠다고 생각하는게 제일 편하다 이런 규칙 찾는 문제가 다이나믹 프로그래밍의 가장 기본형태라고 생각하면 된다 그래서 몇개 해보면 규칙이 나올거야 p(1)부터 p(10)까지는 1,1,1,2,2,3,4,5,7,9라고도 친절하게 나와있고 그림에서 p(1..
1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 주어진 n개의 임의의 수열에서 1개 이상의 연속된 부분 수열을 선택할 때, 가장 큰 합을 출력 2. 나의 풀이 단순한 규칙, 점화식으로는 풀기 어렵다 메모리, 시간제한 문제로 $O(N^2)$으로도 통과하기 어렵다 처음에 i번째부터 j번째까지 수열의 합을 dp[i][j]에 저장해서 테이블을 완성하려고 했는데 n의 최대가 100000이라 10만*10만 만들자 마자 메모리 초과 from sys impo..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
