henry's PS diary

https://www.acmicpc.net/problem/1761 트리에서의 두 정점 사이의 경로는 하나만 존재하므로 경로 사이의 거리가 곧 최단 거리가 된다. 이 점을 이용하여 루트에서 부터의 정점 i까지의 거리를 d[i]라 하면 두 정점 u,v 사이의 거리는 d[u]+d[v]에서 경로에 해당되지 않는 부분인 d[lca(u,v)]가 두 번 포함되었으므로 dist(u,v)=d[u]+d[v]-2*d[lca(u,v)] 이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include #include using namespace std..

https://www.acmicpc.net/problem/11437 트리에서 두 노드의 LCA (Lowest Common Ancestor), 즉 가장 가까운 공통 조상을 찾는 문제이다. Naive한 방법으로 O(N)만에 구할 수 있다. 모든 노드를 루트에서 시작하여 BFS (Breadth First Search)로 탐색하여 모든 노드의 부모와 깊이를 구한다. 그리고 LCA를 구하고자 하는 두 노드 중 더 깊은 노드를 올려서 두 노드의 깊이를 똑같이 맞춰준다. 그리고 하나씩 동시에 올리면서 처음 두 노드가 같아졌을 때 그 노드가 LCA이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051..

https://www.acmicpc.net/problem/1915 d[i][j] = (i,j)을 오른쪽 아래로 하는 가장 큰 정사각형의 한 변의 길이 123456789101112131415#include #include using namespace std; int i,j,n,m,d[1001][1001],ans; int main(){ scanf("%d %d",&n,&m); for(i=1;i

https://www.acmicpc.net/problem/4150 string의 + 연산을 연산자 오버로딩(Operator Overloading)하여 큰 수 연산을 구현하였다. 123456789101112131415161718192021222324252627282930313233#include #include #include using namespace std; string operator+(string &a,string &b){ string ret; int s1=a.size(),s2=b.size(),up=0; for(int i=s1-1,j=s2-1;(i>=0||j>=0);i--,j--) { int d; if(i>=0 && j>=0) d=a[i]-'0'+b[j]-'0'+up; else if(i>=0 && j

https://www.acmicpc.net/problem/3896 에라토스테네스의 체를 이용하여 소수를 구해주자. 123456789101112131415161718192021222324#include int t,k,p[1299710]; int main(){ p[0]=p[1]=true; for(int i=2;i*i

https://www.acmicpc.net/problem/1654 이분 탐색으로 정답의 범위를 줄여가면서 랜선의 최대 길이를 찾는다. 랜선의 개수가 모자라면 범위를 내리면서 개수를 늘려가고 랜선의 개수가 원하는 개수보다 같거나 크다면 범위를 최대한 올려가면서 랜선의 최대 길이를 찾는다. 이 때 mid가 정답이 되는 것이 아니라 매번 조건을 만족하는지 확인하면서 정답을 갱신해줘야 한다. 12345678910111213141516171819202122232425262728293031323334#include long long k,n,ans,lc[10000],max; void bs(){ long long left=1,right=max,mid; while(left

https://www.acmicpc.net/problem/5355 입력에 띄어쓰기가 있으므로 줄 전체를 받아야 한다. 123456789101112131415161718192021222324#include #include int main(){ int t,len; double n; char s[10]; scanf("%d",&t); while(t--) { scanf("%lf",&n); gets(s); len=strlen(s); for(int i=0;i

https://www.acmicpc.net/problem/2447 별찍기 11과 마찬가지로 재귀적으로 구현한다. 123456789101112131415161718192021222324252627282930#include int n;char s[7000][7000]; void go(int x,int y,int n){ if(n==3) { for(int i=x;i

https://www.acmicpc.net/problem/1913 소용돌이 모양으로 달팽이가 만들어 지게끔 적절히 구현한다. 1234567891011121314151617181920212223242526#include int i,j,k,n,m,x,y,X,Y,v=1,s[1000][1000]; int main(){ scanf("%d %d",&n,&m); x=y=X=Y=n/2+1; s[x][y]=1; for(k=0,j=2;k

https://www.acmicpc.net/problem/1021 덱(Double Ended Queue)을 이용한 구현 문제이다. 매 단계마다 왼쪽으로 밀면서 빼는것과 오른쪽으로 밀면서 빼는 것 중에 연산을 더 적게 쓰는 것을 사용한다. 구현할 때 index 범위와 사용에 주의하자. 헷갈리지 않게 index 시작을 0으로 다 맞춰주는 것도 한 방법이다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include using namespace std; int main(){ int n,m,t,cnt=0; scanf("%d %d",&n,&m); deque dq(n); for(int i=0;i