CS/APS (19) 썸네일형 리스트형 [Baekjoon Online Judge] 2230. 수 고르기 (C++, Java) https://www.acmicpc.net/problem/2230핵심N은 최대 100,000모든 두 원소의 차를 비교하려면 시간복잡도가 O(N^2)이다. (시간초과)한 원소에 대해 조건에 맞는(차가 M 이상이면서 가장 작은) 원소를 빠르게 찾을 수 있다면, 시간복잡도를 줄일 수 있다.방법 1. 이분 탐색A[i] + M에 대한 Lower Bound는 위 조건에 맞는 원소의 인덱스와 동일하다.이를 모든 i에 대해 찾고 차를 비교하면 된다.시간복잡도는 O(NlogN)방법 2. 투 포인터 알고리즘1. 정렬 후 두 개의 포인터를 시작 지점에 둔다. (i = 0, j = 0)2. 두 원소의 차가 M보다 커지는 지점까지 j를 옮긴다.3. 차가 지금까지의 차 중에서 가장 작다면, 갱신한다.4. i를 1증가 시키고 2~.. [Baekjoon Online Judge] 10815. 숫자 카드 (C++, Java) https://www.acmicpc.net/problem/10815핵심N과 M이 최대 500,000이다. 단순 탐색으로는 N개의 원소와 M개의 원소를 각각 대응시켜 봐야 하므로 시간복잡도 O(NM)이다. (시간초과)따라서 시간복잡도를 낮춰야 한다. 이분 탐색을 활용하면 M개의 각 원소에 대해 각각 O(logN)으로 탐색할 수 있다.전체 시간복잡도는 O(MlogN)으로 줄어든다. Code (C++)#include #include using namespace std;#define MAX_N 500000int arr[MAX_N];int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M, x; cin >> N; for (int i = 0; i > arr[i]; .. [Baekjoon Online Judge] 4179. 불 (Java) https://www.acmicpc.net/problem/4179핵심BFS를 이용해서 `불`이 각 위치에 도달할 수 있는 최소 시간을 구하기 BFS를 이용해서 `지훈이`가 불을 피해서 테두리로 갈 수 있는지 확인 Code (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { private static int INF = Integer.MAX_VALUE; private static Pair[] dirs = { new Pair(1, 0), new Pair(0, 1), .. 이전 1 2 3 다음
