청정알고리즘

문제

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]<<" ";
}

문제

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

풀이

만약 mod가 query개수 보다 많다면 항상 불가능하므로, -1을 출력한다.

mod가 query개수보다 작은 경우에는 0~mod-1까지의 index를 가지는 stack을 만들어보자.

그리고 숫자가 새로 들어올때 마다, 해당하는 나머지를 index로 가지는 stack에 현재 arr의 원소의 개수를 넣어준다.

3 query가 들어왔을 때, 각 나머지 별로 stack의 top에 있는 숫자의 min값이 우리가 찾는 index가 되고, 전체 사이즈에서 찾은 값을 빼주면 답이 된다.

이 방식으로 구하면 $O(q\times mod)$의 시간복잡도가 걸리지만 segment tree를 이용하면 $O(mod+q log mod)$의 시간복잡도로 원하는 답을 구할 수 있다.

Time Complexity : $O(mod+q log mod)$

코드

#include<iostream>
#include<vector>
#include<stack>
#define N 1000000
#define INF 1<<30
using namespace std;

stack<int, vector<int> > S;
stack<int, vector<int> > rem[N];

int seg[1<<21];
int p, q, mod;

void update(int t)
{
	t+=p;
	while(t!=1)
	{
		t>>=1;
		seg[t] = min(seg[t<<1], seg[t<<1|1]);
	}
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>q>>mod;
	for(p=mod;p^(-p&p);p+=(-p&p));

	if(mod>q)
	{
		while(q--)
		{
			int x;
			cin>>x;
			if(x==3) cout<<-1<<"\n";
			if(x==1) cin>>x;
		}
		return 0;
	}

	for(int i=p;i<p<<1;i++) seg[i]=i<p+mod?-1:INF;
	for(int i=p-1;i>0;i--) seg[i] = min(seg[i<<1],seg[i<<1|1]);
	while(q--)
	{
		int x;
		cin>>x;
		if(x==1)
		{
			cin>>x;
			int t=x%mod;
			S.push(t);
			rem[t].push(S.size());
			seg[p+t]=S.size();
			update(t);
		}
		else if(x==2)
		{
			if(S.empty())continue;
			int t = S.top();
			S.pop();
			rem[t].pop();
			seg[p+t]=rem[t].empty()?-1:rem[t].top();
			update(t);
		}
		else
		{
			if(seg[1]==-1) cout<<"-1\n";
			else cout<< S.size()-seg[1]+1<<"\n";
		}
	}
}

문제

https://codeforces.com/contest/1150/problem/E

풀이

우선 괄호열과 트리 간의 어떤 관계가 있는지를 관찰해보자.

s=(()(()))이라고 하면, 트리는 다음과 같이 그려진다.

트리를 주의깊게 살펴보면 depth가 늘어날때 여는 괄호이고, depth가 줄어들때 닫는 괄호이다.

즉, 여는 괄호가 나오면 새로 자식노드를 만들고, 닫는괄호가 나오면 퇴각하면 되는 것이다.

따라서, 지금까지의 괄호열의 prefix에서 (여는 괄호의 개수)-(닫는 괄호의 개수)가 tree에서의 depth가 되는 것이다.

여기서 구하고자 하는 tree의 지름은 두 노드 사이의 거리의 최대값이 된다.

두 노드 사이의 거리는 다음과 같이 표현할 수 있다.

$$d(u,v)=depth(u)+depth(v)-2depth(lca(u,v))$$

여기서 $lca(u,v)$는 두 노드의 lowest common ancestor이다.

괄호열이 트리를 순서대로 순회하고 있으므로, $lca(u,v)$는 u와 v사이의 depth값중 가장 작은 값을 가지는 점이 된다.

따라서 문제에서 구해야 할 것은 다음과 같다.

$$\max(depth(u)+depth(v)-2depth(k))(u \leq k \leq v)$$

이것을 단순히 계산하면 depth를 미리 계산해 놓는다 하여도,  쿼리마다 $O(n^3)$의 시간복잡도가 필요하다.

이를 쿼리마다 빠르게 계산하기 위해서, segment tree를 사용한다.

segment tree의 각 노드에서 관리하는 값을 하위 구간의 $diam=\max(depth(u)+depth(v)-2depth(k))(u \leq k \leq v)$라 하자.

그러면 다음과 같은 경우로 나눌 수 있다.

case 1) u,k,v가 전부 왼쪽 자식에 있을 경우

이 경우는 왼쪽 자식의 $diam$이 정답이 된다.

case 2) u,k는 왼쪽자식, v는 오른쪽 자식에 있을 경우

이 경우에는 왼쪽에서의 $\max(depth(u)-2depth(k))$ 와 오른쪽의 $\max(depth(v))$의 합이 답이 된다.

단, 여기서 주의해야 할것은, 현재 오른쪽 자식에 있는 $depth(v)$는 현재 왼쪽자식의 정보없이 구한 값이다.

따라서, $\max(depth(v))$에 현재의 depth를 더해주어야 한다.

case 3) u는 왼쪽자식, k,v는 오른쪽 자식에 있을 경우

이 경우는 왼쪽의 $\max(depth(u))$와 오른쪽의 $\max(depth(v)-2depth(k))$의 합이 답이 된다.

case 2와 비슷하게, 오른쪽 자식의 $depth(v)$는 현재 왼쪽자식의 정보없이 구한 값이다.

따라서 각각의 depth에 현재의 depth를 더해주어야 하므로, $\max(depth(v)-2depth(k))$에 현재 depth를 빼준다.

case 4) u,k,v 모두 오른쪽 자식에 있을 경우

이 경우 오른쪽 자식의 $diam$이 정답이 된다.

depth의 변동이 있지만 모두 더하면 0이므로 그냥 값을 그대로 사용한다.

이 4가지 case중 최대값이 구하고자 하는 $diam$의 값이 된다. 

여기서 추가적으로 $\max(depth(v)-2depth(k))$와 $\max(depth(u)-2depth(k))$도 구해야 함을 알 수 있다.

위의 방법과 똑같은 방법으로 각각을 구할 수 있다.

각각 3가지의 case가 나오고, 코드가 아래에 있으니 과정은 생략하겠다.

-가 붙은 부분의 최대값을 구할 때, 최소값으로 바꾸어야 함을 주의하자.

따라서 이 과정으로 segment tree를 이용하여 $diam$을 구하기 위해서 구간 $I$에 해당하는 노드에서

현재 depth

$\max(depth(v)) (v \in I)$

$\min(depth(v)) (v \in I)$

$\max(depth(v)-2depth(k)) (k \leq v \in I)$

$\max(depth(u)-2depth(k)) (u \leq k \in I)$

$\max(depth(u)-2depth(k)+depth(v)) (u \leq k \leq v \in I)>$

를 관리하면 되며, 쿼리가 들어올 때마다 leaf노드를 바꿔주고 부모노드로 올라가면서 update를 해주면 된다.

이 과정은 $O(log n)$만에 가능하다.

따라서 총 시간복잡도는 트리의 초기화 $O(n)$ 과 쿼리당 $O(log n)$으로 아래와 같다.

Time Complexity : $O(n+qlogn)$

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define lc(i) ((i)<<1)
#define rc(i) (((i)<<1)+1)
#define pa(i) ((i)>>1)
#define N 1<<19

using namespace std;

struct segnode
{
	int sum;
	int psummax; 
	int psummin;
	int leftmax;
	int rightmax;
	int diam;
} seg[N];

int n,q, p,l;
string s;
segnode merge(segnode x, segnode y)
{
	segnode ret;
	ret.sum = x.sum+y.sum;
	ret.psummax = max(x.psummax, x.sum+y.psummax);
	ret.psummin = min(x.psummin, x.sum+y.psummin);
	ret.leftmax = max( max(x.leftmax, y.leftmax-x.sum), x.psummax - (x.sum+y.psummin)*2);
	ret.rightmax = max( max(x.rightmax, y.rightmax-x.sum), x.sum+y.psummax - x.psummin*2);
	ret.diam = max( max(x.diam, y.diam), max(x.leftmax+x.sum+y.psummax, x.psummax+y.rightmax-x.sum));
	return ret;
}
segnode leaf(int x)
{
	segnode ret;
	ret.sum=x;
	ret.psummax= (x==1?1:0);
	ret.psummin= (x==1?0:-1);
	ret.leftmax= 1-x;
	ret.rightmax= 1;
	ret.diam =1;
	return ret;
}
void update(int x)
{
	seg[x+p] = (s[x]=='(')?leaf(1):leaf(-1);
	x+=p;
	while(x!=1)
	{
		x>>=1;
		seg[x] = merge(seg[lc(x)], seg[rc(x)]);
	}
}

void init()
{
	for(int i=0;i<l;i++) seg[i+p]= (s[i]=='(')?leaf(1):leaf(-1);
	for(int i=p-1;i>0;i--) seg[i]=merge( seg[lc(i)], seg[rc(i)]);
}
void printnode(int i)
{
	cout<<seg[i].sum<<" "<<seg[i].psummax<<" "<<seg[i].psummin<<" ";
	cout<<seg[i].leftmax<<" "<<seg[i].rightmax<<" "<<seg[i].diam<<" ";
	cout<<"\n";

}
int main()
{
	cin>>n>>q>>s;
	l=2*n-2;
	for(p=l;p^(-p&p);p+=(-p&p));
	
	init();
	cout<<seg[1].diam<<"\n";
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		--x,--y;
		swap(s[x],s[y]);
		update(x);
		update(y);
		cout<<seg[1].diam<<"\n";
	}
}

문제

https://codeforces.com/contest/1150/problem/D

풀이

3차원 dp를 이용하여 해결한다.

쿼리 형의 문제가 아니라 일반적인 DP라고 생각하고, 모든 문자가 미리 다 들어와있다고 가정하고 문제를 먼저 풀자.

$dp(i,j,k)$ = 1번, 2번 3번 religion description이 각각 i글자, j글자, k글자일 때, 필요한 Word of Universe의 최소길이

라고 정의하자. 

그러면 $dp(i,j,k)$는 $dp(i-1,j,k)$에서 한글자가 추가된 경우와, $dp(i,j-1,k)$에서 한글자가 추가된 경우, $dp(i,j,k-1)$에서 한글자가 추가된 경우. 이 세가지의 경우 중에서 가장 작은 경우의 답이 된다.

각 케이스는 서로 대칭이므로 첫 번째 케이스만 보자.

현재 $dp(i-1,j,k)$만큼의 Word of Universe를 사용하고 있다.

이 때 새로운 글자 c가 추가될 때 $dp(i,j,k)$는 Word of Universe 위에서 $dp(i-1,j,k)$ 이후에 나타나는 가장 가까운 c의 위치가 된다.

따라서 이를 빠르게 계산하기 위해서 $nx(i,j)$라는 배열을 만드는데 $nx(i,j)$는 Word of Universe 상에서 i+1~끝까지 배열에서 가장 가까운 알파벳 j의 위치이며, 이를 미리 만드는데에는 $O(n * |A|)$이면 충분하다. ($|A|$는 사용하는 알파벳의 개수) 

따라서, 이 nx를 이용해서 dp 관계식을 엄밀히 세워보면 다음과 같다.

$$dp(i,j,k)=\min(nx(dp(i-1,j,k), des_1(i-1)), nx(dp(i,j-1,k), des_2(j-1)), nx(dp(i,j,k-1), des_3(k-1)))$$

단, $des_i$는 i 종교의 description 목록이다.

이 점화식을 바탕으로 dp배열을 구현한다.

+ query가 들어올 경우 해당하는 글자를 하나 늘리고, 해당 글자가 늘어나서 값이 추가되는 부분만 새로 구해주면 된다. 이 부분의 개수는 쿼리 한 번에 $O(n^2)$이다.

- query가 들어올 경우 단순히 description 개수만 한개 빼주면 된다. 이미 채워져있는 테이블은 무시한다.

Time Complexity : $O(n|A|+qn^2)$

코드

#include <iostream>
#include <vector>
#include <string>

#define INF 1<<30
#define N 251
#define L 100010
#define A 26
using namespace std;

string wou;
int n,q;
int nx[L][A], p[A];
int dp[N][N][N], len[4], pre[4];
char des[4][L];

int main()
{
	cin>>n>>q>>wou;
	wou=" "+wou;
	for(int i=0;i<26;i++)
	{
		nx[n+1][i]=n+1;
		p[i]=n+1;
	}
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<26;j++) nx[i][j]=p[j];
		if(i) p[wou[i]-'a'] = i;
	}

	while(q--)
	{
		string type,c;
		int x;
		cin>>type>>x;

		for(int i=1;i<4;i++) pre[i]=0;
		if(type[0]=='-')
		{
			len[x]--;
			cout<< (dp[len[1]][len[2]][len[3]]<=n?"YES":"NO")<<"\n";
			continue;
		}
		cin>>c;
		pre[x] = len[x];
		des[x][len[x]++] = c[0];

		for(int i=pre[1];i<=len[1];i++) for(int j=pre[2];j<=len[2];j++) for(int k=pre[3];k<=len[3];k++)
		{
			if(i==0 && j==0 && k==0)continue;
			dp[i][j][k] = INF;
			if(i) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i-1][j][k] ][ des[1][i-1]-'a' ]);
			if(j) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i][j-1][k] ][ des[2][j-1]-'a' ]);
			if(k) dp[i][j][k]= min(dp[i][j][k], nx[ dp[i][j][k-1] ][ des[3][k-1]-'a' ]);	
		}
		cout<< (dp[len[1]][len[2]][len[3]]<=n?"YES":"NO")<<"\n";
	}
}

문제

https://codeforces.com/contest/1150/problem/C

풀이

2를 제외한 모든 소수는 홀수이다.

따라서, 주어진 순열을 2 1 2 2 2 ... 2 2 1 ... 1 1 1의 형태로 놓는다면, $\sum a_i$이하의 모든 소수를 포함하게 된다.

이것이 불가능한 경우는, 모두 1이거나 모두 2인 경우뿐이므로, 이 경우만 따로 출력한다.

Time Complexity : $O(n)$

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int n, onenum=0, twonum=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x==1) onenum++;
		else twonum++;
	}

	if(onenum==0)
	{
		for(int i=0;i<n;i++) cout<<"2 ";
	}
	else if(twonum==0)
	{
		for(int i=0;i<n;i++) cout<<"1 ";
	}
	else
	{
		cout<<"2 1 ";
		for(int i=0;i<twonum-1;i++) cout<<"2 ";
		for(int i=0;i<onenum-1;i++) cout<<"1 ";
	}
}

문제

https://codeforces.com/contest/1150/problem/B

풀이

왼쪽 위부터 순서대로 채운다. 이렇게 채워도 가능한 모든 경우를 다 볼수 있다는 것이 증명 가능하다.

저 첫 빈칸을 채우기 위해서는 저 첫 빈칸을 위쪽타일로 하는 십자타일을 놓는 경우 외에는 존재하지 않는다.

따라서, 이 타일을 전부 채울수 있는 경우가 있다면, 저 곳은 o로 포함된 타일 모양으로 채워야 하고, 이를 반복적으로 진행하여, 다 채울 수 있는지 확인한다.

Time Complexity : $O(n^2)$

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define N 52
using namespace std;

int n;
string mp[N];
bool f(int p,int q)
{
	if(p<0 || q<0 || p>=n || q>=n) return false;
	return mp[p][q]=='.';
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>mp[i];

	for(int i=0;i<n*n;i++)
	{
		if(mp[i/n][i%n]=='#')continue;
		int x=i/n, y=i%n;
		if( !f(x,y) || !f(x+1, y-1) || !f(x+1, y) || !f(x+1, y+1) || !f(x+2, y))
		{
			cout<<"NO";
			return 0;
		}
		mp[x][y]=mp[x+1][y-1]=mp[x+1][y]=mp[x+1][y+1]=mp[x+2][y]='#';
	}
	cout<<"YES";
}

문제

https://codeforces.com/contest/1150/problem/A

풀이

가장 저렴하게 구매해서, 가장 비싸게 파는 것이 유리하다.

$smin=\min(s_i)$와 $bmax=\max(b_i)$를 구하자.

가능한 만큼, $smin$원에 구매하고, $smax$원에 판매하면 된다.

Time Complexity : $O(n+m)$

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int main()
{
	int n,m,r,x;
	int smin=10000,bmax=0;

	cin>>n>>m>>r;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		if(smin>x)smin=x;
	}
	for(int i=0;i<m;i++)
	{
		cin>>x;
		if(bmax<x)bmax=x;
	}

	if(smin>=bmax) cout<<r;
	else cout<<(r/smin)*bmax+r%smin;
}

문제

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of kthen left-out nodes in the end should remain as it is.

풀이

list 문제의 연속이다.

전체 길이를 구한다음 k개씩 묶어서 각각을 뒤집는다. 뒤집는 과정은 다음과 같다.

Time Complexity : $O(n)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL || k==1)return head;
        ListNode* prev = new ListNode(0);
        prev->next = head;
        
        int l=0;
        for(ListNode* it = head; it!=NULL; it=it->next)l++;
        
        ListNode *p = prev;
        for(int i=0;i+k<=l;i+=k)
        {
            ListNode* now = p->next;
            ListNode* nxt = now->next;
            for(int j=1;j<k;j++)
            {
                now->next= nxt->next;
                nxt->next =p->next;
                p->next = nxt;
                nxt =now->next;
            }
            p=now;
        }
        return prev->next;
    }
};