문제 https://www.acmicpc.net/problem/10265 10265번: MT 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 SCC로 새롭게 구성한 컴포넌트 별로 최대, 최소 인원을 파악해 배낭 문제로 값을 구해야 했던 문제로 굉장히 어려웠다.. 일단 인원 마다 같이 가고 싶은 인원(pick)을 가리키도록 그래프로 표현해보자. 1번 인원이 2번 인원과 가고 싶다면 다음과 같이 표현된다. 관계를 이런식으로 나타냈을 때 예제의 입력인 12 3 2 3 4 5 6 7 4 7 8 8 12..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 DSF문제 중에서도 그리디 알고리즘으로 해결하는 문제이다. 항상 최선의 선택을 하는 그리디 방식으로 이번 문제를 해결하면, 다음의 세 가지 경로 선택 중에서 다음과 같은 우선순위를 정하면 된다. 1. 오른쪽 위를 방문 2. 오른쪽을 방문 3. 오른쪽 아래를 방문 이런 식으로 오른쪽 위를 항상 먼저 방문한다면 생성되는 파이프 라인을 최대한 오른쪽 위로 밀착시킬 수 ..

문제 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)이 직접 주..

문제 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)에 속한다. 즉, 그래프의 사이클에서 같은 사이클 내에 존..

문제 https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 이전 문제에서 단절점/절단점(무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서브 그래프)로 나뉘는 정점)에 대해서 다루었다. 이번에는 무향 그래프에서 간선을 지웠을 때 그래프가 두 개 이상의 컴포넌트로 나뉘는 간선인 절단선/단절선(Bridge / Cut edge)에 대한..

문제 https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 DFS를 응용하여 해결할 수 있는 문제들 중에 하나인 절단점/단절점(Articulation point / Cut vertex)에 대한 문제이다. 절단점(Articulation point / Cut vertex) 절단점이란 무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서..