Doby's Lab

https://www.acmicpc.net/problem/4305 4305번: 성격 진단 테스트 각 테스트 케이스마다 정답을 출력한다. 한 줄에 하나의 그룹(partition)을 알파벳순으로 출력하며, 각 그룹의 알파벳순으로 가장 앞에 오는 원소 기준으로 그룹들도 알파벳순으로 출력되어야 한 www.acmicpc.net Solved By: SCC (Tarjan Algorithm) 문제에서 말하는 모순이라는 건 선택한 어떤 활동들이 같은 SCC 안에 있는지 묻는 것입니다. 문자형 변수들을 숫자로 바꾸어서 SCC를 구해주고, SCC끼리 정렬하여 출력하면 풀리는 문제였습니다. #include #include #include #include #define MAX 27 using namespace std; vect..

https://www.acmicpc.net/problem/2416 2416번: 문 첫째 줄에 수로의 개수 N (1 ≤ N ≤ 250,000)과 스위치의 개수 M (1 ≤ M ≤ 500,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 수로의 정보가 주어진다. 수로의 정보는 4개의 숫자로 이루어져 있고, a, sa, b www.acmicpc.net Solved By: 2-SAT, SCC 메모리 초과가 계속 나서 최대한의 최적화를 해보려 했지만 원인이 무엇인지 알 수 없었습니다. 그러다가 바보같이 SCC를 구하여 담아두는 2차원 vector배열이 필요 없다는 것을 알아내어 맞출 수 있었습니다. 2-SAT은 결국 각 변수가 몇 번째 SCC에 속하는지만 알고 있으면 된다는 걸 깨닫습니다. (물론 이 문제에 한정..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net Solved By: DFS 간선의 가중치를 2차원 배열을 선언하여 따로 관리하였는데 이는 메모리 초과가 뜹니다. 그래서 인접 배열에 pair형으로 향하는 노드와 그에 따른 가중치를 함께 관리하여 DFS를 통해 풀었습니다. 제일 긴 지름을 구하려면 leaf node에서부터 시작해야 합니다. leaf node부터 시작하려면 인접 배열에서 사이즈가 1인 노드부터 DFS를 돌리면 됩니..

2-SAT에 대하여 공부해봅시다. 2-Satisfiability의 약자로 boolean variable들의 충족 가능성을 묻는 문제입니다. BOJ 2-SAT 3(11280), 2-SAT 4(11281)를 기반으로 연구합니다. 공부하는 데에 도움이 된 블로그 링크들 1(https://blog.naver.com/kks227/220803009418) 2(https://everenew.tistory.com/140) 22.04.03 연구일지 CNF(Conjunctive Normal Form) 식을 true가 될 수 있게 boolean variable의 조합이 있는지 조합이 있다면 어떤 조합으로 이루어지는지 알아내는 알고리즘입니다. 2-SAT에서 CNF는 2-CNF로 이는 한 Clause당 boolean varia..

https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net Solved By: Sort 오래 걸리는 묘목을 순서로 정렬을 한 후, 오래 걸리는 묘목부터 빠르게 심어야 최소 일수를 구할 수 있음을 알 수 있다. 심는데 하루가 걸리므로 묘목을 담은 배열에 처음부터 1일씩 더해가며 걸리는 일수를 구해준다. 그리고, 시작일이 1일이므로 걸리는 최소일 수를 더하여 출력해준다. #include #include #include using n..

https://www.acmicpc.net/problem/7420 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net Solved By: Convex Hull (Graham Scan) 문제에서 주어진 그림 중 점선으로 이어진 선들이 구해야 하는 벽인 줄 알고, '저걸 어떻게 convex hull로 구하나..' 생각하다가 점선이 구해야하는 벽임을 깨달았습니다. 그래서, Graham Scan을 이용한 Convex Hull로 점들을 구해주고, 거리를 구해주며 저..

https://www.acmicpc.net/problem/2207 2207번: 가위바위보 첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각각의 학생들의 선택을 나타내는 두 정수 x, y(1 ≤ |x|, |y| ≤ M)이 주어진다. x가 양수일 경우에는 원장선생님이 x번째에 가위를 낼 거라는 www.acmicpc.net Solved By: 2-SAT, SCC #include #include #include #include #define MAX 20002 using namespace std; vector SCC; vector adj[MAX]; int visitedOrder[MAX]; int sccNum[MAX]; stack s; int order = 0, sccCnt = 0; int n, m;..

https://www.acmicpc.net/problem/1217 1217번: 하우스 M.D. 입력은 여러 개의 테스트 데이터들로 구성되어 있다. 각 데이터의 첫 줄에는 House의 규칙의 개수 N, 증세의 종류 M이 빈 칸을 사이에 두고 주어진다. 다음 줄부터 N개의 줄에 걸쳐 House의 규칙에 대 www.acmicpc.net Solved By: 2-SAT, SCC 문제 글의 일부분을 가져와봅니다. "House의 규칙이 2 -3이라면, 증세 2가 일어나고 동시에 증세 3이 일어나지 않은 경우 환자가 죽게 된다는 뜻이다." >> 이 말인즉슨, 증세 2가 일어나지 않고, 증세 3이 일어난다면 환자는 살 것이고, 증세 3이 일어나고, 증세 2가 일어난다면, 이 또한 환자는 살 것이라는 말입니다. >> NO..