728x90 반응형 분류 전체보기325 [Algorithm] network flow (포드 풀커슨, 에드몬드 카프) 최대 유량 파이썬 구현 Network flow 다음과 같은 그래프가 있다고 하자. 각 에지의 가중치는 용량인데 용량은 흐를 수 있는 유량의 최대량이다. 네트워크 플로우 문제는 시작점 s에서 t까지 보낼 때 최대값을 가지는 플로우를 구하는 문제이다. a/b라고 할 때 b는 유량의 총량인 용량을 의미하고 a는 현재 흐르는 유량을 의미한다. 당연히 a가 b보다 클 수는 없다. 다음 그림은 s에서 5만큼 t로 보낼 때의 예시이다. 최소 컷 컷이란 노드들을 두 개의 집합으로 분할하는 것이다. 시작점 s와 도착점 t는 서로 다른 집합에 있어야 한다. 아래는 두 집합 { s, a, c, d } 와 { b, t }로 나눈 예시이다. 다음과 같이 a->b, d->b, d->t 간선들이 컷에 속해있다. 해당 간선들의 비용 총합을 컷의 비용 총합.. 2023. 6. 16. [AWS] EC2 인스턴스 t 타입. 프리티어 EC2 인스턴스 먹통되는 현상 (502 bad gateway) 프로젝트를 진행하면서 스프링부트 API 서버를 EC2에 배포하였다. 프론트 분들께서 개발하시도록 API 서버를 24시간 동안 가동하였는데 EC2 인스턴스가 얼마 가지 못하고 계속 먹통이 되는 현상이 발생하였다, 보통 아래와 같은 현상이 발생하였다, 응답까지 시간이 매우 오래 걸린다. 502 bad gateway 에러가 발생한다. 임시 방편으로 EC2를 중지하였다가 다시 실행 후 서버를 다시 배포하면 괜찮아졌으나 이마저도 1시간도 채 지나지 않아서 다시 먹통이 되는 현상이 발생하였다. 뭔가 내가 놓치는 부분이 있을 거라 생각하여 EC2 프리티어 인스턴스 타입인 t2.micro에 대해서 알아보았다. 먼저 EC2의 유형을 보기위한 방법은 다음과 같다. t 2 . micro (인스턴스 타입) (세대) (크기) .. 2023. 6. 15. [Network] SDN(Software Defined Networking) Per-router control plane 기존 네트워크 상의 라우터들은 다음과 같은 구조를 하고 있다. 라우팅 알고리즘을 통해 최적의 경로를 계산하고 적절한 출구로 패킷을 보낸다. 라우터 하나가 소프트웨어적인 부분과 하드웨어적인 부분 모두를 담당하는 구조였다. 하나의 라우터에 control plane과 data plane이 같이 있는 모습을 볼 수 있다. 그런데 라우팅 알고리즘은 각 라우터들의 control plane 끼리 상호작용한다. 그래서 이러한 control plane을 따로 분리하여 중앙 서버에서 제어를 담당하는 구조가 제시되었다. Logically centralized control plane Logically centralized control plane의 경우 위 그림에서 보다싶이 co.. 2023. 6. 14. [백준 11657][파이썬] 타임 머신 (벨만 포드) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 음의 간선을 포함하고 있기 때문에 다익스트라가 아닌 벨만 포드 알고리즘을 사용한다. 무조건 음의 간선을 포함한다고 문제가 생기는 것은 아니다. 정확히는 음의 간선이 포함된 사이클이 최단 거리를 - ∞로 만들 때 문제가 발생한다. 다음과 같은 음의 사이클은 문제가 되지 않는다. 사이클을 반복하면 비용이 증가하기 때문에 최단 거리를 구하는 .. 2023. 6. 13. 이전 1 ··· 29 30 31 32 33 34 35 ··· 82 다음 728x90 반응형
