알고리즘

안녕하세요. 오늘은 2-SAT알고리즘을 배워볼 거예요. SAT문제 sat문제는 충족 가능성 문제입니다. (satisfiability problem) 충족 가능성 문제는 여러 boolean 변수들이 있는 식이 있을 때 그 식을 참(true)으로 만드는 boolean값들 (true, false)이 있는지 구하는 문제입니다. 이런게 sat문제입니다. 아래로...

안녕하세요. 오늘은 회전하는 캘리퍼스를 배워볼 거예요. 뭐 할때 씀? 가장 먼 두 점 사이의 거리를 구할 때 씁니다. 어떻게 씀? 가장 먼 두점 사이의 거리는 볼록 껍질 위 두 점 A, B가 있을 때 A -> nextA 와 B -> nextB 간선이 최대한 평행이 되도록 만드는 A와 B입니다. 만약 A -> nextA 와 B -> nextB 가 반시계...

안녕하세요. 오늘은 삼분탐색을 할 거예요. 삼분탐색이란? 삼분탐색은 볼록함수, 즉 증가하다가 감소하는 함수 또는 감소하다가 증가하는 함수에서 최대/최소를 찾을 때 씁니다. 알고리즘만 설명하자면 범위 [left,right]가 주어진다. 범위를 삼등분해서 [left,llr],[llr,lrr],[lrr,right]로 나눈다. 최솟값을 구하려면 f(llr)f(...

안녕하세요. 오늘은 HLD를 배울거예요. HLD란? HLD는 이름 그대로 무거운거랑 가벼운거를 나누는 것입니다. 이런 쿼리가 있을 때 많이 쓰죠. 트리에서 특정 간선(혹은 정점)의 가중치 바꾸기 특정 경로에서 가중치를 더하거나 곱하거나 xor하거나 최대최소 찾기 이게 사실 선형이면 세그트리로 너무쉽게 해결되는 문제입니다. 하지만 여기는 트리 속이므로 ...