본문 바로가기
반응형

Problem Solving242

백준 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.
백준 18138번 리유나는 세일러복을 좋아해 - 스위프트(Swift) 풀이 1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다. 2. 티셔츠와 카라를 이분 매칭 한다. 1. 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍에 대해 간선으로 연결한다. 티셔츠 집단과 카라 집단을 최대로 매칭 시켜야 하는 이분 매칭 문제이다. 먼저 각 티셔츠와 카라들을 그래프의 정점이라고 생각한 뒤, 세일러복을 만들 수 있는 모든 (티셔츠, 카라) 쌍을 간선으로 연결해 그래프를 만들어준다. 2. 티셔츠와 카라를 이분 매칭 한다. 이제 완성된 그래프에 대해 이분 매칭을 진행하면 된다. DFS를 사용하여 구현하였다. import Foundation var N = 0, M = 0 var Tshirts = Array(repeating: 0, count: 201) var co.. 2022. 3. 8.
반응형

티스토리툴바