거의 알고리즘 일기장

https://www.algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 www.algospot.com 접근 첫번째 아이디어 수열을 합치는게 어떨까 생각했다. 하지만 더 곰곰히 생각해보니 어떻게 합칠지와 시간면에서 통과하는 방법은 아닐것으로 생각되어 패스했다. 두번째 아이디어 일반적인 LIS를 구하는 방식에서 두 수열을 모두 살펴본다. (종만북의 풀이) 풀이방법 그냥 LIS와 다를것 없는 풀이방식이다. 다만 모든 원소들은 32비트 부호 있는 ..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 풀이방법 일반적인 top down 메모제이션 풀이로 풀면 됨. 전체코드 #include #include using namespace std; int A[1001]; int dp[1001]; int N; void dpInit() { for (int i = 0; i > N; for (int i = 1; i > A[i]; } int getMa..

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다. www.acmicpc.net 접근 이 문제를 완전탐색으로 푼다면 최악의 경우 100!으로 절대 시간안에 풀수없다. 잘 보면 중복연산이 매우매우 많으니 메모제이션을 사용하자!! 풀이방법 이 문제는 주어진 word들이 S를 만들수 있는지 없는지만 판별하면 되는 문제다. 그러므로 dp[string 길이] : -1일땐 아직 탐색안한..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 풀이방법 그냥 냅색 알고리즘이다. dp[가방종류][무게] = 가질수있는 최대가치 이렇게 dp를 설정해두고, dp[i][j] = max(dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value) 이 점화식을 이용해 풀면된다. for (int ..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이방법 이거 그대~로 풀고 메모제이션 사용하면 정답 전체코드 #include #define DIV_NUM 10007 using namespace std; long long nCk[1001][1001]; int N, K; void nCkInit() { for (int i = 0; i N >> K; nCkInit(); cout

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 풀이방법 dp문제이며 직전에 푼 쉬운 오르막과 거의 유사한 문제다. 그냥 똑같다고 보면됨. 그러므로 생략하겠습니다.ㅎ 전체코드 #include #include #define DIV_NUM 10007 using namespace std; long long dp[10][1001]; int N; void dpInit() { for (int i = 0; i

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주의사항 %를 계산시마다 할것!!! 전체코드 재귀 풀이 #include #define DIV_NUM 1000000000 using namespace std; long long dp[10][101]; int N; void dpInit() { for (int i = 0; i n; long long int result = 0; for (int j = 1; j

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 풀이방법 제곱수를 미리 구해놓음 void powNumberInit() { powNumber[1] = true; for (int i = ..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. www.acmicpc.net 풀이방법 메모제이션 문제, 거의 동일한 방식으로 푼 밑의 풀이를 참고. https://kunkunwoo.tistory.com/100 백준 2293번 _ 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는..

https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 풀이방법 선택의 경우가 3가지가 있다. 위의 경우들을 끝까지 갈때까지 반복하면됨. 전체코드 #include #include using na..