복습 정리 노트

백준 BOJ 11281번 : 2-SAT - 4 문제 난이도 : Platinum III 알고리즘 분류 : SCC, 2-SAT 2-SAT에 맞는 식이 주어질 때 x1 ~ xN에 참 또는 거짓을 넣어 식 전체가 참이 되도록 만들 수 있는지 판별하고, 만약 가능하다면 식을 참으로 만드는 각 변수 x1 ~ xN의 값으로 가능한 것을 하나 구하는 문제이다. 식을 참으로 만들 수 있는지 여부의 판별은 2-SAT - 3의 풀이와 동일하다. 이제 식을 만족시키는 각 변수의 참/거짓 값을 찾아야하는데, 그리디하게 접근해보자. x → y라는 식이 거짓이 되는 경우는 x = true, y = false인 경우뿐이다. x = false이면 y는 true든 false든 관계없다. 식을 최대한 참으로 만들기 위한 최선의 전략은 노..

백준 BOJ 11280번 : 2-SAT - 3 문제 난이도 : Platinum IV 알고리즘 분류 : SCC, 2-SAT bool 변수 x1, ... , xn에 대해서 F = (xi ∨ xj) ∧ (xk ∨ xl) ∧ ... 와 같은 꼴의 식이 주어질 때, 변수들의 참 거짓을 적절히 설정하여 F의 값이 참이 되게 할 수 있는지 판별하는 문제이다. (a ∨ b)와 같은 식이 있을 때 a가 거짓이면 b가 참, b가 거짓이면 a가 참이라는 두 개의 식을 얻을 수 있고 이렇게 2M개의 식을 얻은 뒤 x와 ~x가 모두 참인 식이 하나라도 나오면 불가능, 나머지 경우는 가능이다. 이것은 SCC로 풀이 가능한데, 2N개의 노드에 대해 2M개의 간선을 모두 연결한 그래프를 만든 후 a와 ~a가 같은 scc에 속해있는 ..

백준 BOJ 13904번 : 과제 문제 난이도 : Gold III 알고리즘 분류 : 그리디, 우선순위 큐 N개의 과제들의 남은 날짜 수와 그 과제의 점수가 주어질 때, 하루에 하나씩 과제를 하여 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 먼저 문제들을 남을 일 수를 기준으로 오름차순 정렬해준 뒤, 우선순위 큐에 할 과제들만 남겨보자. 우선순위 큐에 과제를 하나씩 넣고 만약 우선순위 큐의 size가 방금 넣은 날짜 수보다 많다면 같아질 때까지 빼주면 된다. i번째 과제를 넣는 과정을 통해 i일까지 할 과제들을 우선순위 큐에 남긴다고 생각하면, 하루에 한 개씩 과제를 할 수 있으므로 i보다 많은 수의 과제가 들어있으면 안되기 때문이다. 더보기 #include #define int long long us..

백준 BOJ 1477번 : 휴게소 세우기 문제 난이도 : Gold IV 알고리즘 분류 : 이분 탐색 길이가 K인 도로 위에 N개의 휴게소가 있고, 여기에 M개의 휴게소를 더 지어 휴게소 간 거리의 최댓값이 최소가 되도록 할 때, 그 최솟값을 구하는 문제이다. 이분 탐색을 이용하여 풀이할 수 있다. 답을 m으로 두고 l ~ r 범위 내에서 이분 탐색을 하면서 휴게소 간의 거리를 m으로 두고 휴게소를 설치했을 때 휴게소가 M개 이하로 설치되었는지 확인하면서 값을 갱신해주면 된다. 주의할 점은 두 휴게소 사이의 거리가 x라면, 휴게소는 max(x-1, 0) / m개 설치된다. 왜냐하면, 예를 들어서 생각해보면 휴게소 사이의 거리가 100인데 거리 50으로 휴게소를 설치한다고 하여 휴게소가 2개 설치되지는 않기..

백준 BOJ 2150번 : Strongly Connected Component 문제 난이도 : Platinum V 알고리즘 분류 : 강한 결합 요소 (SCC) 방향 그래프가 주어질 때, 이들을 SCC로 나누어 출력하는 문제이다. 여기서 말하는 SCC(Strongly Connected Component)란, 한 Component 내의 어떤 두 점 사이에도 이동이 가능한 요소를 말한다. (SCC를 나눌 때는 당연히 한 Component의 크기가 최대가 되도록 나누어야 한다.) 그래프를 입력받고 adj 벡터에 간선들을 저장해주는 부분은 기본적이므로 설명을 생략한다. 이제 DFS 방식으로 노드들을 탐색하며, 노드 번호를 방문하는 순서대로 오름차순으로 매긴다. (nnum 벡터에 저장) 즉, 번호를 먼저 매기는 것..

백준 BOJ 24411번 : Stamp Combinations 문제 난이도 : Silver I 알고리즘 분류 : 누적 합, 해시를 사용한 집합과 맵 길이 N인 수열에 대해, 앞의 부분합과 뒤의 부분합의 합으로 쿼리로 입력된 값을 만들 수 있는지 구하는 문제이다. 이 때 N x Q(쿼리의 수) ≤ 10^7이다. 누적 합을 사용하는 것은 확실해보이나, 누적 합을 사용하더라도 O(N^2)에 돌아간다. 따라서 시간 복잡도를 조금 더 개선할 방법을 찾아보아야 한다. v_i를 1 ~ i번째 원소의 합이라고 하자. 그러면 뒤쪽 부분의 합은 v_N - v_i이고, 앞쪽 부분은 쿼리 값이 x라고 했을 때 x - (v_N - v_i)이다. map을 활용하여 v_0 ~ v_N 값들을 모두 저장해두고 m[x - (v_N - ..

백준 BOJ 16287번 : Parcel 문제 난이도 : Platinum V 알고리즘 분류 : 중간에서 만나기 (밋 인더 미들), DP N개의 물품 중 "서로 다른" 물품 4개를 골라 그 무게의 합이 M이 되도록 하는 경우가 있는지 확인하는 문제이다. 우선 N이 5,000이므로, O(N^4) 같은 방법은 안 된다. 각 원소는 최대 20만이므로, 두 원소의 합을 배열에 저장하고, 나머지 두 원소의 합을 배열의 기록을 이용하여 비교해보는 방식을 사용해볼 수 있다. O(N^2) 시간에 두 원소의 합을 구성하는 원소의 주소를 u, w에 저장한다. 다음으로 O(N^2) 시간에 나머지 두 원소의 합이 기록된 것들 중에서 주소가 둘 다 겹치지 않는 것이 있으면, YES를 정답으로 출력해주면 되고 그러한 조합이 하나도..

백준 BOJ 6325번 : Definite Values 문제 난이도 : Silver V 알고리즘 분류 : 트리를 사용한 집합과 맵 N개의 (변수) = (변수) 꼴의 수식이 주어지고, 처음에는 a만 값이 제대로 지정되었다고 할 때, 모든 등식이 적용된 이후 값이 제대로 지정된 변수의 목록을 구하는 문제이다. set을 사용한다. a = b라는 등식에서, a가 값이 지정되지 않고 b가 지정되었다면 a는 제대로 된 값이 지정된다. (set에 insert 해준다.) 반대로 a가 값이 지정되고 b가 지정되지 않았다면 a의 값은 쓰레기 값으로 덮어진다. (set에서 erase 해준다.) 이 과정을 N번 반복한 다음 set의 모든 원소들을 출력해주면 된다. #include #define int long long usi..

백준 BOJ 18869번 : 멀티버스 II 문제 난이도 : Gold V 알고리즘 분류 : 값/좌표 압축 두 집합에 대해, a_i, a_j와 b_i, b_j의 대소 관계가 모두 같다면 두 집합은 동일하다고 할 때, N개의 집합에 대해 몇 개의 집합 쌍이 동일한지를 구하는 문제이다. 각 집합에 대해 좌표 압축을 수행해주면, 원소들의 대소 관계가 같은 집합은 동일한 원소들을 가지게 된다. 이를 활용하여 좌표 압축을 N번 반복해준 뒤 브루트포스로 답을 구해주면 된다. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int M, N; ci..

백준 BOJ 17272번 : 리그 오브 레전설 (Large) 문제 난이도 : Gold I 알고리즘 분류 : 분할 정복을 이용한 거듭제곱 N초를 길이가 1초인 스킬과 길이가 M초인 스킬로 구성하는 방법의 수를 구하는 문제이다. dp[N] = dp[N-1] + dp[N-M]이라는 점화식을 세울 수 있다. 그러나 Large 문제에서는 N이 10^18 이하이므로 dp로는 풀이가 불가능하다. 따라서 점화식을 행렬로 구성하여 행렬의 거듭제곱으로 답을 구해주어야 한다. 위와 같이 점화식을 만들 수 있다. 참고로 M이 100 이하이므로, 행렬의 크기는 아무리 커도 100 x 100을 넘어가지 않는다. 위의 A 행렬을 N 제곱 해주면, 곱해지는 행렬은 a_0, a_-1, ...으로 구성되는데, 정의에 의해 a_0 = 1..