출항사

각 노드간의 거리가 주어졌을때, A -> B로 이동하는 최소 시간이 C보다 작거나 같은지 확인하는 문제이다. 노드의 개수가 500개, 쿼리의 개수가 1만개이다. 노드의 개수를 N, 쿼리의 개수를 K라고 하자. 그렇다면 간선의 개수는 N^2개가 되는 것을 알 수 있다. 쿼리가 들어올때마다 다익스트라를 돌리면 O(KN^2 log N)의 시간복잡도가 소요되기에 시간안에 문제를 해결할 수 없다. 따라서 N이 작은 것을 이용하면 되는데, 플로이드 와샬을 사용하면 된다는 것을 눈치챌 수 있다. O(N^3)에 모든 노드간의 거리를 전처리 해놓는다면 쿼리를 해결하는데 O(1)의 시간복잡도가 걸린다. 따라서 O(N^3)에 문제를 해결할 수 있다. #include #define MINF 0x7f7f7f7f #define ..

동전 2개가 주어질때, 하나의 동전만 떨어뜨리도록 적절히 움직이라고 한다. 최대 움직일 수 있는 횟수가 10회인점에 집중해보자. 매번 움직일 수 있는 경우의 수는 최대 4회이다. 따라서 4^10번의 경우의 수를 전부 돌려 동전 중 하나만 밖으로 나가는 경우가 존재하는지 확인하면 된다. 움직인 방향을 vector로 관리하고, 이 vector에 들어있는 방향으로 시뮬레이션을 돌려 움직여보자. 이때 하나의 동전만 밖으로 나가는 값을 찾으면 된다. 4^10번 만큼 경우의 수를 찾고, 시뮬레이션을 돌리는 최대 움직임이 10회이므로, 시간복잡도 O(4^10 * 10)에 문제를 해결할 수 있다. #include #define MINF 0x7f7f7f7f #define INF 1000000000 #define MOD ..

문제는 길지만 간단하게 해결할 수 있는 시뮬레이션 문제이다. 4개의 톱니바퀴가 주어지고, 특정 톱니바퀴를 회전시킬 때, 양옆에 존재하는 톱니바퀴에 영향을 준다고 한다. 회전을 모두 수행했을 때 최종 상태를 맞추면 되는 문제이다. 톱니바퀴는 시계 방향, 반시계 방향으로 회전할 수 있다. 따라서 덱 자료구조로 톱니바퀴를 구현해주면 아주 간단하게 양쪽 방향의 회전을 구할 수 있다. 그다음은 쿼리가 들어올때마다 회전시키기만 하면 된다. 초록색으로 표시된 값들이 무엇인지가 중요하기에, 이를 기준으로 비교해 주고 회전의 영향을 퍼뜨려주면 된다. 주의해야 할 점은 각 톱니바퀴가 회전할 것인지, 한다면 어느 방향인지 모두 표시를 해놓은 후 한 번에 회전을 해야 한다는 점이다. 순차적으로 회전시키면 비교할 때 잘못된 계..

간단한 그리디 문제이다. N명이 방에 올 것이고, K번만 난로를 켤 수 있다. 이때 난로가 켜져 있는 시간을 최소로 해야 한다. 상황을 살짝 변형해서 생각해 보자. K번을 언제 켤지 생각하지 않고, 일단 N명이 들어올 때마다 전부 난로를 켤 것이다. 그러면 연결해야 하는 난로의 개수는 N-K개라는 것을 알 수 있는데 이제 이 값을 최소로 만들면 된다. 당연하게도 앞에 있는 사람과 나의 연결 값이 작아야 전체의 값이 작아진다. 따라서 나의 앞사람과 나 사이에 난로가 켜져 있는 시간들을 구하고 전부 배열에 넣어 오름차순 정렬하자. 그다음 앞에서부터 N-K명을 연결해 주면 항상 최소 시간을 유지할 수 있다. #include #define MINF 0x7f7f7f7f #define INF 1000000000 #..

간단한 다이나믹 프로그래밍 문제이다. 각 도시별로 [ 홍보 비용, 고객의 수 ] 정보가 주어진다. 이때 최소 C명을 모으기 위해 필요한 최소 비용을 구하라고 한다. 단, 도시별로 여러번 홍보할 수 있다. DP[i][j] = i번째 도시까지 j명을 모으기 위한 최소 홍보 비용이라고 정의하자. 그러면 점화식을 도출할 수 있는데, j가 i번째 사람의 고객의 수보다 크거나 같을때 DP[i][j] = DP[i][j-고객의 수] + 홍보 비용이 된다. 그리고 j가 i번째 사람의 고객의 수보다 작다면, DP[i][j] = DP[i-1][j]가 된다. 이를 2중 for문으로 구해주면 된다. 주의 해야할점은 '최소한 C명'이 되는 비용을 구하는 것이다. 따라서 j의 범위는 최댓값인 1100까지 잡고 점화식을 돌려야 한다..

정말 간단한 그래프 탐색 문제이다. 나를 기준으로 친구들과는 적대적인 관계이지만, 친구의 친구와는 우호 관계라고 한다. 이를 만족하는 그래프인지 확인해야 하는데, 그래프가 순환하는 형태인지 확인하면 된다. 왜냐면 트리 구조일 경우에는 무조건적으로 위의 조건을 만족하기 때문이다. 자 그럼 그래프가 순환하는지 확인해보자. 현재 노드와 연결된 노드 중 이전에 방문한 적이 있음에도 나와 우호적인 관계로 표시된 노드가 있다면 그래프가 순환하는 상태라고 판단할 수 있다. 그래서 boolean 변수를 하나 두고, dfs 탐색에 조건문 하나를 추가해 이를 판별하도록 구현했다. #include #define MINF 0x7f7f7f7f #define INF 1000000000 #define MOD 1000000009 #..

이분탐색 + 우선순위 큐 자료구조를 사용해야하는 문제이다. N개의 재료중 Oi가 1인 재료 K개를 제외했을때, 세균의 합이 G이하라면 먹을 수 있다. 이때 최대 유통기한을 얼마나 만들 수 있을까? 문제를 보자마자 이분탐색인걸 파악했다. mid로 날짜를 대입해보면서 만족하는 최대 mid를 구하면 되겠다 싶었다. 그러면 K개를 어떻게 선정할까? 그리디하게 생각해보고 싶지만, Si * max(1, x - Li)를 항상 보장할 수는 없다. 그래서 우선순위 큐에 현재까지 뽑은 재료 K개를 유지하도록 접근해봤다. mid를 이용해 모든 세균의 합을 구하고, 마지막에 우선순위 큐에서 K개의 재료로 인해 발생한 세균을 빼주면 간단하게 구할 수 있다. 날짜는 최대 20억이 가능하므로 left = 1, right = 2e9..

[Docker] Docker Swarm Service 스웜 모드 서비스 개념 Docker Swarm 모드를 사용하지 않고, 사용하는 도커 명령어의 제어 단위는 컨테이너이다. 예를 들어 docker run 명령어는 컨테이너를 생성하고, docker rm 명령어는 컨테이너를 삭 jojaeng2.tistory.com 이전에 Docker Swarm Service를 생성하고 사용해 봤다. Docker Swarm은 사용법이 어렵지 않아 3대의 서버에 Cluster를 쉽게 구축할 수 있었지만, 서비스가 업데이트돼야 할 때마다 매번 manager 노드로 가서 업데이트하는 작업이 귀찮다고 느껴졌고 CI/CD 파이프라인을 구축하기로 결정했다. 큰 흐름은 아래의 그림과 같다. Worker Node에 대한 설정은 이전 글에 ..