문제 https://www.acmicpc.net/problem/16915 16915번: 호텔 관리 첫째 줄에 방의 개수 N(2 ≤ N ≤ 100,000)과 스위치의 개수 M(2 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 초기 방의 잠금 상태가 1번 방부터 순서대로 주어진다. 0은 닫힌 상태, 1은 열린 상태이다. 셋째 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 2-SAT 문제에 대하여 모른다면 반드시 먼저 공부하고 옵시다. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이번 문제는 (A || B) &&(B || C) && (C || D) 와 같은 논리곱 정규형(Conjunctive normal..

문제 https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 2-SAT 문제에 대하여 모른다면 반드시 먼저 공부하고 오자. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이번 문제도 심사위원의 투표 A와 B중 하나는 반드시 영향이 있어야 하기 때문에 두 가지 변수로 절을 생성할 수 있는 2-SAT 문제이다. 각 절은 (A || B) 로 표현된다. 심사위원들의 투표를 토대로 함의 그..

문제 https://www.acmicpc.net/problem/11281 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 풀이 solved.ac 난이도: Platium 3 일단 2-SAT에 대하여 공부하고 문제를 풀어봅시다. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이전 문제에 해당하는 [백준] 2 - SAT - 3(11280) 문제를 먼저 해결하고 옵시다. 이번 문제에서 위..

문제 https://www.acmicpc.net/problem/11280 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 풀이 solved.ac 난이도: Platium 4 일단 2-SAT에 대하여 공부하고 문제를 풀어봅시다. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이번 문제에서 위의 2-SAT 해설과 다른 점이 있다면 두가지 변수가 or로 연결된 절(clause)이 직접 주..

Boolean 변수들에 대해서 참, 거짓의 결정을 여러 번 해야 하는 문제를 충족 가능성 문제(Satisfiability Problem, SAT)라고 합니다. 특히 그중에 선 괄호 안의 각 절(clause)에 최대 두 가지 변수만이 존재하는 경우를 2-SAT 문제라고 합니다. 예를 들어 다음과 같은 식은 각 절에 두 가지 변수를 가지고 있습니다. (A || B) && (B || C) && (C || D) (이처럼 각 절들이 && 로 연결된 수식을 논리곱 정규형(Conjunctive normal)이라고 합니다.) 이제 2-SAT로 해결해야 하는 문제인 알고스팟 회의실 배정(MEETINGROOM) 문제를 풀면서 2-SAT에 대하여 알아봅시다. 문제 https://algospot.com/judge/proble..

문제 algospot.com/judge/problem/read/GALLERY algospot.com :: GALLERY 감시 카메라 설치 문제 정보 문제 전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모 algospot.com 풀이 종만북 난이도: 중 이번 문제를 해결하는 힌트는 문제 속에 있다. 미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며, 모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다. 방문한 갤러리(노드)를 다시 가기 위해서는 지나왔던 복도(간선)를 지나야 한다는 것은 미술관 구조(그래프 구조)에 사이클..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 일반 DFS 문제 [백준] 텀 프로젝트(9466) - Gold 4 [백준] 빵집(3019) + 그리디 - Gold 2 DFS를 이용하는 알고리즘의 세부 분류들 정말 DFS만을 사용해서 해결하는 간단한 문제들보다는 이를 활용하는 알고리즘을 공부해보자. 위상정렬 문제 모음 [알고스팟] 고대어 사전(DICTIONARY) + DFS 위상 정렬 [백준] 장난감조립(2637) + 다이나믹 - Gold 2 [백준] 최종 순위(3665)★ + 큐 위상 정렬 - Gold 1 [백준] 알고스팟어(2848)★ + 큐..

문제 https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 강한 결합 컴포넌트(SCC,Strongly Connected Component)로 해결해야 하는 문제. SCC를 모른다면 굉장히 풀기 힘드니 먼저 공부하고 오자. 방향 그래프에서 두 정점이 서로 이동 가능한 경로가 있는 경우 해당 정점들은 같은 강한 결합 컴포넌트에 속한다. 예를 들어 아래의 방향 그래프에서 같은 SCC끼리를 ..

문제 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 강결합 컴포넌트(Strongly Connected Component)는 방향 그래프에서만 정의된다. 그래프에서 두 정점에 대해서 양방향으로 이동 가능한 경로가 모두 있을 때 두 정점은 같은 강결합 컴포넌트(SCC)에 속한다. 즉, 그래프의 사이클에서 같은 사이클 내에 존..

절단점/단절점(Articulation point / Cut vertex) 절단점이란 무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서브 그래프)로 나뉘는 정점을 의미한다. 해설 게시글 [백준] No.11266 - 단절점 (C++, Articulation point) 절단선/단절선 (Bridge / Cut edge) 절단선이란 무향 그래프에서 간선을 지웠을 때 그래프가 두 개 이상의 컴포넌트로 나뉘는 간선을 의미한다. 절단점을 먼저 공부하고 보면 쉽게 풀 수 있다. 해설 게시글 [백준] No.11400 - 단절선 (C++, Bridge)