세그먼트 트리에서 [a,b] 범위에서 연속 구간 합의 최댓값을 구하는 방법을 알아봅시다.파이썬은 재귀 호출이 매우 느리기 때문에 쿼리 횟수가 많아지면 시간 내에 문제를 해결하기 어렵습니다. 따라서 본문에서는 연속 구간합의 최대 쿼리를 비재귀 방식으로 구현했습니다. 0. 사전 지식이 내용을 알아보기 전에 다음과 같은 사전 지식이 필요합니다.세그먼트 트리의 초기화세그먼트 트리의 쿼리비재귀 세그먼트 트리 1. 문제 상황일단 지금 풀고 있는 문제는 백준 10167번: 금광입니다. 2014 KOI 중등부 문제로 악명이 높습니다. 지금은 이게 웰노운이 되었다고 하는데 또 저만 모르는 웰노운인 거예요. 아무튼 이걸 해결하기 위해 공부하다보니 세그먼트 트리 스위핑 이외에도 알아야 할 테크닉이 있었습니다. 바로 구간 합..

세그먼트 트리는 구간의 정보를 빠르게 얻기 위한 자료구조입니다. 연속된 구간의 합이나 곱, xor 값 등을 처리하기에 좋습니다. 길이 N인 배열의 구간 정보를 얻기 위해서 선형탐색을 실시하면 O(N)으로 탐색이 가능합니다. 아주 느린 건 아니지만 전체 데이터가 좀 크다면 답이 안나옵니다. 그리고 쿼리의 실행 횟수가 많으면 많을수록, 트리의 업데이트가 잦을수록 이런 방법은 좋지 않습니다. 세그먼트 트리는 전체 배열을 이진트리로 분할하여 관리합니다. 양쪽 노드를 타고 가면서 구간의 좌, 우 경계 값과 맞닿은 노드들의 종합으로 원하는 결과를 O(logN)에 구할 수 있습니다. 다만 트리의 업데이트는 lazy propagation을 사용하지 않으면 여전히 O(N)의 시간이 소모됩니다. 우선 트리의 초기화, 쿼리..

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의 일부이기 때문입니..