지난 글에 이어서 더 빠른 최대 유량 알고리즘인 디닉 알고리즘.에드몬즈-카프는 bfs를 활용하며 O(VE2) 안에 문제를 해결할 수 있다. 간선에 대한 지수시간이기 때문에 정점의 수와 무관하게 간선이 여러 개라면 bfs에서 너무 많은 시간을 소모하게 된다. 하지만 디닉은 정점에 대한 지수시간 O(V2E) 안에 문제를 해결한다.디닉 알고리즘의 순서는 이렇다.유량 그래프 = G, source = s, sink = t1. G의 레벨그래프 L을 만든다.  a. s로부터 t까지의 bfs로 깊이는 각 정점의 레벨이 된다.  b. t의 레벨이 정의되지 않으면 모든 작업을 멈춘다.2. L에서 다음 작업을 반복한다.  a. dfs로 s→t의 증가경로를 찾는다.  b. 증가경로의 최소 컷을 찾아 경로에 유량을 생성한다.3..

1. 최대 유량 문제정점 간에 흐를 수 있는 양이 있을 때 그 최대치를 간선으로 표현하면 하나의 방향 그래프가 나온다. 두 정점 사이에 흐를 수 있는 최대 양을 용량(capacity), 두 정점 사이에 흐르고 있는 양을 유량(flow), 현재 남아있는 용량을 잔여용량(residual)이라고 한다. 예를 들어 파주에서 안양에 이르는 수도권 서부의 도로 교통용량을 대충 다음과 같이 표현할 수 있다.(실제로 이런 상황에다가 써먹지는 않는 듯 하다.)그렇다면 이 그래프 외의 다른 연결을 전부 무시하고 모든 도로가 전부 비어있다고 가정했을 때 파주에서 안양까지 이어지는 도로 교통용량의 최대치는 얼마일까?자유로에서 서부간선도로를 타면 파주-일산-고양-서울-안양으로 이어진다. 이 경로에 따르면 일산~고양 구간이 용량..

시간 제한메모리 제한2초1024MB문제사람들이 N행 M열의 직사각형 모양으로 모여 있다. 초기에 각각의 사람의 상태는 정상 체온이거나 저체온증이고, 낮과 밤을 지나면서 사람들의 상태가 변화한다.낮은 따뜻하기 때문에 저체온증인 사람이 정상 체온으로 회복할 수 있는 기회이다. 어떤 사람과 사방으로 인접한 두 명 이상의 사람이 정상 체온이라면 따뜻한 체온을 나눠 받아 저체온증에서 정상 체온으로 회복된다. 어떤 사람이 정상 체온으로 회복된 후에는 같은 방법으로 인접한 다른 사람들이 정상 체온으로 회복할 수 있으며, 이러한 체온 회복 과정은 낮 사이에 충분히 많이 반복될 수 있다.밤은 춥기 때문에 정상 체온인 사람들이 저체온증에 걸릴 수 있다. 단, 밤 사이에 새롭게 저체온증에 걸리는 사람은 K명 이하이다.낮과 ..

1년 반의 세월을 건너 드디어 다음 버전으로 업데이트를 하게 되었다. 실용성을 갖고 지속적으로 활용될 수 있는 프로그램을 작성, 관리하는 일이 "개발"이라고 한다면 내가 해오는 일들은 개발이라고 보기 어렵다. 돈을 받고 한 일도 아니고 댓가를 바라고 있는 것도 아니지만 비유해보자면 자동차 회사가 차를 만들고 수십년이 지나도록 신형 차를 만들지 않는 것과 똑같다. 나는 프로그램을 만들었고 방치했다. 물론 바빠서도 큰 이유였지만 이걸 업데이트 하는 일이 귀찮았다는 사실을 부정할 수 없다. 그리고 변호하자면 어려운 과정이 있었다. 1. 주석 달기지난 작업에 주석을 충분히 달아놓지 않은 것은 굉장히 멍청한 짓이었다. 1000줄 꼬박 넘는 작은 규모의 프로그램이긴 하지만 정식적인 개발 경험이 없어서 규격화되지 않..

23829번: 인문예술탐사주간태영이는 SASA의 축제라고 불리는 "인문예술탐사주간"을 보내게 되었다. "인문예술탐사주간"을 맞이하여 세종호수공원에 가게 된 태영이는 아름다운 경치에 놀라움을 금치 못했다. 세종호수공원www.acmicpc.net 만약 태영이의 위치가 0이라면 사진의 점수는 모든 나무의 위치 총합이 된다.태영이의 위치가 X일 때, X 오른쪽 나무들로 얻는 점수는 각 나무의 위치에서 X를 뺀 값의 총 합이 된다. X 왼쪽 나무들의 점수는 X에서 나무의 위치를 뺀 값의 총합이 된다. 결국 점수는 특정 위치로부터의 누적합이 되는 셈이다. i번째 나무까지의 누적합을 prepix[i]에 저장한다. 그림으로 보면 아래와 같다. 태영이가 13에 있다면 a와 b는 이렇게 그려볼 수 있다. 파란색이 빼야 하..

시간 제한메모리 제한1초128MB문제학생회장을 하고 있는 상근이는 이번 학교 축제 행사로 학우들간의 친밀감을 돈독히 하고자 줄다리기를 하려 한다. 하지만 이 줄다리기에 형평성을 최대한 고려하기위해 두 팀간의 사람 수 차이를 1 이하로 하려하며, 두 팀간의 몸무게의 차이가 최소화되도록 하고자 한다. 이때 상근이가 나누려 하는 두 팀의 몸무게를 각각 출력 하시오. 입력가장 첫 번째 줄에 줄다리기를 하기 원하는 총 인원의 수(1 ≤ N ≤ 100)가 주어진다. 이후 N개의 줄에 줄다라기에 참여하기 원하는 사람의 몸무게(1 ≤ K ≤ 450)가 주어진다. 출력두팀의 몸무게를 작은 순서대로 순차적으로 출력한다. 풀이N명이 주어졌을 때, 한 팀에 있을 수 있는 최대 인원은 N//2명 또는 N//2+1명이다. 여기서..

시간 제한메모리 제한1초128MB문제대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다. 대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다) 고속도로가 서로 교차하..

파이썬의 Boolean타입 파이썬에서는 True를 대체할 수 있는 다양한 수단이 존재한다. 예를 들어 이런 것들 numbers = map(int, input().split()) count = 0 while numbers: numbers.pop() count += 1 print(count) numbers 배열의 길이가 0이 아니라면 while에 True로 전달된다. 또는 이런 것 k = 0 k = int(input()) if k: print("k has been changed") else: print("k is still zero") k의 값이 0이라면 if문에서 False로, 0이 아니라면 True로 전달된다. (정확히는 아님) 따라서 이런 표면적인 현상에 익숙해지면 이런 끔찍한 실수를 저지를 수 있는데..