청정알고리즘

#define MAX 30000
#define QSIZE 10
using namespace std;

class Status
{
private:
	int num[4], ind, mod[4][4], high;
	int f(int x)
	{
		return 81*81*81*num[x] + 81*81*num[(x+1)&3] + 81*num[(x+2)&3] + num[(x+3)&3];
	}
public:
	Status(){}
	Status(int m[4][4])
	{	
		high = -1;
		for(int i=0;i<4;i++) for(int j=0;j<4;j++)
		{
			mod[i][j]=m[i][j];
			if(mod[i][j]>high) high=mod[i][j];
		}
		num[0] = 27*m[0][0]+9*m[0][1]+3*m[1][0]+m[1][1];
		num[1] = 27*m[0][3]+9*m[1][3]+3*m[0][2]+m[1][2];
		num[2] = 27*m[3][3]+9*m[3][2]+3*m[2][3]+m[2][2];
		num[3] = 27*m[3][0]+9*m[2][0]+3*m[3][1]+m[2][1];
		
		ind=0;
		for(int i=1;i<4;i++)
		{
			int find = f(ind), fi = f(i);
			if(find>fi) ind=i;
		}
	}
	int get(int x){ return num[(ind+x)&3]; }
	bool operator==(Status& x)
	{
		for(int i=0;i<4;i++)
		{
			if(get(i)!=x.get(i)) return false;
		}
		return true;
	}
	bool operator<(Status& x)
	{
		for(int i=0;i<4;i++)
		{
			if(get(i)!=x.get(i)) return get(i)<x.get(i);
		}
		return false;
	}

	int getHigh(){return high;}
	Status flipComplement()
	{
		int t[4][4];
		for(int i=0;i<4;i++) for(int j=0;j<4;j++) t[i][j] = high - mod[i][3-j];
		return Status(t);
	}
};
struct Block
{
	Status st;
	int base;
	Block(){}
	Block(int _d[4][4], int _b)
	{
		st = Status(_d);
		base = _b;
	}
	bool operator<(Block& x)
	{
		if(st==x.st)return base>x.base;
		return st<x.st;
	}
};
class Queue{
private:
	int data[QSIZE];
	int f,b,s;
public:
	Queue()
	{
		f=b=s=0;
	}
	void push(int x)
	{
		data[b]=x;
		++b;
		++s;
		if(b==QSIZE) b=0;
	}	
	void pop()
	{
		++f;
		--s;
		if(f==QSIZE) f=0;
	}
	int front(){return data[f];}
	int size(){return s;}
};

class Data
{
public:
	Status status;
	Queue q;
	Data(){}
	Data(Status& _st)
	{
		status=_st;
		q=Queue();
	}
};
void swap(Block& x,Block& y)
{
	Block t=x;
	x=y;
	y=t;
}

void quickSort(int l,int r, Block* b)
{
	if(l+1>=r)return;
	
	int pivot = l;
	int j=pivot;
	
	for(int i=l+1;i<r;i++)
	{
		if(!(b[i]<b[pivot])) continue;
		j++;
		swap(b[i], b[j]);
	}

	swap(b[l], b[j]);

	pivot=j;
	quickSort(l, pivot, b);
	quickSort(pivot+1,r, b);
}

int binary_search(int l, int r, Status& v, Data* d)
{
	while(l<r)
	{
		int mid = (l+r)>>1;
		if(d[mid].status==v)return mid;
		
		if(d[mid].status<v) l=mid+1;
		else r=mid;
	}
	return -1;
}

Block b[MAX];
Data d[MAX];

int normalize(int module[4][4])
{
    int base=module[0][0];
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(base>module[i][j])
                base = module[i][j];
    
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            module[i][j] -= base;
    
    return base;
}

int makeBlock(int module[][4][4]) {
	for(int i=0;i<MAX;i++)
	{
		int base = normalize(module[i]);
		b[i] = Block(module[i], base);
	}
	quickSort(0, MAX, b);

	int dnum=0;
	for(int i=0;i<MAX;i++)
	{
		d[dnum]=Data(b[i].st);
		d[dnum].q.push(b[i].base);
		while(b[i].st == b[i+1].st)
		{
			d[dnum].q.push(b[i+1].base);
			++i;
		}
		++dnum;
	}

	int ans=0;
	for(int i=0;i<dnum;i++)
	{	
		if(d[i].q.size()==0)continue;
		Status target = d[i].status.flipComplement();
		int ind = binary_search(0, dnum, target, d);
		if(ind==-1) continue;

		if(i==ind)
		{
			while(d[i].q.size()>1)
			{
				ans += d[i].q.front();
				d[i].q.pop();
				ans += d[i].q.front();
				d[i].q.pop();
				ans += d[i].status.getHigh();
			}
			continue;
		}
		while(d[i].q.size()>0 && d[ind].q.size()>0)
		{
			ans += d[i].q.front() + d[ind].q.front() + d[i].status.getHigh();
			d[i].q.pop();
			d[ind].q.pop();
		}
	}
	return ans;
}

문제

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

풀이

전형적인 Convex Hull 문제이다.

아래 풀이에서는 Graham Scan이라고 하는 $O(nlogn)$의 알고리즘을 사용한다.

Convex Hull을 구한 후, Convex Hull 상에서 가장 먼 두 점을 찾는데, 원래는 Rotating Calipers 라는 알고리즘을 사용하여 $O(n)$에 구해야 한다.

하지만 필자는 한 번도 구현해본 적이 없고, 실제 이 문제에서는 좌표의 범위가 작고, 정수점만 입력으로 들어오기때문에 Convex Hull의 점의 수가 매우 작고, 실제로 1000*4=4000개보다 작음은 약간의 논증을 통해 보일 수 있다.

따라서 Convex Hull 내부의 모든 점을 비교해도 시간안에 구할 수 있다.

정해는 rotating calipers라는 알고리즘을 이용해서 가장 먼 두 점을 구하는데 $O(|convex hull|)$이면 충분하다.

Time Complexity : $O(nlogn + |convex hull|^2)$

코드

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 100002
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pos;
 
double dist(pos p1, pos p2)
{
	double dissq = (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second);
	return sqrt(dissq);
}

int n;

vector<pos> p;

ll ccw(pos p1, pos p2, pos p3)
{
	return (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
}

bool cmp(pos p1, pos p2)
{
	ll c = ccw(p[0], p1, p2);
	if (c > 0) return 1;
	if (c < 0) return 0;
	else
    {
		if (dist(p[0], p1) < dist(p[0], p2)) return 1;
		else return 0;
	}
}

int main()
{
	cin>>n;

	p.resize(n);
	for (int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
	
	sort(p.begin(),p.end());
	sort(p.begin()+1,p.end(),cmp);
    
	vector<pos> cvxh;
	cvxh.push_back(p[0]);
	cvxh.push_back(p[1]);

	for (int i=2;i<n;i++)
	{
		while (cvxh.size() >= 2 && ccw(cvxh[cvxh.size()-2],cvxh.back(),p[i])<=0)
			cvxh.pop_back();
		cvxh.push_back(p[i]);
	}
    
	double ans=-1;
	int len=cvxh.size();
	for (int i=0;i<len;i++) for (int j=i+1;j<len;j++)
		ans=max(ans, dist(cvxh[i], cvxh[j]));

    printf("%.10f", ans);
}

문제

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

풀이

$x,y$가 input으로 들어올때, $f(x)=$(1부터 $x$까지 적었을 때, 나타나는 0~9의 숫자의 배열)이라고 정의하자.

그럼 구하고자 하는 정답은 $f(y)-f(x-1)$이 된다.

그럼 $f(x)$는 어떻게 구할까?

자릿수별로 각 숫자의 개수를 계산한다는 아이디어를 기본적으로 생각해보자.

즉, 1의 개수를 셀때, 1의 자리에 오는 1, 10의 자리에 오는 1, 100의 자리에 오는 1,....들을 모두 세서 더해준다면 구하고자하는 전체 1의 개수를 구할 수 있을 것이다.

결국 위의 질문은 1~x까지의 숫자중 $10^t$자리가 $a$인 숫자가 모두 몇개인지를 각 $t$에 대해 모두 풀어서 더해주면 된다.

이는 다음과 같이 경우를 나누어 풀수 있다.

case 1) $a$가 $x$의 $10^t$자리 숫자보다 작을 경우

예를 들어서 $x=12345, a=1, 10^t=100$인 경우를 보자.

그러면 ??1?? 꼴의 숫자가 몇 개인지를 세는 것인데, 이는 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류) * 100이 된다.

또한 (찾는 자리수보다 높은 자리에 올수 있는 숫자들의 종류)는 위의 예시에서는 0부터 12까지이므로, 총 13개가 가능하다.

즉 1??, 11??, 21??, 31??, ... , 121??의 경우가 가능하다는 뜻이다.

수식으로 나타내면 $(x/10^{t+1}+1)\times 10^t$가지 경우임을 알 수 있다.

case 2) $a$가 $x$의 $10^t$자리 숫자와 같을 경우

$x=12345, a=3, 10^t=100$을 예로 들어보자.

이 경우에는 3??, 13??, ..., 113??까지는 자유롭게 가능하고, 123??의 경우에는 0~45까지 총 46개만 가능하다.

같은 방식으로 수식으로 나타내면 $(x/10^{t+1})\times 10^t+(x%10^t)+1$ 가지 경우가 있음을 알 수 있다.

case 3) $a$가 $x$의 $10^t$자리 숫자보다 클 경우

비슷한 방식으로  $x=12345, a=5, 10^t=100$을 예로 들어보자.

이 경우에는 5??, 15??, ..., 115??까지만 가능하므로 case 1)의 경우보자 $10^t$개 적게 된다.

따라서 이 경우는 $(x/10^{t+1})\times 10^t$ 가지이다.

따라서 이를 모두 각각 더해주면 된다.

주의할 점은 맨 앞자리에 0이 올수는 없으므로 0은 각 경우에서 $10^t$개만큼 빼주어야 한다는 점이다.

즉 10?? 꼴의 숫자는 있지만, 0?? 꼴의 숫자는 존재하지 않으므로, 이 경우를 빼주는 것이다.

위와 같은 방식으로 0~9까지 등장수를 모두 더해주면 $f(x)$를 구할 수 있다.

Time Complexity : $O(logx+logy)$

코드

#include<iostream>
#include<vector>
using namespace std;

vector<int> f(int t)
{
	vector<int> ret(10);
	for(int i=1;i<=t;i*=10)
	{
		for(int j=0;j<10;j++)
		{
			if( j<(t/i)%10) ret[j] += (t/(i*10)+1)*i;
			else if( j==(t/i)%10 ) ret[j] += (t/(i*10))*i+(t%i)+1;
			else ret[j] += (t/(i*10))*i;
		}
		ret[0]-=i;
	}
	return ret;
}
int main() {
	while(1)
	{
		int x,y;
		cin>>x>>y;
		if(x==0 && y==0)break;
		vector<int> a1 = f(y);
		vector<int> a2 = f(x-1);
		for(int i=0;i<10;i++)
		{
			cout<<a1[i]-a2[i]<<" ";
		}
		cout<<"\n";
	}
}

문제

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

풀이

단순히 생각하면 30000 * 30000 배열을 만들어 사각형이 입력으로 들어오면 해당 사각형의 영역에 1씩 더해준다.

그 후, 1이상의 값을 가지는 모든 칸의 값을 세주면 된다.

하지만 이와 같은 방법으로는 시간도 많이 소모하고, 공간도 많이 잡는다.

따라서 line sweeping 알고리즘을 사용하여 현재 line과 닿아있는 부분의 30000개 배열만 생각한다.

세로 선을 왼쪽 끝부터 오른쪽 끝까지 sweeping한다고 생각하자.

sweeping하면서 만나는 면적을 모두 더하면 구하고자 하는 정답이 된다.

sweeping 하면서 발생하는 event의 종류가 두 가지인데, 각각에 대해서 처리해 주면 된다.

case 1) 새로운 사각형의 등장

이 때는 현재 직사각형의 왼쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 증가시켜준다.

case 2) 사각형의 퇴장

이 때는 현재 직사각형의 오른쪽변에 처음 닿게 된다.

이 때, 이 변에 해당하는 y좌표를 가진 부분에 1씩 감소시켜준다.

위와 같은 과정을 거치면서 현재 line에 있던 1이상의 칸의 수를 모두 더해주면 된다.

하지만 이렇게 되면 $O(nC)$의 시간복잡도로 시간안에 통과할 수 없다.

따라서 전체 구간의 합을 segment tree를 이용하여 관리해주면 된다.

이 때, 등장하는 쿼리는 구간에 1을 더해주는 query이므로, lazy propagation의 아이디어를 사용한다.

lazy propagation처럼 게으르게 값을 관리하는데, 현재 구간이 전파될 예정이라면, 하위 노드의 값과 관계 없이 이 구간은 모두 값을 구하는데 사용되게 된다.

root 노드로 부터 내려가다가 처음으로 전파될 예정인 노드를 만나면 바로 그 하위 구간의 길이를 return해주면 되기 때문에, 전파과정은 진행하지 않아도 무방하다.

이러한 방법을 이용하여 segment tree를 업데이트 해주면, event마다 log 시간복잡도에 원하는 작업을 완료할 수 있다.

Time Complexity : $O(N(logN+logC))$

코드

#include<iostream>
#include<algorithm>
#define N 10005
#define C 40000
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

struct ev
{
	int x, y1, y2, z;
	bool operator<(const ev & t)
	{
		return x<t.x;
	}
}evt[N<<1];

ev make_ev(int X, int Y1, int Y2, int Z)
{
	ev r;
	r.x=X;
	r.y1=Y1;
	r.y2=Y2;
	r.z=Z;
	return r;
}
struct segtree
{
	int val;
	int num;
} seg[C<<2];

int n,pr,ans;

void update(int l, int r, int v, int t, int x, int y)
{
	if(y<l || r<x) return;
	if(l<=x && y<=r) seg[t].num+=v;
	else
	{
		int mid=(x+y)>>1;
		update(l,r,v,lc(t),x,mid);
		update(l,r,v,rc(t),mid+1,y);
	}
	if(seg[t].num) seg[t].val=y-x+1;
	else seg[t].val=(x==y?0:seg[lc(t)].val+seg[rc(t)].val);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;

		evt[i]=make_ev(a,b,d-1,1);
		evt[i+n]=make_ev(c,b,d-1,-1);
	}
	sort(evt,evt+2*n);
	for(int i=0;i<2*n;i++)
	{
		if(i>0) ans+=(evt[i].x-pr)*seg[1].val;
		update(evt[i].y1, evt[i].y2, evt[i].z,1,0,C);
		pr=evt[i].x;
	}
	cout<<ans;
}

문제

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

풀이

우선 flood fill을 이용하여 각 섬별로 넘버링을 한다.

같은 방법으로 0,0 구석의 물에서부터도 flood fill을 이용하여 안전한 바다를 전부 구할것이다.

flood fill을 할때, 4방향, 즉 상하좌우의 경우 인접한 바다를 모두 queue에 추가한다.

또한 추가적으로 대각선방향 4방향에서도 안전한 바다로 전파될 수 있는 바다들이 존재한다.

만약

#.

.#

모양처럼 대각선으로만 뚫려있고 상하로 막혀있지만, 왼쪽의 섬과 오른쪽의 섬이 서로 다른 섬이라면 사냥꾼은 두 섬에 동시에 존재할 수 없으므로, 둘 중 사냥꾼이 없는 쪽으로 빠져나올 수 있다.

따라서 대각선으로만 뚫려있어도 위의 조건에 해당한다면 queue에 추가해준다.

이 과정을 진행하면서 안전한 바다와 인접한 땅들을 모두 체크해주어 'O'로 바꾸고, 나머지를 'X'로 바꾸면 문제를 해결할 수 있다.

Time Complexity : $O(nm)$

코드

#include<iostream>
#include<string>
#include<queue>
#define N 2004

using namespace std;
typedef pair<int,int> pi;
string s[N];
int mp[N][N],n,m,color;
pi flag[4]={pi(1,0),pi(0,1),pi(-1,0),pi(0,-1)};
vector<char> ans;

pi operator+(const pi &x1, const pi &x2)
{
	return make_pair(x1.first+x2.first, x1.second+x2.second);
}

bool cango(pi t)
{
	return t.first>=0 && t.first<n && t.second>=0 && t.second<m;
}

void floodFillLand(pi st, int v)
{
	mp[st.first][st.second]=v;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			vector<int> V;

			if(!cango(next) || mp[next.first][next.second]!=0) continue;

			if(s[next.first][next.second]=='#')
			{
				mp[next.first][next.second] = v;
				Q.push(next);
			}
		}
	}
}

void floodFillWater(pi st)
{
	mp[st.first][st.second]=-1;
	queue<pi> Q;
	Q.push(st);
	while(!Q.empty())
	{
		pi f = Q.front();
		Q.pop();
		for(int k=0;k<4;k++)
		{
			pi next = f+flag[k];
			if(!cango(next)) continue;
			if(mp[next.first][next.second]>0)
			{
				ans[mp[next.first][next.second]]='O';
				continue;
			}

			if(mp[next.first][next.second]==0 && s[next.first][next.second]=='.')
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}

		for(int k=0;k<4;k++)
		{
			pi next= f+flag[k]+flag[(k+1)&3];
			pi c1 = f+flag[k];
			pi c2 = f+flag[(k+1)&3];
			if(!cango(next) || s[next.first][next.second]=='#') continue;

			if(mp[next.first][next.second]!=-1 && mp[c1.first][c1.second]>0
				&& mp[c2.first][c2.second]>0 && mp[c1.first][c1.second]!=mp[c2.first][c2.second])
			{
				mp[next.first][next.second] = -1;
				Q.push(next);
			}
		}
	}
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i];

	color=0;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(mp[i][j] || s[i][j]=='.') continue;
		floodFillLand(make_pair(i,j),++color);
	}

	ans.resize(color+1,'X');
	floodFillWater(make_pair(0,0));

	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		if(s[i][j]=='.')continue;
		s[i][j] = ans[mp[i][j]];
	}

	for(int i=0;i<n;i++) cout<<s[i]<<"\n";
}

문제

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

풀이

한 줄을 입력 받아서 공백 뒤의 문자가 맨 앞 문자와 전부 같은지 체크한다.

Time Complexity : $O(|S|)$

코드

#include<iostream>
#include<string>
using namespace std;

int main() {
	while (1) {
		string s;
		int c=1;
		char x;
		getline(cin, s,'\n');
		if (s[0] == '*') break;

		for(int i=0;i<s.length();i++) if(s[i]>='A' && s[i]<='Z') s[i]=s[i]-'A'+'a';
		x=s[0]>='a'?s[0]-'a'+'A':s[0];
		for(int i=1;c!=0 && i<s.length();i++)
		{
			if(s[i-1]==' ')
			{
				if(s[i]==s[0]) continue;
				c=0;
			}
		}
		cout<<(c?"Y\n":"N\n");
	}
}

문제

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

풀이

Dynamic Programming과 DFS spanning tree에 대한 지식 모두를 요하는 문제라 어려울 수 있다.

우선 주어진 입력으로 주어지는 방향그래프가 어떤 모양일지 생각해보자.

주어진 그래프는 $n$개의 vertex와 $n$개의 edge로 이루어져 있다.

따라서 connected component 끼리 나눠도 각각의 component에 존재하는 vertex와 edge의 개수는 같다.

따라서 이 1개의 component에 대해서만 확인해 보자.

한 component는 $k$개의 vertex와 edge로 이루어져있는데, 이는 즉 DFS spanning tree를 만들면 남는 edge가 1개가 생기고 이 edge를 제거하면 전체 그래프는 tree가 된다는 것이다.

즉, 한개의 component는 중심이 되는 cycle이 하나가 존재하고, 이 cycle에 여러개의 tree가 달라붙어 있는 모양을 가지게 된다. 다음은 component의 예시이다.

전체 component를 색칠하는 경우의 수는 (사이클을 색칠하는 경우의 수) * (트리 부분을 색칠하는 경우의 수)이다.

따라서, 이 각각을 구한다면 원하는 경우의 수를 구할 수 있다.

우선 사이클 부분의 경우의 수를 구해보자.

$dp(n,k)=$($n$개의 칸에 $k$가지 색으로 칠할 때, 이웃한 색깔을 다르게 칠하면서, 첫번째 칸과 $n$번째 칸을 다르게 칠하는 경우의 수)

이 $dp$에 대한 점화식을 구하기 위해서 다음과 같이 경우를 나눠보자.

case 1) 1번 노드의 색깔과 $n-1$번 노드의 색깔이 다를 경우

이 경우는 1번부터 $n-1$번 까지 칠하는 경우의 수가 $dp(n-1,k)$와 일대일 대응이 된다.

$n$번 칸에는 1번과 $n-1$번과 다른 색깔로 칠해야 하므로 $k-2$개의 색깔중 하나를 골라서 칠할 수 있다.

따라서 이 경우의 수는 $(k-2) \times dp(n-1,k)$이다.

case 2) 1번 노드의 색깔과 $n-1$번 노드의 색깔이 같을 경우

이 경우는 1번과 $n-1$번을 겹쳐서 cycle을 만든다고 생각하면, 1번부터 $n-1$번 까지 칠하는 경우의 수가 $dp(n-2,k)$와 일대일 대응이 된다.

$n$번 칸에는 1번과 $n-1$번과 다른 색깔로 칠해야 하는데, 두 색깔이 같으므로 $k-1$개의 색깔중 하나를 골라서 칠할 수 있다.

따라서 이 경우의 수는 $(k-1) \times dp(n-2,k)$이다.

종합해보면 $dp(n,k)=(k-2) \times dp(n-1,k) + (k-1) \times dp(n-2,k)$이다.

여기서 초기값을 잘 생각해보아야 하는데, $n \geq 2$일 때에는 $dp$값과 구하고자 하는 사이클의 색칠 값이 같지만, $n=1$일 때에는 사이클의 색칠하는 경우의 수는 $k$이지만 $dp$값은 0이어야 한다.

따라서 $dp(1,k)=0, dp(2,k)=k^2-k$로 dp테이블을 먼저 채워준 후, $dp(1,k)=k$로 정의해야 한다.

다음은 트리 부분의 경우의 수를 구해보자.

이 부분은 어렵지 않은데, 각 노드들은 유일한 부모노드가 존재하며, 위에서부터 부모의 색깔과 다르게 칠하기만 해면 재귀적으로 칠할 수 있으므로, 각 칸마다 $k-1$가지의 색깔로 칠할 수 있다.

요약하자면 주어진 input에 $t$개의 component가 있고 각각의 component를 구성하는 cycle의 크기를 $c_i$라고 하면, 총 경우의 수는 다음과 같은 식으로 표현이 가능하다.

$$\prod_{i=1}^t dp(c_i,k) \times (k-1)^{(n-\sum_{i=1}^t c_i)}$$

cycle의 탐색은 DFS탐색을 하면서 visitTime을 관리하면 쉽게 할 수 있다.

출발한 노드의 visitTime과 도착한 노드의 visitTime을 비교했을 때, 출발한 노드의 visitTime이 더 크다면, 지금 도착한 노드는 이미 계산이 끝난 노드이므로 무시하고, 도착한 노드의 visitTime이 더 크다면 현재시간과 도착한 노드의 시간의 차이가 cycle의 크기가 된다.

따라서 시간복잡도는 $dp$ 테이블을 채우는데 $O(n)$, DFS를 하면서 cycle 부분의 색칠 수를 곱하는데에 $O(n)$ 나머지 트리 부분의 색칠 수를 곱하는데에 $O(n)$(이 부분은 $O(logn)$에도 가능하지만 bottleneck이 아니므로 무시)으로, 총 시간복잡도는 $O(n)$이다.

Time Complexity : $O(n)$

코드

#include<iostream>
#include<algorithm>
#define N 1000004
#define MOD 1000000007

using namespace std;

int n,k;
int a[N],t[N];
typedef long long ll;
ll dp[N];
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];

	dp[0]=k;
	for(int i=2;i<=n;i++) dp[i] = (dp[i-1]*(k-2)+dp[i-2]*(k-1))%MOD;
	dp[1]=k;
    
	int c=1,cnt=0;
	ll ans=1;

	for(int i=1;i<=n;i++)
	{
		if(t[i]!=0)continue;
		int j=i;
		for(;t[j]==0; j=a[j]) t[j]=c++;
		if(t[j]>=t[i])
		{
			int x = c-t[j];
			ans = (ans*dp[x])%MOD;
			cnt += x;
		}
	}
	for(int i=n-cnt;i>0;i--) ans = (ans * (k-1))%MOD;
	cout<<ans;
}

문제

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

풀이

shift 연산과 더하기 빼기를 이용하여 나누기를 해본다.

우선 절댓값을 취해서 부호부분을 제외한 나머지 부분만 계산할 것인데, 이때 INT_MIN의 경우 절대값을 하면 넘어가므로, INT_MIN에 대한 처리를 진행한다.

지금 답을 출력할 수 있는 것은 출력하고, 아니라면 divisor를 한번 더해줘서 미리 한번의 덧셈을 진행해놓는다.

이제 $x/y$를 계산하는데 $b$라는 변수를 초기값 1로 따로 관리를 한다.

기본적인 알고리즘은 다음과 같다.

case 1) $x\leq y*b$

x에서 y*b를 빼내고, $ans$에 b를 더해준다. 그 후, b에 2를 곱한다.

이 때, y*b가 INT_MAX보다 커지려고 하면 곱하지 않는다.

case 2) else

이때, x가 처음의 divisor보다 작아졌을 경우, 다 나눴으므로 반복문을 종료한다.

아니라면, b에 2를 나눈다.

이 과정을 반복하면, $O(log n)$의 시간복잡도로 나누기를 할 수 있다. 

Time Complexity : $O(log n)$

코드

class Solution {
public:
    int divide(int dividend, int divisor) {
        int ans=0;
        if(divisor==INT_MIN) return dividend==INT_MIN?1:0;
        if(dividend==INT_MIN)
        {
            if(divisor==-1) return INT_MAX;
            if(divisor==1) return INT_MIN;
            ans++;
            dividend+=abs(divisor);
        }
            
        int x=abs(dividend);
        int y=abs(divisor);
        bool sgn = (dividend<0)^(divisor<0);
        int b=1;
        while(x>0)
        {
            if(x>=y)
            {
                x-=y;
                ans+=b;
                if(y>>30) continue;
                b<<=1;
                y<<=1;
            }
            else
            {
                if(divisor>x) break;
                b>>=1;
                y>>=1;
            }
        }
        return sgn?-ans:ans;
    }
};

문제

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

풀이

문자열 내에 특정 문자열이 있는지 찾는 알고리즘으로 kmp 알고리즘이 유명하다.

이를 이용한다. 

Time Complexity : $O(n+m)$

코드

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hl = haystack.length();
        int nl = needle.length();
        if(nl==0) return 0;
        
        vector<int> fail;
        fail.resize(nl,0);
        int j=0;
        for(int i = 1; i< nl ; i++)
        {
            while(j > 0 && needle[i] != needle[j]) j = fail[j-1];
            if(needle[i] == needle[j]) fail[i] = ++j;
        }
        j=0;
        for(int i=0;i<hl;i++)
        {
            while(j>0 && haystack[i] != needle[j]) j = fail[j-1];
            if(haystack[i] == needle[j])
            {
                if(j==nl-1) return i-nl+1;
                else j++;
            }
        }
        
        return -1;
    }
};

문제

Given an array nums and a value val, remove all instances of that value in-place 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.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

풀이

two pointer를 이용하여 문제를 푼다.

선행 포인터가 val이랑 다를 경우 후행 포인터의 칸에 순차적으로 채워준다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0;
        for(int j=0;j<nums.size();j++)
            if(nums[j]!=val)nums[i++]=nums[j];
        return i;
    }
};