본문 바로가기
반응형

구현11

프로그래머스 과제 진행하기 - C++ 풀이 1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다. 2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다. 3. 다음과제를 시작하기 전까지 텀이 존재하는 경우, 텀 동안 중단했던 과제들을 해결한다. 1. 시작시간을 기준으로 오름차순 정렬하여 순차적으로 시작한다. 시작시간에 맞춰 순차적으로 시작해야하므로, 시작시간을 기준으로 오름차순 정렬해둔다. 2. 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단한다. 중단된 과제들은 스택으로 관리한다. 만약 현재 과제를 끝내기 전에 다음 과제를 시작해야 하는 경우, 현재 과제를 중단해야 한다. 이때 중단된 과제들은 스택에 넣어둔다. 멈춰둔 과제가 여러 개일 경우.. 2023. 9. 5.
백준 2563번 색종이 - C++ 풀이 1. 도화지를 100X100 그리드로 나눈다. 2. 각 색종이를 추가하면서 그리드에 색종이가 붙어있음을 표시한다. 3. 모든 그리드를 탐색하면서 색종이가 붙은 그리드의 개수를 센다. 1. 도화지를 100X100 그리드로 나눈다. 색종이가 붙은 영역의 넓이를 구해야 한다. 넓이 계산을 쉽게 하기 위해 각 칸의 넓이가 1이 되도록 그리드를 그린다. 100X100으로 나누면 된다. 2. 각 색종이를 추가하면서 그리드에 색종이가 붙어있음을 표시한다. 각 색종이의 위치가 주어진다. 모든 색종이의 크기는 10X10으로 동일하므로, 색종이가 붙는 100개의 그리드를 순회하면서 해당 그리드에 색종이가 붙었음을 기록해둔다. 3. 모든 그리드를 탐색하면서 색종이가 붙은 그리드의 개수를 센다. 모든 색종이를 붙였으면 이제 .. 2023. 9. 4.
백준 14719번 빗물 - C++ 풀이 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 3. 그 중 더 낮은 블록 높이까지 빗물이 고이게 된다. 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 각 열마다 고이는 빗물의 양을 구한 뒤 합치는 방식으로 전체 고이는 빗물의 양을 구해준다. 이때 양 끝 열(제일 왼쪽과 오른쪽)에는 절대 빗물이 고일 수 없다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 빗물이 고이기 위해서는 그릇의 형태가 되어야 한다. 즉, 양쪽이 i열보다 더 높은 블록으로 막혀있어야 한다. (양 끝 열에는 절대 빗물이 고일 수 없는 이유이다.) 또한 그.. 2023. 7. 24.
프로그래머스 택배 배달과 수거하기 - C++ 풀이 1. 배달은 갈 때, 수거는 돌아올 때 한다. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 3. 배달할 상자와 수거할 상자가 모두 없어질 때까지 반복한다. 1. 배달은 갈 때, 수거는 돌아올 때 한다. 이동 거리를 최소화해야 한다. 물류센터에서 출발할 때 트럭을 배달상자로 가득 채우고 출발한다. 가면서 각 집에 상자를 배달하여 트럭을 비우고, 다시 물류센터로 돌아오면서 수거상자들로 트럭을 채워오자. 2. 최대한 먼 집부터 해결하는 것이 최적이다. 또한 이동 거리를 최소화하기 위해서는 최대한 먼 집부터 방문하는 것이 최적이다. (A= 0 || pp >= 0) { int dist = 0; // 트럭을 배달상자로 채움 truck = cap; // 배달은 갈 때 while (truck > 0 && dp >=.. 2023. 7. 22.
백준 17779번 게리맨더링 2 - C++ 풀이 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 가능한 모든 (x, y, d1, d2) 쌍은 N^4개, 선거구 나누기 시뮬레이션에 O(N^2)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(N^6). 이때 N=20이므로 브루트 포스로 해결할 수 있다. 선거구 나누기 시뮬레이션은 주어진 조건을 잘 구현하면 되고, 경계선으로 둘러싸인 5번 선거구는 DFS로 처리해주었다. #include #include #include using namespace std; const int INF = 987654321; int N; int A[20][20]; int board[20][20]; bool va.. 2022. 9. 18.
반응형

티스토리툴바