과학고에서 떨어진 나는 그동안 충격에 휩싸여 열심히 하지 않아 실력이 많이 줄었을거라 생각되니 더 열심히 재활 활동을 꾸준히 해보자. 소개할 알고리즘 : LIS LIS는 Longest Increasing Subsequence, 즉 최장 증가 부분 수열을 말한다. *) 예를 들어 {10,20,10,30,20,50}이라는 배열이 있다고 가정하자. 그렇다면 이 배열에서의 LIS는 {10, 20, 10, 30, 20, 50} => {10, 20, 30, 50} 이러한 상태가 된다. 이 LIS 알고리즘은 우리에게 특정한 배열에서의 LIS를 구해주는 알고리즘이다. 이 알고리즘에는 3가지 방법이 있다. 1. O(n^2) DP 2. O(n log n) Segment Tree 사실상 거의 안씀 3. O(n log n) ..

이번에 KOI에서 잘 못해서 빡친 나는 이번년도에 코포 오렌지 달고 간다는 생각으로 재활훈련을 시작했다. 처음 셋은 조합론 + dp 조합이다. 운으로 올솔하였다. 1. www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 처음 봤을 때는 만만치 않은 문제처럼 보이나, 순서를 고려해주면 아주 쉽게 풀 수 있는 문제이다. 먼저 우리가 신경써야 할 것은 순서에 의한 중복되는 경우의 수인데, 순서를 어떤 기준..

문제는 3문제였고 자기 전에 1시간 정도 연습을 진행했다. 올솔 ㅎ 1. 한 줄로 서기 (Silver 2) www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 � www.acmicpc.net N> n; for(int i=0; i> s[i]; for(int i=0; i

DP 위주로 2시간 동안 연습한 세트이다. 1. 카드 구매하기2 (Silver 1) www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 그냥 쉬운 DP 문제. dp[i]=min(dp[i],dp[j]+su[i-j]); #include #define MEM 1009 #define sanic ios_base::sync_with_stdio(0) using namespace std; typedef long long ll; ll n; ll su[MEM], dp[MEM]; ma..

www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net O(nk)로 풀어야 한다. 스택으로 한 문자씩 넣은 뒤 문자가 폭발 문자열의 마지막 문자열이랑 같다면 그 전 문자열들을 확인해서 제거하면 된다. 쉬운 문제. #include #define MEM 1000009 #define sanic ios_base::sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pi; co..

www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 투 포인터 문제다. 두 포인터를 움직일 때 범위를 주의하자. #include #define MEM 100003 #define sanic ios_base::sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pi; const ll MOD = 1e9+7; ll n,m; ll a[MEM]; int ma..