컴공생 일상 블로그 컴공생 일상 블로그

문제https://www.acmicpc.net/problem/24024 풀이X개 이하의 스푼을 사용했을 때, 최소 비용의 최대 값을 구해야 함조금 생각해보면, X 스푼을 사용했을 때가 최소 비용의 최대 값임을 알 수 있다.정확한 그래프 개형은 몰라도, 특정 값에서 최대가 되는 그래프를 그리기 때문에, 빨간색 면에 대해 n 스푼, 파란색 면에 대해 X-n 스푼으로 삼분 탐색을 돌려주면 된다. 코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M, X;struct Input { int n; long long cost; int color;};struct Node {..

문제https://www.acmicpc.net/problem/13310 풀이캘리퍼스 + 삼분 탐색각 시간마다 찍힌 별들 중 최대 거리에 대해 최소값을 찾는 문제f(x)에 대한 삼분 탐색이지만 f(x)가 캘리퍼스 구현 ㅇㅇ..., distance 반환값을 int로 해놓고 발견못해서 고통받았다. + 계속 틀리길래 혹시해서 탐색 구현을 아래처럼 변경했더니 pass됨, 왜 그런지는 좀 생각해봐야 할듯// 틀림if (sim(lm) sim(rm)) { left = lm;}else { right = rm;}  코드#include #include #include #include #include #include #include using namespace std;struct Input { long long x, y, ..

삼분 탐색어떤 unimodal한 그래프에서, 최대/최소 값을 O(logN)에 찾는 알고리즘  unimodal은 단조 증가와 단조 감소로 이분되는 그래프로 아래 그림과 같다.이런 값들의 나열에 대해서 삼분 탐색을 가능하고, 만약 같은 값이 연속되는 평평한 구간이 존재하는 경우 사용 불가능하다.   삼분 탐색 알고리즘 과정1. unimodal한 구간에 대해 삼분 탐색을 수행2. 구간을 3개로 나누어서 탐색, [O, A], [A, B], [B, N]3. f(A)가 f(B)보다 크다면, [O, A]에는 최솟값이 존재할 수 없으므로, 구간을 [A, N]으로 축소4. 2 ~ 3 과정을 반복5. 남은 구간3개의 후보 값에 대해 완전 탐색 이분 탐색과 과정은 비슷한데, 3개의 구간에 대해 탐색 영역을 줄여나가면서 진행..

개요한동안 바빠서 새 알고리즘을 공부할 틈이 없었는데, 연휴 기념 오랫만에 들고온 기하 알고리즘 ~아래 내용은 CCW와 Convex Hull에 대한 이해를 바탕으로 한다.CCW: https://doraeul19.tistory.com/297Convex Hull: https://doraeul19.tistory.com/343   회전하는 캘리퍼스(Rotating Calipers)캘리퍼스는 아래와 같이 길이를 측정하는 도구로, 회전하는 캘리퍼스 알고리즘은 볼록 다각형을 돌면서 두 지점간의 거리를 구하는 알고리즘이다.   지지선과 대척점지지선(A line of support): 볼록 다각형에 대해 점이나 변에 접한 직선  대척점(Anti podal points): 평행한 두 지지선이 있을 때, 그 지지선에 닿아있..

문제https://www.acmicpc.net/problem/3679 풀이오랫만에 보는 Convex hull...? 비슷한 문제원래는 스택에 하나씩 push/pop하면서 Convex hull을 구해줘야하는데, 이는 모든 점을 사용해서 다각형을 만들어 주기만 하면 된다. 시작점0을 기준으로 반시계 기준으로 정렬하고 점을 차례로 이으면 좌측(N=5)그림과 같이 다각형을 그릴 수 있다.하지만 우측(N=7)그림과 같이 마지막 점들이 직선을 이루고 있는 경우 역순으로 이어줘야한다.이경우만 잘 고려해서 cross(0, N - 1, index)가 0일 경우부터는 역순으로 이어주면된다. 코드#include #include #include #include #include #include using namespace st..

문제https://www.acmicpc.net/problem/12752 풀이특별한 알고리즘은 없고, 단순 다익스트라 문제이다.많은 도시들이 있고 그 중 K(K   1. K = 1도로가 필요 없음  2. K = 2두 개의 도시를 연결하는 최소 비용을 구하면 된다. 간단하게 다익스트라 1번으로 구할 수 있다.  3. K = 3아래와 같은 경우들이 있을 수 있다. 각 점에서 출발해서 어떤 점에서 만난다고 생각하면 쉽다. K개의 도시(0, 1, 2 정점) N개의 정점에서 만나는 경우 중 비용 합의 최소 값을 구한다.A정점에서 만나는 경우: cost[0][A] + cost[1][A] + cost[2][A]B정점에서 만나는 경우: cost[0][B] + cost[1][B] + cost[2][B]...  4. K =..

문제https://www.acmicpc.net/problem/5670 풀이Trie: https://doraeul19.tistory.com/415전형적인 트라이 문제, 근데 입출력 형식이 여러개의 TC이므로 while(cin >> N)으로 입력받자Insert함수를 구현해서 트리를 잘 만들어주고, Find함수에서 자판을 눌러야하는 횟수를 더해가면 된다. 자판을 눌러야 하는 경우1. 맨 처음 글자: 첫 번째 글자는 무조건 눌러야 한다.2. 다른 문자열과 구분되지 않는 경우    - 현재 문자가 isEnd(다른 문자열의 끝인 경우)    - 다음 문자로 올 수 있는 경우가 2개 이상인 경우 코드#include #include #include #include #include #include #include #in..

어떤 문자열이 어떤 문자열들의 집합에 속하는지 알아내기 위해 단순히 모두 비교할 경우O(문자열의 길이 x 문자열의 개수) 의 시간 복잡도를 가진다. 이 때 문자열을 효율적으로 저장하고 탐색하는 자료 구조가 Trie이다. 대충 O(N) 그냥 그림을 보면 이해가 쉽다. 아래와 같이 4개의 단어가 있다고 해보자. Trie 자료 구조에 각 단어를 담아보면 아래와 같다.    트라이 자료구조는 주어진 문자열에 대해 앞 문자부터 하나씩 노드를 생성하면서 만들어진다. Insert1. 문자열에서 현재 문자를 확인2. 현재 문자로 이루어진 노드가 존재한다면 → 그 노드를 탐색존재하지 않는다면 → 새 노드를 생성 Find1. 문자열에서 현재 문자를 확인2. 자식 노드가 현재 문자인 노드가 있는지 확인, 없다면 return..