본문 바로가기

전체 글327

Union Find (=disjoint set) 필요한 것: uf배열. find 함수 : 1. uf 배열이 -1로 초기화된 경우 2. uf 배열이자기자신으로 초기화된 경우 merge 함수: 1. merge함수가 일반적으로 union의 기능만을 수행하는 경우 2. MST등에서 union에 성공했을 떄 true, 실패했을 때 false 반환하는 경우 3. merge 후 대표정점(집합)에 포함된 요소의 크기를 초기화해주는 경우 등등등.. 상황에 맞게 구현할 수 있다 int uf[MAX]; //uf배열이 -1로 초기화된 경우 int find(int a) { if (uf[a] == -1) return a; return uf[a] = find(uf[a]); } //union기능만 수행 void merge(int a, int b) { a = find(a); b =.. 2019. 8. 18.
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.
tip. lower_bound, upper_bound arr : 1 3 3 5 5 5 7 ^ * lower_bound(arr,arr+n, 5) : ^ upper_bound(arr,arr+n, 5) : * arr에 있는 5의 개수는 upper-lower로 구할 수 있다. https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. .. 2019. 8. 6.

티스토리툴바