너와 나의 스토리

문제: https://www.acmicpc.net/problem/1965 문제 풀이: 가장 긴 증가하는 부분 수열을 찾으면 된다. 소스 코드: int n; vector v; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i > q; int pos = lower_bound(v.begin(), v.end(), q)-v.begin(); if (pos == v.size())v.push_back(q); else v[pos] = q; } cout

문제: https://www.acmicpc.net/problem/15976 문제 풀이: 이걸 x에 대해 묶으면 -> X0(Y-1+Y0+Y1) + x1(Y0+Y1+Y2)+X2(Y1+Y2+Y3) ..... ` 즉, a≤t≤b라고 할 때 Xi*{ Y(i+a)~Y(i+b)} + .... 가 된다. 여기서 Y(i+a)~Y(i+b)는 미리 합을 저장해 둔 후 구간 합을 구한다. y의 인덱스를 저장하는 벡터를 따로 만들어서 lower bound를 통해 구간을 찾는다 만약 y가 다음과 같을 때, i 0 1 2 3 4 Yi 7 5 2 y의 인덱스를 저장하는 벡터에는 다음과 같이 저장된다. -> 2,3,4 0~1 구간을 찾게 되면, P1=0, p2=0이 되고, (y의 인덱스 저장하는 벡터)[0]은 2인데 1보다 크므로 p..

문제: https://www.acmicpc.net/problem/15975 문제 풀이: https://hororolol.tistory.com/140 이 문제에서 long long으로 바꿔주고 색이 하나 일 수도 있으므로 하나일 때는 연산 스킵해주면 됨 소스 코드: typedef long long ll; int n; ll res; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); unordered_map m; cin >> n; for (int i = 0; i > q >> w; m[w].push_back(q); } for (auto next : m) { vector v = next..

문제: https://www.acmicpc.net/problem/15973 소스 코드: typedef pair P; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); P a1,a2, b1,b2; cin >> a1.first >> a1.second; cin >> a2.first >> a2.second; cin >> b1.first >> b1.second; cin >> b2.first >> b2.second; if (a1.first > b1.first) { swap(a1, b1); swap(a2, b2); } if (a1.second >= b1.second) { if (a1.first

문제: https://www.acmicpc.net/problem/15970 소스 코드: int n,res; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); map m; cin >> n; for (int i = 0; i > q >> w; m[w].push_back(q); } for (auto next : m) { vector v = next.second; sort(v.begin(), v.end()); res += (v[1] - v[0]); for (int i = 1; i < v.size()-1; i++) { res += min(v[i] - v[i - 1], v[i + 1] - ..

문제: https://www.acmicpc.net/problem/14444 문제 풀이: manacher 알고리즘 이용 A[i] : i번째 문자를 중심으로 가능한 회문의 길이(반지름) S=baab 이런 경우 어떤 문자를 기준으로 해도 회문을 찾을 수 없으므로 '#'을 추가해 준다 -> S=#b#a#a#b# ex) S=#b#a#a#b# i 0 1 2 3 4 5 6 7 8 A[i] 0 1 0 1 4 1 0 1 0 r: (가장 긴) 회문의 길이 + 해당 위치의 인덱스 p: (가장 긴) 회문의 길이를 가지는 중심축의 위치 2*p-i: p를 중심으로 i의 회문에서의 대칭점 i> s; string s2=""; for (int i = 0; i < s.size(); i++) { s2 += '#'; s2 += s[i]; ..

* map - Red-Black-Tree를 사용해 키 순서 유지 - 삽입&삭제&탐색: O(logN) * unordered_map - hash table 사용해 키 순서 유지할 필요 없음 - 탐색 속도: O(1) * set - 균형 이진 트리로 구현됨 - 삽입&삭제&탐색: O(logN)

문제: https://www.acmicpc.net/problem/17074 문제 풀이: 오름차순인 구간을 나눔 ex) 123845인 경우 각각 0~3, 4~5번째 값들은 오름차순으로 정렬되어 있다. 그럼 경계에 있는 3, 4번 값이 뺄 수 있는 값의 후보이다 만약 3번을 뺐을 때, 4번을 뺐을 때 둘 다 정렬된 값이면 답은 2 즉, 답의 최대값은 2이다. 구간이 3개 이상이 나오면 어떤 값을 빼도 정렬될 수 없으므로 답은 0 case1: 왼쪽 구간이 한개만 존재하는 경우 case1-1: 오른쪽 구간도 한개만 존재하는 경우 -> 두 개다 뺄 수 있으므로 답은 2 case1-2: 오른쪽 구간은 여러개인 경우 -> 오른쪽 경계 뺐을 때 오름차순이면 답은 2 -> 아니면 왼쪽 값만 뺄 수 있으므로 답은 1 ca..