본문 바로가기
반응형

Problem Solving/BOJ228

백준 3259번 PEOPLE - C++(cpp) 풀이 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 1. N명의 거짓말쟁이 여부를 결정하는 모든 경우, 2^N가지를 전부 체크한다. N명의 거짓말쟁이 여부를 결정하는 모든 경우는 총 2^N가지이다. 각 경우가 유효한지 체크하는 데 O(2N)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(2N*2^N)이다. N이 최대 20밖에 되지 않으므로 브루트포스로도 해결이 가능하다. 2. 어떠한 경우가 해가 되려면, 해당 경우를 기준으로 했을 때 모든 사람들의 진술에 모순이 없어야 한다. 어떠한 경우가 유효한지 체크하려면, 해당 경우를 기준으로 모든 사람들의 진술에 모순이 존재.. 2022. 3. 18.
백준 1700번 멀티탭 스케줄링 - C++(cpp) 풀이 1. 이미 꽂혀있다면 스킵한다. 2. 빈 자리가 있다면 빈 자리에 꽂는다. 3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다. 1. 이미 꽂혀있다면 스킵한다. 이미 꽂혀있다면 스킵해도 된다. 2. 빈 자리가 있다면 빈 자리에 꽂는다. 빈 자리가 있다면 빈 자리를 채우면 된다. 3. 빈 자리가 없다면 가장 나중에 사용할 것을 뽑는다. 문제는 빈 자리가 없는 경우인데, 이때는 가장 나중에 사용할 것을 뽑는 것이 최적이다. 반대로 가장 나중에 사용할 용품이 아닌 것을 뽑았다고 치면, 그 전기용품 차례가 왔을 때 어차피 기존 것을 하나 뽑고 새로 꽂아야 하기 때문이다. #include #include #include using namespace std; const int MAX = 101; int N, K.. 2022. 3. 14.
백준 14891번 톱니바퀴 - C++(cpp) 풀이 1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다. 2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다. 1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다. 인접하면서 맞닿는 극이 반대인 톱니바퀴로만 전이가 일어날 수 있으므로, 그런 톱니바퀴들끼리만 간선으로 연결되어있다고 생각하자. 2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다. 회전 쿼리가 주어질 때마다 DFS로 회전의 전이를 시뮬레이션하면 된다. 전이는 회전하기 전의 상태를 기준으로 결정되기 때문에 rotate를 재귀 호출 이후에 실행해.. 2022. 3. 11.
백준 11277번 2-SAT - 1 - 스위프트(Swift) 풀이 1. 변수가 최대 20개이므로, 각 변수의 값을 정하는 모든 경우의 수는 2^20이다. 2. 비트마스킹을 사용하여 모든 경우를 계산해 결과가 true가 되는 경우가 존재하는지 확인한다. 1. 변수가 최대 20개이므로, 각 변수의 값을 정하는 모든 경우의 수는 2^20이다. 변수의 개수가 20개로 매우 작기 때문에 모든 경우를 고려해볼 수 있다. 각 변수마다 true/false 값 중 하나를 가지므로 모든 경우의 수는 2^20이다. 또한 각 경우의 결과값을 계산하는데 O(M)의 시간복잡도가 든다. 따라서 총 시간복잡도는 O(2^N*M). 2. 비트마스킹을 사용하여 모든 경우를 계산해 결과가 true가 되는 경우가 존재하는지 확인한다. Xi를 i번째 비트로 표현한다고 하면, 모든 변수가 false인 경우는 .. 2022. 3. 10.
백준 11378번 열혈강호 4 - C++(cpp) 풀이 1. 각 직원은 한 개의 일만 할 수 있으므로 각 간선의 용량이 1인 네트워크 플로우 문제로 생각할 수 있다. 2. 벌점을 받으면 추가로 일을 할 수 있고, 벌점의 합이 K이므로 source에서 시작해 K만큼의 용량을 각 직원에게 분산하는 정점과 간선을 추가한다. 3. 포드 풀커슨 알고리즘을 사용하여 최대 유량을 구한다. 1. 각 직원은 한 개의 일만 할 수 있으므로 각 간선의 용량이 1인 네트워크 플로우 문제로 생각할 수 있다. 2. 벌점을 받으면 추가로 일을 할 수 있고, 벌점의 합이 K이므로 source에서 시작해 K만큼의 용량을 각 직원에게 분산하는 정점과 간선을 추가한다. 3. 포드 풀커슨 알고리즘을 사용하여 최대 유량을 구한다. 포드 풀커슨 알고리즘의 시간 복잡도는 O((V + E) * F)... 2022. 3. 9.
반응형

티스토리툴바