ps(알고리즘) (32) 썸네일형 리스트형 LCA 2 제목에서부터 나와있듯 그냥 LCA 알고리즘을 구현하라는 문제이다.정점에서부터 하나씩 부모 노드로 거슬러 올라가게 되면 시간이 너무 많이 걸리기 때문에2의 거듭제곱 단위로 끊어서 거슬러 올라가는 방식이다. 이렇게 하면 logN의 시간이 걸려서 훨씬 빠르다. 우선 두 정점의 깊이를 맞춰주고, 동시에 거슬러 올라가면 된다.parent 배열이 중요한데 parent[i][j]가 뜻하는건 i번 정점의 2^j 번째 부모 노드이다.void set_par_depth(int par,int n,int dep){ depth[n]=dep; parent[n][0]=par; for(int i=0;i우선 depth배열을 채우고 parent[i][0]을 채우는 함수이다.단순한 dfs 함수이다.set_par_depth(.. 행성 터널 MST에서 사용하는 kruskal알고리즘을 쓰면 풀리는 문제이다.kruskal에 대해 간단하게 설명하자면, 간선들을 가중치 순으로 오름차순 정렬하고앞에서부터 간선을 보고 둘이 이어져 있지 않다면 잇고 이미 이어져 있으면 잇지 않는 시행을 반복해서이은 간선이 N-1개가 되면 멈추는 알고리즘이다.이어져 있는지 아닌지는 union-find로 판단한다.매우 간단한 알고리즘인데 이 문제에서는 한가지 더 생각을 해야 한다.간선이 N^2개이기 때문에 모두 넣을 수가 없다.따라서 x,y,z 각각을 오름차순 정렬을 한 다음에 이웃한 것끼리의 간선만 저장하는 식으로 하면 3(N-1)개의 간선을 가지고 kruskal 알고리즘을 돌리면 된다.#include#include#includeusing namespace std;pai.. 최솟값 찾기 구간의 최솟값을 N번 찾는데 구간이 한칸씩 오른쪽으로 이동하는 형태이다.그냥 세그트리를 쓰면 NlogN이 걸려서 될지 안될지 확실하지 않다.deque라는 자료구조를 써서 풀 수 있다.deque는 앞에도 뒤에도 push와 pop을 할 수 있는 자료구조이다.deque의 front를 구간의 최솟값으로 놓을 것이다.새로운 수가 들어오면 우선 현재 최솟값인 deque의 front의 인덱스가 i-L+1보다 큰지 판단하고 아니면 pop_front를 해준다.그리고 새로 들어온 수를 deque의 back에서부터 비교하면서 새로 들어온 수보다 큰 값들을 전부 pop_back으로 없애준다.이렇게 해도 되는 이유는 새로 들어온 수가 구간의 가장 오른쪽에 있는 수이기 때문에 구간이 한칸씩 오른쪽으로 이동할 때 계속 쓰일텐데 이.. 가장 긴 증가하는 부분 수열 5 이전에 풀었던 가장 긴 증가하는 부분수열 문제랑 거의 같은데 그 수열을 출력해야 하기 때문에 조금 더 추가해야 할 부분들이 있다.일단 전에 풀었던 코드에서 그냥 lis 배열을 출력시키면 이상한 값들이 나온다.예를 들어 10 20 40 50 30 이 있을 때 lis배열이 10 20 40 50에서 10 20 30 50 으로 바뀌는데 이는 실제 증가하는 부분 수열이 되지 못하기 때문이다. 길이만 구할 수 있는 알고리즘이었기 때문에 lis배열을 그대로 출력하면 안된다.그래서 ind라는 배열을 추가해서 ind[i]를 i번째 값이 lis배열에 추가된 인덱스로 정의한다.예를 들어 10 20 40 30에서 ind[1]=1,ind[2]=2,ind[3]=3,ind[4]=3이 된다.이렇게 하고 ind배열을 뒤에서부터 보면.. 히스토그램에서 가장 큰 직사각형 앞에서 본 히스토그램과 같은 문제이다.이전에는 스택으로 풀었으니 이번에는 세그먼트 트리로 풀어볼 것이다.구현은 좀 더 복잡하지만 개인적으로 직관적인 이해는 세그트리 방식이 더 쉬웠던거 같다.간단하게 그냥 구간에서 높이가 최소인 곳을 찾고 그 점을 기준으로 왼쪽, 오른쪽에서 넓이가 최대인 직사각형과을 비교하면 된다.구간의 왼쪽에서의 최대넓이, 구간의 오른쪽에서의 최대넓이, 기준점의 높이*구간의 길이 이렇게 3개의 값을 비교해서 최대를 찾으면 끝난다.#include#includeusing namespace std;long long arr[100004];int N;long long big = 1000000005;struct Data{ long long ind,val; bool operatorfe) .. 히스토그램 직사각형들의 높이가 주어졌을 때 가장 큰 넓이의 직사각형을 구하면 된다.두가지 풀이가 있는데 이번에는 스택을 이용해서 풀고 다음에 다른 풀이로 풀어보겠다. 스택을 이용해서 앞에서부터 높이를 하나씩 볼 때 새로 들어온 높이 값이 이전 높이보다 크면 스택에 높이를 넣어준다.이전 높이보다 작으면 이전의 더 큰 높이들은 앞으로의 직사각형에 영향을 미치지 않기 때문에 지금 새로 들어온 높이보다 작아질 때까지 스택에서 pop을 해주면서 직사각형의 넓이들을 구한다.#include#includeusing namespace std;int N;long long ans=0;long long arr[3000004];stack st;int main(){ scanf("%d",&N); st.push(0); for(.. 제곱 ㄴㄴ수 에라토스테네스의 체 원리를 이용한 간단한 문제이다.그냥 min부터 max까지 돌면서 sqrt(max)보다 작은 값들의 제곱수로 나눠 떨어지는 수들을 하나씩 제외하면 된다.이미 제외한 수들을 중복해서 제거하지 않기 위해 check 배열을 만드는데 이 배열로 체크할 때 인덱스를 min으로 빼야 배열 크기를 줄일 수 있다. (안 빼면 인덱스가 최대 max까지 늘어나야 해서 불가능)#include#include#includeusing namespace std;long long minv, maxv;int check[1000004];int main(){ scanf("%lld %lld",&minv,&maxv); int arrange = int(sqrt(maxv)); long long ans = max.. 외판원 순회 모든 가능한 경로를 탐색하면 최대 16!의 시간이 걸려서 시간초과가 뜰 것이다.더 효율적으로 처리하기 위해서 dp를 쓸 것이다.현재까지 방문한 노드의 상태를 2진법 16자리수로 비트마스킹을 하고, 현재 방문한 점을 이용해서dp[state][current] 이런식으로 쓸 것이다.만약 이 dp값이 존재하며 그 이후는 탐색이 필요하지 않기 때문에 시간을 줄일 수 있다.탐색은 dfs로 돌리면 된다.#include#include#includeusing namespace std;int N;int w[100][100];int dp[100000][100];int big = 100000000;int dfs(int state, int curr){ //printf("%d %d\n",state,curr); if(d.. 이전 1 2 3 4 다음
