생각하는 아이들

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

캘리퍼스란? 캘리퍼스는 작은 물건의 지름,너비 등을 측정할 때 쓰는 도구로 두개의 평형한 변 사이의 길이를 측정하는 도구이다. 회전하는 캘리퍼스(Rotating Calipers) 알고리즘이란? 회전하는 캘리퍼스 알고리즘은 실제 볼록 다각형의 지름을 재는데 사용된다. 다각형을 따라 두 직선을 한바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구하는 알고리즘이다. 백준 10254번 고속도로 문제를 기준으로 살펴 보자 https://www.acmicpc.net/problem/10254 10254번: 고속도로 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 www...

Persistent 의 의미는 보존 된다는 의미인데 이 알고리즘의 핵심은 서로 다른 세그먼트 끼리 값을 보존 하며 공유하는 것이 핵심입니다. 예제 문제로 다음의 문제를 예로 들어 봅시다. https://www.acmicpc.net/problem/11012 11012번: Egg You are a president deeply loved by many folks in your country. Every time you go on a parade (which is your main job, what else should a president do), the folks would throw eggs at you — because you love eggs! The folks passionately send the..

Dynamic Segment Tree 는 다음과 같은 경우에 사용됩니다. 0으로 초기화 된 10억개의 수열이 있을 때 Q개의 질의에 대해 실시간으로 업데이트와 그에 대한 답을 구하는 경우 일반적인 세그먼트 트리로는 10억개의 공간을 모두 할당 할 수 없기 때문에 불가능 합니다. 하지만 이때 잘 생각해 보면 1번의 쿼리에 변경되는 노드의 갯수는 log2(10억) =(약)21의 갯수만 변경 되는 것을 알 수 있습니다. 따라서 최대 21 * Q 개의 공간만 있으면 가능하겠다는 아이디어에서 Dynamic Segment Tree 는 출발 합니다. 즉 다음과 같은 트리에서 2번 위치의 값이 변경이 된다면 노드의 갯수를 3개만 만들어 놓겠다는 것이 Dynamic Segment Tree 입니다. 이렇게 만드는 것은 링..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

Meet in the middle Meet in the middle 은 브루트포스 알고리즘을 사용해야 하지만 경우의 수가 브루트포스 알고리즘을 사용하기에 조금 클 때 사용 된다. 즉 브루트포스 알고리즘을 사용하되 이를 분할 해서 연산의 수를 최소화 하는 것이다. 예를 들면 N크기 배열 원소의 모든 조합을 고려해야 하는 문제가 있다고 하자. 이때 N이 20이라면 2^20(약 100만)개의 연산을 하면 된다. 하지만 만약 N이 40이라면 2^40 개의 연산을 수행하므로 초당 연산 수 1억번 이내에서 해결이 어렵다. 이때 MITM 알고리즘을 사용하게 되는데~ MITM 은 분할 정복과 비슷한 형태를 취하지만 분할정복은 작은 문제 해결을 통해 커다란 하나의 문제를 해결하는 반면~ MITM은 작은 문제 해결 + 알..