1. 문제 설명 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 2. 아이디어 내가 떠올린 것은 아니고 union-find 알고리즘을 공부하기 위해 찾아본 문제였다. 애초에 1,000,000개의 정점을 BFS, DFS 같은 완전 탐색으로 구현해서 문제를 풀기엔 무리가 있어 보인다. 굉장히 재밌는 알고리즘인데 단순히 리스트에 정점과 간선을 넣는 방식이 아니라 인덱스 번호 자체가 정점을 의미하고 인덱스가 가..

1. 문제 설명 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net dp문제는 웬만하면 이제 풀이 방법이 너무 뻔히 보인다고 해야 하나.. 플래티넘치고는 쉬웠다. 2. 아이디어 DP문제일 거라는 생각은 들었는데 인덱스에 어떤 조건을 넣어줄까 생각해보니 왼쪽에서 보는 경우, 오른쪽에서 보는 경우는 필수로 들어가야 할 것 같고 패턴을 찾아보다보니 빌딩의 높이도 고려해줄 필요가 있음을 느꼈다. 정확하게는 dp[빌딩 수(= 최대 높이)][왼쪽에서 보이는 ..

1. 문제 설명 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 2. 아이디어 숫자 100,000개 주고 구간(1, 100,000)을 100,000줬다고 생각해보자. O(N) 알고리즘으로 구현해도 2초 안에 해결하기란 무리다. 그렇기 때문에 min(), max()함수를 사용하겠다는 얄팍한 생각으로는 이 문제를 찢을 수 없다. 시간복잡도 O(logN)를 가지는 알고리즘이 필요한데, log면 보통 트리다. 즉 ..

1. 문제 설명 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번째 줄 www.acmicpc.net 2. 아이디어 sum() 함수를 사용해서 풀겠다는 얄팍한 생각으로는 찢을 수 없는 문제다. 시간복잡도 \(O(N)\)이 걸리는데 최악의 케이스 N*K (1,000,000 * 10,000)만 고려해주어도 벌써 백억이 넘어가니 2초 내에 해결할 수 없다. 이걸 해결할 만한 방법은 어딘가 구간합을 계속 '저장'하고 '업데이트'시..