16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 문제를 이해하는 데 시간이 좀 걸렸었다. 구현해야 할 내용을 정리하자면 아래와 같다. 1. 매 턴마다 MST를 만든다. 2. MST가 완성됐다면 MST의 비용을 출력하고, 해당 MST에서 가장 비용이 작은 간선을 제거한다. 3. MST가 완성되지 않았다면 해당 턴부터 마지막 턴까지 0을 출력한다. 문제에서 주어진 대로 계산했을 때 간선 개수는 최대 50만 개다. 그렇기 때문에 제거할 간선에 대한 표시..
분류 전체보기
16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 단순 그리디라고 생각해서 작은 것부터 자를 수 있는 만큼 잘라나가는 식으로 했지만 실패했다. 왜 틀렸을까 생각해 보니 1. 길이가 20인 롤케이크는 한 번 잘라서 길이 10인 롤케이크를 2개 만들 수 있다는 점 2. 길이가 10의 배수인 롤케이크를 길이가 10으로 나누어 떨어지지 않는 롤케이크 보다 먼저 자르는 게 이득일 것이라는 점 이 같은 점들을 고려해서 1. 10으로 나누어 떨어지는 것들을 오름차순으로 앞에 오도록, 2. 10으로 나누어 떨어지지..
배포 당시를 대략적으로 표현한 아키텍처 배경 제공받은 EC2에 기본적으로 UFW가 설치되어 있었고, 방화벽 설정을 UFW를 통해 관리했다. 모든 요청을 Nginx가 받고, 각 애플리케이션 컨테이너로 포워딩하도록 하고 싶었다. 세 컨테이너 모두 같은 Docker network에 포함시켜 뒀기 때문에 Nginx 설정에서는 proxy_pass http://container_name:port 이렇게 포워딩하도록 설정해 뒀었다. 상황 하지만 분명 8080 포트를 allow 한적 없는데, 로컬에서 http://domain:8080으로 요청을 보내니 응답이 오는 문제가 생겼었다. 직접 ufw deny 8080을 해봐도 정상적으로 요청이 가고 응답이 왔다. UFW가 적용되지 않은 이유 도커 공식 문서의 Packet f..
1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 어렵사리 냅색과 DP라는 생각을 떠올렸는데도 해결을 못 했었다;; 계속해서 DP를 시도하다가 재귀로 시도하여 통과했다. 재귀 부분 설명 배열의 인덱스는 유치한 고객 수이며 값은 비용이다. 하나의 도시를 0개부터 최대한으로 선택하는 경우까지 모두 비교. 최대한으로 선택하는 경우는 해당 도시 고객만으로 유치해야 할 고객을 넘어서는 시점으로 설정. 해당 도시에 N배를 투자했는데도 유치해야할 고객 수와 같거나 그에 미치지 못한다면 (현재까지의 비용 + 해당 도시의 ..
