본문 바로가기

알고리즘225

Segment Tree, LIS https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 가장 기본문제. 구간의 합,최댓값,최소값 등, 원소간 결합,교환법칙이 성립하는 연산에대해 구간의 연산을 구할 수 있는 알고리즘. .. 2019. 8. 18.
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.

티스토리툴바