거의 알고리즘 일기장

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비트 부호 있는 ..

풀이방법 A : 1 + 2 + 4 + .. + 2^k-1의 축적합을 구해서 주어지는 수를 나눠주면 된다. 주의사항으로는 int의 범위값을 넘기때문에 담는 배열을 long long으로 만들어주면된다. 축적합은 30까지만 만들어주면 주어진 범위 넘으니 30까지만 만들어주자. #include #include #include using namespace std; long long aSum[31]; void ASumInit() { for (int i = 1; i num; solve(num); } return 0; } B : n%4 == 0이여야 조건중 하나인 배열의 1~n/2까지 누적합 *2 = 배열의 1~ n까지의 누적합이 성립한다. 이제 no는 문제가 없고 yes일때 list를 생각해면 나같은 경우에는 만약에..

https://codeforces.com/contest/1213 Dashboard - Codeforces Round #582 (Div. 3) - Codeforces codeforces.com 먼저 풀었던 a, b, c 번 부터 리뷰하고 이후 문제는 아직 풀이를 제대로 하지 못해 이후에 리뷰하겠다. 풀이방법 A. Chips Moving 칩을 옮겨서 같은 곳에 두는 방법중 최소의 수를 찾는 문제다. 먼저 조건을 잘보자. 잘 보면 홀수와 짝수인 개수를 세고 둘중에 작은 것의 개수를 구하는 문제라는 것을 알수있을것이다. 이후는 생략~ B. Bad Prices 이 문제는 지금 위치의 값보다 작은 값이 있는지 없는지 알아보는 문제이다. 별건 없고 역순으로 MIN값을 만들어 비교하면 개수를 세면 끝이다. C. Boo..

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 = ..