알고리즘/백준 & swacademy108 BOJ 12015 - 가장 긴 증가하는 부분수열2 (segtree) 라이님 블로그에서 공부했음을 밝힘니다. 구간 최대값을 저장하는 세그먼트트리를 마련해 두자. 값을 입력받을 땐, {원소값, 인덱스} pair로 p배열을 만들고, 원소값 순 인덱스 역순으로 정렬해 준다. p배열을 순서대로 방문하면서 세그트리를 업데이트 해준다. 마지막에 루트에 남은 값이 LIS길이가 된다. #include #include #include using namespace std; int arr[1 > a; p[i] = { a,i }; } sort(p, p + n, [](pair p, pair q) { if (p.first != q.first) return p.first q.second; }); for (int i = 0; i < n; i++) {.. 2019. 8. 19. BOJ 3745 - 오름세 https://www.acmicpc.net/problem/3745 3745번: 오름세 문제 주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다. 정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다. n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다. n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오. 입력 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케 www.acmicpc.net 가장 긴 증가하는 부분수열의 길이(LIS)를 출력하는 문제다. dp로 O(n^2) 수행시간에 해결하는 것은 종만북에서 해본 기억이 있지만,.. 2019. 8. 6. BOJ 16562 - 친구비 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N) 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. www.acmicpc.net 유니온파인드 문제다. 각 집합의 최소를 모두 더한 합을 출력하면 된다. #include #include using namespace std; int n, m, k; int uf[10001]; int cost.. 2019. 8. 6. BOJ 2075 - N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 라이님블로그의 풀이를 리뷰. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; priority_queue pq; //최소힙 for (int i = 0; i < n; i++) { for (int j = 0,a;.. 2019. 8. 6. 이전 1 ··· 20 21 22 23 24 25 26 27 다음