청정알고리즘

문제

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

풀이

unique 함수를 이용하여 계산한다.

직접 구현하려면 two pointer를 이용해서 구해보자. 어렵지 않다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return unique(nums.begin(), nums.end())-nums.begin();
    }
};

문제

https://www.acmicpc.net/problem/1734

풀이

DFS를 탐색하면서 각 노드 별로 다음 정보를 저장한다.

• sTime : 노드를 처음 만났을 때의 시간
• eTime : 자식 노드의 탐색을 모두 끝내고 노드를 빠져나올 때의 시간
• low : 해당 노드에서 DFS를 진행했을 때, 등장하는 노드들의 sTime의 최솟값
• depth : DFS spanning tree에서의 depth
• par : DFS spanning tree에서의 부모 노드
• adj : 인접리스트, 현재 노드와 연결된 노드의 정보
• child : DFS spanning tree에서의 자식 노드들

이제 쿼리를 분석해보자.

1) 1번 쿼리, $a,b,g_1,g_2$가 입력으로 들어온다.

만약 $g_1,g_2$가 DFS spanning tree의 tree edge가 아니라면, $a,b$는 DFS spanning tree로 연결된다.

일반성을 잃지 않고 $g_1$이 $g_2$의 parent라고 하자.

이 때, $g_1, g_2$ edge가 단절선이 아니면, 즉 $g_2$에서 $g_2$위로 가는 bypass가 있으면 그 bypass로 연결이 가능하다.

만약 $g_1, g_2$가 단절선이라면, $a,b$가 단절선을 기준으로 같은 쪽에 있는지를 확인하고, 같은 쪽에 있으면 단절 후에도 연결이 가능하다.

위의 경우가 모두 불가능하다면, $a,b$ 사이의 경로는 단절선을 통하는 경로 뿐이고 단절선을 끊으면 이동할 수 없다.

각각의 체크는 모두 $O(1)$만에 가능하다.

2) 2번 쿼리, $a,b,c$가 입력으로 들어온다.

만약 $a,b$가 둘 모두 DFS spanning tree 상에서 $c$의 자손이 아니라면, tree의 정의에 의해 c를 통하지 않는 $a$와 $b$사이의 경로가 존재한다.

만약 둘 모두 $c$의 자손이라면, $c$의 자식들 중에서 $a$와 $b$를 각각 포함하는 자식이 존재할 것이다.

이를 $ac, bc$라고 하자. ($a=ac, b=bc$일 수도 있다.)

만약 $ac=bc$라면 $c$가 $ac, bc$의 lca(lowest common ancestor)가 아니라는 뜻이므로, c가 없어져도 a와 b사이의 경로가 존재한다.

만약 위의 경우가 아니라면 $a,b$중 $c$의 자손인 노드는 $c$를 우회해서 갈수 있는지 체크하고, 자손이 아닌 노드끼리는 단절의 전후 상관없이 항상 연결이 가능하므로 자손인 노드만 $c$보다 빠른 점으로 가는 bypass가 있는지 확인해주면 된다.

각각의 처리는 대부분 $O(1)$에 가능하지만, $ac,bc$를 찾기 위해서 $c$의 child 목록에서 binary search를 통해 해당하는 child를 찾아야하므로 $O(log(\text{# child of c}))$만큼의 시간복잡도가 필요하고, 이는 최대 $O(logn)$ 만큼 필요하다.

Time Complexity : $O(n+q_1+q_2logn)$

코드

#include<iostream>
#include<vector>

using namespace std;

struct data
{
	int sTime;
	int eTime;
	int low;
	int depth;
	int par;
	vector<int> adj;
	vector<int> child;
};
vector<data> info;

int n,e,q;
int visitTime = 1;
void dfs(int now)
{
	data& d=info[now];
	d.sTime = d.low = visitTime++;
	for(vector<int>::iterator it=d.adj.begin();it!=d.adj.end();++it)
	{
		int nxt = *it;
		data& x = info[nxt];
		if(x.depth!=-1)
		{
			if(d.par!=nxt) d.low = min(d.low, x.sTime);
			continue;
		}
		x.depth = d.depth+1;
		x.par = now;
		d.child.push_back(nxt);
		dfs(nxt);
		d.low = min(d.low, x.low);
	}
	d.eTime = visitTime++;
}

bool isAncestor(int x1, int x2)
{
	return info[x1].sTime<=info[x2].sTime && info[x2].eTime <=info[x1].eTime;
}
bool bypass(int x1,int x2)
{
	return info[x1].low<info[x2].sTime;
}

int findChild(int x1, int x2)
{
	int l=0,r=info[x1].child.size()-1;
	while(l!=r)
	{
		int mid = (l+r)>>1;
		int now = info[x1].child[mid];
		if(info[x2].sTime > info[now].eTime) l=mid+1;
		else if(info[x2].eTime < info[now].sTime) r = mid-1;
		else return now;
	}
	return info[x1].child[l];
}
void yes()
{
	cout<<"yes\n";
}
void no()
{
	cout<<"no\n";
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>n>>e;

	data init={0,0,0,-1,0,vector<int>(),vector<int>()};
	info.resize(n+1,init);
	while(e--)
	{
		int x,y;
		cin>>x>>y;
		info[x].adj.push_back(y);
		info[y].adj.push_back(x);
	}
	
	info[1].par = -1;
	info[1].depth = 1;

	dfs(1);

	cin>>q;
	while(q--)
	{
		int x,a,b;
		cin>>x>>a>>b;
		if(x==1)
		{
			int g1,g2;
			cin>>g1>>g2;
			if(isAncestor(g2,g1)) swap(g1,g2);

			if(info[g1].depth != info[g2].depth-1) yes();
			else if(bypass(g2,g2)) yes();
			else if(isAncestor(g2,a)==isAncestor(g2,b)) yes();
			else no();
		}
		else
		{
			int c;
			cin>>c;
			if(!isAncestor(c,a) && !isAncestor(c,b)) yes();
			else if(isAncestor(c,a) && isAncestor(c,b))
			{
				int ac = findChild(c,a);
				int bc = findChild(c,b);
				if(ac==bc)yes();
				else if(bypass(ac,c)&&bypass(bc,c)) yes();
				else no();
			}
			else
			{
				if(!isAncestor(c,a)) swap(a,b);
				int ac = findChild(c,a);
				if(bypass(ac,c)) yes();
				else no();
			}
		}
	}
}

문제

https://www.acmicpc.net/problem/1849

풀이

세그먼트 트리를 1로 모두 채운 다음, 숫자의 입력을 쿼리라고 생각하자.

i번째 쿼리로 x가 들어왔을 경우, 현재 prefix sum이 x+1인 점중 가장 작은 점을 찾아서 그 칸을 채우면 된다. 

예를 들어서 $n=8$인 경우 첫번째 쿼리로 5가 들어온 경우 현재 세그먼트 트리는 다음과 같이 구성된다.

그 후 다음과 같이 segment tree를 업데이트 해준다.

이 때, 저 prefix sum이 5가 되는 부분을 찾아야 하는데, 이는 거꾸로 segment tree의 꼭대기 부터 내려오면서 찾을 수 있다.

만약 left child의 sum이 v보다 작거나 같다면 원하는 index는 오른쪽 자식에 있으며, left child의 sum이 v보다 크다면 원하는 index는 왼쪽 자식에 있다.

이러한 방법으로 leaf node까지 도착하면, 도착한 노드에 원하는 숫자를 추가해주면 된다.

이 방법으로 쿼리마다, node를 찾는데 $O(log n)$, 세그먼트 트리를 업데이트 해주는데 $O(log n)$이 걸린다.

따라서 총 시간복잡도는 $O(n+qlogn)$이다.

Time Complexity : $O(n+qlogn)$

코드

#include<iostream>
#include<vector>
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

int seg[1<<18];
int n,p;
vector<int> ans;
void update(int t)
{
	t+=p;
	while(t!=1)
	{
		t>>=1;
		seg[t] = seg[lc(t)]+seg[rc(t)];
	}
}
int loc(int t)
{
	int r=1;
	while(r<p)
	{
		if(t>=seg[lc(r)])
		{
			t-=seg[lc(r)];
			r=rc(r);
		}
		else r=lc(r);
	}
	return r-p;
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>n;

	ans.resize(n);
	for(p=n;p^(-p&p);p+=(-p&p));
	for(int i=p;i<p+n;i++) seg[i]=1;
	for(int i=p-1;i>0;i--) seg[i]= seg[i<<1]+seg[i<<1|1];

	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		int l=loc(x);
		seg[p+l]=0;
		ans[l]=i;
		update(l);
	}
	for(int i=0;i<n;i++) cout<<ans[i]<<" ";
}