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

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

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

어떤 그래프에서 정점을 제거했을 때, 그래프가 분리되어버리는 경우가 있습니다. 또는 간선을 제거 했을 때 분리되는 경우도 있습니다. 각각의 정점과 간선을 "단절점", "단절선"이라고 합니다. 1. 단절점의 특징단절점과 단절선이 갖는 중요한 특징이 있습니다. 하나의 연결그래프를 dfs로 탐색하면 탐색 경로가 트리의 형태로 남게 됩니다. 여기서 어떤 정점 n을 탐색했을 때 그 정점으로부터 탐색된 하위 정점들에서 n의 상위 정점으로 돌아가는 경로가 하나도 없다면 n은 단절점이 됩니다. 그러니까, n을 제거하면 그보다 하위에 있는 모든 정점들은 n보다 상위 정점에서 분리되어버립니다. 돌아가는 길이 없으니까요. 이거 뭔가 지난 번에 정리한 SCC와 비슷한 느낌인데, 단절점을 찾는 과정이 SCC의 일부이기 때문입니..

어떤 자연수 n이 소수인지 판별하는 좋은 방법이 여러 가지 있습니다. 우선 가장 근본인 2부터 n - 1까지의 수로 n을 나누어보는 방법이 있습니다. 약수가 1과 n 말고 또 있는지 확실히 알 수 있습니다. 그런데 n이 만약 1,000,000,007 같은 수라면, 혹은 2136279841-1처럼 답도 없이 큰 소수에 대해서는 실행 가능성이 좀 낮거나 아예 없습니다. 그리고 구현하기 쉽고 성능도 확실한 "에라토스테네스의 체"가 있습니다. 근데 이건 특정한 소수 하나를 판별하기 보다 N까지의 소수를 모두 구하는데 좋은 방법입니다. n까지의 모든 소수를 빠짐 없이 확실하게 구할 수 있는 결정론적인 성질이 있습니다. 하지만 역시 자릿수가 좀 커진다 싶으면 매우 느려지는 단점이 있습니다. 가장 최적화된 에라토스테..

1. 충족가능성 문제(Boolean satisfiability problem, SAT)여러 변수로 논리 값들이 주어졌을 때, 그 논리 값들로 이루어진 식이 참이 되는 논리 값의 상태가 존재하는가에 대한 문제입니다. 이거 약간 뭐랑 비슷하냐면 대학교 시간표 짜는 거랑 비슷합니다. 작년 연구부장 역임했던 바로 생각해보면 전담 시간표 짜는게 딱 이 SAT 문제 입니다. 제가 일반 종합대학을 다녀본 경험이 없으니 그냥 교육대학교에서 만났던 과목으로 생각해봅시다. (제가 다녔던 대학교는 사실 수강신청이랄 것도 없긴 했습니다. 그냥 예시 만들기 어려우니까 그런갑다 해봅시다.) 개설되는 다음 4개의 과목을 조건에 맞게 수강할 수 있는 방법이 있을까요?교육심리(A)와 교육철학(B) 중 한 과목은 반드시 수강해야 한다...