알고리즘 썸네일형 리스트형 BOJ(백준) 9345 - 디지털 비디오 디스크(DVDs) 아이디어 딱 떠오르는 아이디어는 '누적합 = 세그먼트트리 구간합' 이면 YES 출력이고, 그렇지 않으면 NO 였다.근데 여차저차 해서, [2, 4]에서 1, 3, 5가 들어있어도 누적합 = 구간합이 성립되어 반례가 존재한다. 그래서 떠올려야 하는 것은 구간의 최대, 최솟값 Query이다. 그 구간에 최대/최솟값 Query를 통해 알 수 있다. https://github.com/jongwuner/Algorithm/blob/master/BOJ/1280.cpp 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include#includeus.. 더보기 BOJ(백준) 3653 - 영화 수집 ★ 아이디어처음에 query를 이용해서 간단히 구간합을 뽑을 수는 있는데, 그 이후가 쉽지 않다. DVD를 뽑아서 맨 위로 올리는 것을 어떤 식으로 표현할 것인가?? 처음에는 또 인덱스 및 구간에다가 합을 부여하고 싶다. lazy propergation 같은 아이디어가 떠올랐는데, 그때마다 항상 0과 1, 리프노드를 잘 활용하는 아이디어가 필요했다. 세그먼트트리의 리프를 N + M만큼으로 구성하는 아이디어가 필요하다. N = 8, M = 3이면 0 0 0 1 2 3 4 5 6 7 8 더보기 BOJ(백준) 1280 - 나무심기 ★ 아이디어 일단 좌표의 범위가 (2 더보기 BOJ(백준) 3006 - 터보소트 ★ 아이디어index자체를 바꾸려면 시간이 엄청 걸린다. 구간에다가 합을 부여하고 싶은 생각이 든다. lazy propergation이 떠오르긴 하는데, 그것말고 또 다른 아이디어가 있을까 찾다가, 바꾸는 횟수를 카운트 = 리프노드가 1인 세그먼트트리로 구간합을 구하는 아이디어 이것을 떠올리면 간단해진다. https://github.com/jongwuner/Algorithm/blob/master/BOJ/3006.cpp 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include#include#includeusing namespace std;typedef pair Pair;int N, segSize .. 더보기 BOJ(백준) 3745 - 오름세 아이디어LIS를 구현하는 문제. LIS의 마지막 원소보다 새로들어올 원소가 크면 push_back, 아니면 새로들어올 원소로 기존의 원소를 대체하여 추후에 LIS가 더 커질 수 있도록 만든다. https://github.com/jongwuner/Algorithm/blob/master/BOJ/3745.cpp 123456789101112131415161718192021222324252627282930#include#include#includeusing namespace std;vector lis;int main() { int N; while (scanf("%d", &N) != EOF) { lis.clear(); for (int i = 0; i 더보기 BOJ(백준) 12837 - 가계부(Hard) 아이디어 기본적인 세그먼트트리 구현문제. update 시 편차를 더해주거나 빼주거나 하는 것 빼곤 특별한 것이 없다. https://github.com/jongwuner/Algorithm/blob/master/BOJ/12837.cpp 12345678910111213141516171819202122232425262728293031323334353637383940#include#includeusing namespace std;typedef long long ll;vector seg;int segSize = 1, N, M;void update(int idx, ll val) { idx += segSize; seg[idx] += val; while (idx > 1) { idx /= 2; seg[idx] = seg.. 더보기 BOJ(백준) 10775 - 공항 아이디어처음에 접근을 공항과 비행기 노드를 따로 나눠서 생각해보았다. 어떤 식으로 데이터를 정의하고, 자료구조에 담을 것인가 생각하다가 보니, 이 아이디어는 유니온파인드 스럽지 않은 문제를 유니온파인드로 설정하는 아이디어였다. 문제의 까다로운 조건들을 보면 merge와 find를 어떤 식으로 활용하라는 힌트가 주어져 있다. ★★도킹을 하면 그 노드는 방문하지 못하게끔 되고, parent설정을 통해 방문하지 못하게된 노드를 다시 방문할 때는 parent로 유도한다. 방문과 동시에 merge를 통해 parent를 다시 설정하게 되고, 그 다음 번 방문을 위해 경로압축도 진행된다. 점검해볼 사항- 유니온파인드를 트리의 관점에서 바라보기- 경로압축을 통해 이런 문제 처럼 시간절약을 할 수 있다.- find와 m.. 더보기 BOJ(백준) 16562 - 친구비 아이디어마찬가지로 분리집합에서 시작해서 합집합해가는 과정의 문제이다. 주어지는 N개의 노드와 자기자신이라는 1개의 노드가 더있다고 보았다. 자기자신을 0번노드라 하고 문제에서 주어지는 노드를 1~N번 노드라 할 때, 0번노드와 모든 노드가 하나의 집합이 되어야 하며, 합집합(merge) 연산을 할 때마다 비용이 발생한다. 그 비용이 k를 넘으면 Oh no를 출력한다. 점검해볼 사항 - 합집합연산을 할 때, W배열 사용하여 발생하는 비용 계산 시간복잡도O(N + M) : M개의 친구관계마다 merge연산(+find연산) + N개 노드와 merge연산(+find연산) https://github.com/jongwuner/Algorithm/blob/master/BOJ/16562.cpp 12345678910111.. 더보기 이전 1 2 다음
