1. 최대 유량(Network Flow) 문제최대 유량 문제는 유량이 시작되는 소스(source)와 유량이 도착하는 싱크(sink)가 존재하는 그래프에서 최대로 생성될 수 있는 유량을 찾는 문제입니다. 그래프의 간선들을 타고 유량이 흐르는데 보통 방향 그래프가 다뤄지는 경우가 많으나 방향이 없는 그래프가 주어지기도 합니다. 각 간선들은 흐를 수 있는 유량의 제한인 용량(capacity)이 있습니다. 이 문제를 해결할 수 있는 방법을 처음 제안한 두 사람의 이름을 딴 포드-풀커슨 알고리즘이 있습니다. 이 알고리즘은 방법론에 대한 내용이고 에드몬드-카프 알고리즘에서 O(VE^2)의 BFS를 통한 유량의 증가 경로 탐색 방법이 제시되었습니다. 이후 레벨 그래프를 활용해 O(V^2E)로 개선한 디닉(디니츠) 알..

1. 세포 자동자(Cellular Automata)세포 자동자(CA)란, 유한하게 정의된 상태를 가질 수 있는 셀을 규칙적으로 배치하여 서로 관련있는 셀들이 영향을 주고 받으며 변화하는 모형을 말합니다. 뭐라고 복잡한데 이런 문제가 있어요.백준 7569번 : 토마토"익은" 상태의 토마토가 인접한 "익지 않은" 상태의 토마토를 익게 하는 규칙입니다. "토마토가 없는" 상태의 칸은 영향을 받지 않습니다. 이 문제는 3차원으로 나열된 각 칸이 셀이 되고 토마토가 익었거나 익지 않았거나 없는 3가지 상태를 갖는 세포 자동자라고 볼 수 있습니다. 2. 생명 게임(Game of Life)존 콘웨이가 만든 게임입니다. 이 게임은 초기 상태만 정해주면 그 뒤는 규칙에 따라 알아서 흘러가는 감상 게임이에요. 존 콘웨이는..

https://www.acmicpc.net/problem/32721 시간 제한메모리 제한1초1024MB문제건덕이가 설립한 오리 왕국은 1부터 N까지 N개의 도시로 이루어져 있다. 각 도시는 다른 도시로 향하는 일방통행 도로를 단 한 개만 가지고 있다. 왕국을 다스리던 건덕이는 어떤 도시에서 도로를 이용해 도달할 수 없는 도시가 있음을 알아챘다. 건덕이는 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 도로를 최소한으로 수정하기로 했다. 건덕이는 도로를 아래와 같은 방법으로 수정한다. 도시 A에서 출발하는 도로의 목적지를 수정한다. (1 ≤ A ≤ N ) 건덕이를 위해 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 만드는 도로의 최소 수정 횟수를 구해주자! 입력첫째 줄에 도시의 개수 N..

import sysinput = sys.stdin.readlinet = [(-1, 0), (1, 0), (0, -1), (0, 1)]d = [(-2, 0), (2, 0), (0, -2), (0, 2)]def bin_check(): ret = 0 t = 1 for j in range(3, 6): if grid[0][j]: ret |= t t 여기에 찾았던 기록들 set으로 관리해주면 되는데 그 부분 커밋 안해서 사라짐

1. SCC문제1) SCC 구성하기백준 2150번 Strongly Connected Component백준 11097번 도시 계획 : 최소 간선으로 scc를 만족하는 그래프 만들기백준 25488번 토큰 : [★★★] scc별 빨간 카드, 파란 카드에 적힌 숫자의 수 비교하기백준 1506번 경찰서 : [★★] scc마다 최소 비용만 찾아서 다 더하기 2) a에서 b까지 가장 많은 정점을 방문하는 경로백준 1471번 사탕 돌리기 : [★★★] 모든 정점의 진출차수가 1인 그래프백준 19649번 미담 전하기 : 직접 전파자를 포함하지 않아야 하는 조건 처리가 까다로움백준 2152번 여행 계획 세우기 : [★★★] 같은 컴포넌트의 요소들은 크기만 알면 방문한 셈 칠 수 있음백준 4013번 ATM : [★★★★★]..

이걸 그리면 좀 기억하는데 도움이 될까 싶었는데도움은 별로 안 된 것 같고요...

시간 제한메모리 제한10초 / 3128MB / 128MB문제https://www.acmicpc.net/problem/2782로맨틱왕: 최대 16개의 선물나무를 선택하거나, 선택하지 않을 수 있으며 선물나무를 선택할 때마다 왕이 1칸을 이동하는데 소모되는 시간이 1씩 증가한다. 왕은 처음에 1칸 당 1시간의 속도로 이동할 수 있다. 왕이 왕비가 있는 곳까지 제한 시간 내에 가져갈 수 있는 최대 선물의 수를 구하는 문제. 선물나무의 위치에 도착했다고 반드시 선물을 가져가는 건 아니고 선물나무마다 선물을 1개 까지 가져갈 수 있다. https://www.acmicpc.net/problem/8138Tourist Attractions: 1~n까지의 지점을 두고 연결 그래프의 형태로 그려진 관광지에서 1에서 출발해..

1. 외판원 순회 문제(TSP)외판원 순회 문제는 그래프 탐색 문제입니다. N개의 정점이 있을 때, 이 정점들을 중복하지 않고 모두 방문할 수 있는 최적의 방법을 찾는 것이 문제의 목적입니다. 즉, 가장 효율적인 해밀턴 회로를 찾는 문제라고 설명할 수 있습니다. 이 문제는 쿠팡맨들을 비롯한 택배 기사님들의 숙원이기도 합니다. 정해진 지점들을 중복하지 않고 한 번에 가장 빠르게 돌 수 있는 방법을 알 수 있다면 퇴근을 빨리 할 수 있을 거예요. 2. NP-hard하지만 택배 기사는 근무 강도가 높은 직종입니다. 그 이유는 바로 외판원 순회 문제가 다항시간 내에 해결할 수 있는 문제가 아니기 때문입니다. 아직까지 이 문제를 다항시간 내에 해결할 수 있는 알고리즘은 확인되지 않았고, 이 문제를 다항시간 내에 ..