mojo's Blog

를 priority_queue에 push 한다고 했을 때, pop을 10번 한 결과가 value 값이 가장 크도록 하면서 동일한 경우에 index 값이 작도록 하는 결과가 10개 저장하도록 하는 것을 구현해보겠습니다. 일단 value 값이 가장 크도록 하기 위해 최대 Heap 으로 구현했습니다. (Root의 index는 0으로 설정하였음) 최대 Heap 의 Push 하는 함수 int heapSize; int index[100000], Heap[100000], A[10], B[10]; void heap_Push(int i, int value) { Heap[i] = value; index[i] = i; // Heap 구현 int cur = i; while (cur != 0 && Heap[cur] > Heap..

문제 링크 => 16367번: TV Show Game (acmicpc.net) 16367번: TV Show Game Your program is to read from standard input. The input starts with a line containing two integers, k and n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000), where k is the number of lamps and n the number of game participants. Each of the following n lines contains t www.acmicpc.net SCC 를 활용한 2-SAT 문제이다. 이 문제는 3개중에 2개를 만족하도록 세워야 하는게 핵심이다. a, b, c가 ..

문제 링크 => 2207번: 가위바위보 (acmicpc.net) 2207번: 가위바위보 첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각각의 학생들의 선택을 나타내는 두 정수 x, y(1≤|x|, |y|≤M)이 주어진다. x가 양수일 경우에는 원장선생님이 x번째에 가위를 낼 거라는 의 www.acmicpc.net SCC를 활용한 2-SAT 문제이다. 이 문제의 핵심은 학생들은 가위, 바위만 낼 수 있고 학생이 i 번째와 j 번째에 가위, 바위 둘중에 하나를 랜덤으로 선택할 때 둘중 하나는 무조건 맞아야 한다. 이때, i 번째에 예상하는 것을 xi, j 번째에 예상하는 것을 xj 라고 할 때, (xi v xj) 가 True 이기 위해서 ~xi -> xj 또는 ~xj -> xi 가 True 임..

문제 링크 => 11281번: 2-SAT - 4 (acmicpc.net) 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 SCC를 활용한 2-SAT 문제이다. 이 문제는 2-SAT - 3 에서 출력해야 할 것이 추가되었다. x1, x2, x3, ..., xn 의 true / false 를 임의로 설정해서 출력하도록 해줘야 한다. 2-SAT - 3 에서 만들었던 코드에서 inDegree 를 추가하여 xi, ~xi 의 진입차수를 비교하여 답을 내는것이..

문제 링크 => 11280번: 2-SAT - 3 (acmicpc.net) 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 SCC 를 활용하는 문제이다. 여기서 기본으로 알아야 할 상식은 다음과 같다. 1. ~a v b 는 a -> b 또는 ~b -> ~a (대우) 로 표현이 가능하다. 2. SCC로 묶인 xi, ~xi (i = 1, 2, 3, ... , n) 에 대하여 i가 동일할 경우 xi, ~xi 가 동시에 있는 경우 무조건 False 이다. ..

문자열 공백 포함해서 받는 코드는 다음과 같다 string str; getline(cin, str); 위 방법을 이용해서 split 하도록 하는 코드는 다음과 같다 string str; getline(cin, str); istringstream ss(str); string stringBuffer; vector str_V; str_V.clear(); while (getline(ss, stringBuffer, ' ')) { str_V.push_back(stringBuffer); }