문제 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. 오른쪽 아래를 방문 이런 식으로 오른쪽 위를 항상 먼저 방문한다면 생성되는 파이프 라인을 최대한 오른쪽 위로 밀착시킬 수 ..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 2-SAT 해설 [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 2-SAT 문제 목록 [백준] 2 - SAT - 3(11280) - Platium 4 [백준] 2 - SAT - 4(11281)★ + 답 출력하기 - Platium 3 [백준] 아이돌(3648)★ - Platium 4 [백준] 호텔 관리(16915) + 식 세우기 -Platium 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)이 직접 주..

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)★ + 큐..