Network Flow 최대 유량 알고리즘은 어떤 경로가 있을 때, 시작점에서 도착점까지 흐를 수 있는 최대 유량을 구하는 알고리즘이다. BFS가 단순히 최단 경로를 찾는 알고리즘이었다고 하면, 최대 유량 알고리즘은 최단 경로가 아닌 최대 유량을 구해서 더 복잡하다. Network Flow의 기본 용어 다른 블로거 분들의 내용을 참고해서, 내가 이해하기 쉬운 방법으로 간단히 정리를 해봤다. Network Flow에서 기본적으로 사용하는 용어는 f / c이다. 여기서 f는 flow의 약자이며, A → B로 실제로 흐르는 유량을 의미한다. c는 capacity의 약자이며, A → B로 흐를 수 있는 최대 유량을 의미한다. 즉, c와 f는 항상 c>=f를 만족해야한다. 한 가지 더 알아야 할 개념은 A → B..
C++ 도형, 행렬 회전 코드 : 네이버 블로그 (naver.com) C++ 도형, 행렬 회전 코드 N *M 도형을 90도 회전하게 될 경우 M*N 의 배열이 생성된다 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0... blog.naver.com 도형을 실제로 그려보고 4방향으로 돌린 것에 대한 좌표를 가진다 now 도형과 next 도형의 i,j 관계가 어떠한지 살펴보면 된다. 이 때, i,j는 당연하게도 회전될 도형의 column의 값에 영향을 받는다. def rotate_clock(n,m, graph) : temp = [[0 for _ in range(n)] for _ in range(m)] for i in range(m) : for j in range(n) : temp[i]..
1. 투 포인터는 정렬된 상태가 기본이 되어야 한다. 그렇지 않을 경우, 앞뒤의 상관관계가 전혀 없기 때문에 특정 쿼리 후 인덱스 변경에서 논리성이 없어진다. 2. 투 포인터는 같은 지점에서 시작하는 것이 있고, 양끝에서 시작하는 것이 있다. 상황에 맞게 써야하는데, 아직까지는 내가 구분이 정확히 안된다. 구분이 되면 업데이트 할 것. 3. 투 포인터는 인덱스를 옮길 때, 논리적으로 헛점이 없다는 것이 확인되고 난 다음에 쓰는게 맞다. 9007 카누선수 중간에서 만나기로 배열을 2개로 만들어준다. 배열을 2개로 만들어 준 다음에 각각 정렬을 하고, 두 포인터로 접근해서 센다. 이 방법은 이분탐색보다 더 빠르게 동작한다. 7453 합이 0인 네 정수 이 문제는 완전탐색으로 풀 경우 4000^4이 되어서 말..
이분탐색은 기본적으로 탐색의 범위가 굉장히 넓을 때는 반드시 떠올려야 한다. 또한, 특정 구간의 최대, 최소값을 구하라고 할 때도 파라메트릭 서치 개념으로 접근이 가능하기 때문에 반드시 떠올려야 한다. 이분탐색은 반드시 정렬이 필요하기 때문에 리스트라면 정렬은 무조건 해야한다. 이분탐색을 사용할 때 각 파라메터의 의미는 다음과 같다. L < R vs L
중간에서 만나기 알고리즘 1. 전체 샘플을 절반으로 쪼개서 샘플 자체를 줄이는 방법 1208 → 2^N → 2^(n/2) * 2^(n/2) 2. 샘플은 그대로 두지만, 문제 풀이를 절반으로 쪼개서 시간을 줄이는 방법 2295 → N^4 → 2*N^2 * LogN