복습노트 복습노트

문제 11281번: 2-SAT - 4 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 이전에 있던 문제 에서 주어진 변수 n개를 각각 true인지 false인지 출력해주는 문제입니다. 변수가 true 이면 1을 출력하고, false이면 0을 출력합니다. 나머지 코드들은 모두 동일하므로 추가된 코드를 설명하겠습니다. reverse(SCC.begin(), SCC.end()); scc의 벡터를 뒤집습니다. 왜냐하면 위상정렬로 정렬해주어야 하기 때문입니다. 타잔 알고리즘 특성상 scc의..

문제 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net n개의 변수와 m개의 절(x ∨ y)이 주어집니다. 다음과 같은 식이 주어지면 변수에 true나 false를 넣어서 전체식이 true가 될 수 있는지 구하는 문제입니다. ∧ : AND 연산 ∨ : OR 연산 ㄱ : NOT 연산 예를 들어 위의 식은 x(1) = false, x(2) = false , x(3) =true 로 전체식을 true로 만들 수 있습니다. 반면에 위의 식은 x(1)어 어떤 ..

문제 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net SCC알고리즘를 사용하여 주어진 방향 그래프에서 SCC의 갯수와 각각의 SCC 구성 노드를 차례대로 출력하는 문제 입니다. SCC를 추출해주는 알고리즘은 타잔 알고리즘을 사용 하였습니다. vectorv[10001]; //주어진 그래프 정보 저장 ll dfsn[10001];//방문 순서를 저장할 배열 ll scc_count; //scc의 갯수를 세는 변수 ll sn[10001]; //x..

문제 2180번: 소방서의 고민 첫째 줄에 화재 발생 건수 n이 주어진다. n은 200,000 이하의 양의 정수이다. 둘째 줄부터 n개의 줄에 각각 한 줄에 한 쌍씩 a와 b가 입력된다. a와 b는 40,000 이하의 음이 아닌 정수이다. www.acmicpc.net n개의 화재가 발생하고 소방수가 최소의 시간으로 화재를 진압하는 시간을 구하는 문제입니다. 화재를 진압하는 시간은 a * t + b로 n개의 a, b가 주어지고 t는 항상 0부터 시작합니다. 예를 들어 n이 3이고 a, b가 (2, 0), (1, 2), (0, 3) 이렇게 주어지면 최소시간은 5 입니다. (2 * t0 + 0) + (1 * t1 + 2) + (0 * t2 + 3) =5 우리는 화재를 최대한 빠르게 진압해야 하므로 어느 조건으..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의의 시작시간과 끝시간이 주어지면 회의시간이 서로 겹치지 않게 최대 몇개의 회의가 진행될 수 있는지 알아보는 문제입니다. 다음 시간이 주어졌다고 하면 빨간색 표시된 곳을 선택하면 서로 회의시간이 겹치지 않게 해서 총 4개의 회의를 진행 할 수 있습니다. 이를 통해 알 수 있는 사실은 회의가 끝나는 시간이 가장 이른것이 최적해라는 것을 알 수 있습니다. 이러한 구현방식은 Greedy 알고리즘을 통해 해결할 수 있습니다. 따라서 가장 먼저 회의가 끝나는시간을 기준으로 회의시작 시간이 기준 시간보다 먼저 시작하면 무시해주면 됩니다. 이러한 과정을 계속 해서 갱신해 나가면서 진..

문제 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net LCA알고리즘을 활용하는 문제입니다. N개의 노드 트리가 주어지면 연결된 노드에는 거리가 주어집니다. 이때 임의의 두 노드 사이의 거리를 구하면 됩니다. 1번 노드를 전체 트리의 루트 노드로 보고 value[x] 배열을 선언합니다. value[x] = 1번 노드부터 x번 노드까지의 거리 합입니다. 따라서 우리는 두 노드를 a, b라 할때 정답은 value[a] + value[b] - 2*value[lca(a, b)] 입니다. 예를 들어 5번 노드와..

문제 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net N개의 트리 정점이 주어지고 두 노드의 쌍 M개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇번인지 출력하는 문제입니다. naive하게 생각하면 시간복잡도가 O(N)이므로 범위가 커지게 되면 시간초과가 나게 됩니다. 따라서 Sparse Table 알고리즘 방식을 사용하였습니다. 먼저 par[x][y] = x노드의 2^y 부모 라는 배열을 정의합니다. 다음에 depth배열을 정의해줍니다. depth배열은 노드의 깊이를 저장한 배열입니다. LCA..

문제 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 정의역과 공역 문제 입니다. m개의 정수가 주어지면 각 정수마다 f(1), f(2)....f(m)의 위치를 갖습니다. 쿼리의 갯수 Q가 주어지면 Q개의 쿼리마다 정수 n과 x가 주어지면 n번의 f(x) 연산을 한 값을 출력하면 되는 문제입니다. naive하게 계산하면 총 O(n)번의 연산을 통해 계산 가능합니다. 하지만 m..