본문 바로가기

알고리즘90

GCD 함수 int gcd(int a, int b) { if (b > a) swap(a, b); int r; while (b != 0) { r = a % b; a = b; b = r; } return a; } int gcd(int a,int b){ if(a 2019. 8. 18.
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.

티스토리툴바