-
20210502~20210508 BOJ 연습
1. BOJ4641 Doubles 리스트에서 각 숫자의 순서가 아닌 개수만이 중요하므로, 리스트를 순회하여 개수를 기록하고, 모든 숫자를 set에 삽입한다. set을 순회하면서 $cnt[x]\times !!cnt[2\times x]$를 모두 합하면 끝. 2. BOJ18004 From A to B 얼핏 우박수와도 비슷해보이지만, 결정적인 차이점은 숫자가 줄어들거나 늘어나려면 한 가지 선택지밖에 없다는 것이다. A>B라면 A가 짝수인지를 고려해서 A:=A/2를 가능한 한 시행하고, A<=B라면 A+=1을 B-A번 시행하여 두 수를 같게 만들 수 있다. 3. BOJ20500 Ezreal 여눈부터 가네 ㅈㅈ 상당히 당황스러운 디스크립션의 문제지만(…), 아무튼 어렵지...
-
[BOJ1987] 알파벳
BOJ1987 방문했던 알파벳을 다시 방문하면 안 되므로 backtracking을 하면서 이를 저장해줘야 하는데, 비트마스킹을 사용하면 깔끔하게 처리할 수 있다. 굳이 사용하지는 않아도 되나, 비트마스킹 기초 연습으로 풀기에 좋은 문제인 듯 하다. #include<bits/stdc++.h> using namespace std; #define ORD(x) (x-'A') const int dx[] = { 0, 0,-1, 1}; const int dy[] = {-1, 1, 0, 0}; int R,C; string arr[20]; int vpos(int x,int y){ return x>=0&&x<R&&y>=0&&y<C; } int mx=0; void f(int x,int y,int vis){ mx = max(mx,__builtin_popcount(vis)); for(int...
-
[BOJ] 이진 탐색 트리
BOJ2957 이진 탐색 트리 이진 탐색 트리를 그냥 구현하면 당연히 TLE를 받습니다. 플래티넘 5에 이렇게 단순한 구현을 시킬 일은 없습니다. 이진 탐색 트리를 만들었다고 가정하고, 이를 아래로 눌러 일렬로 만들어봅시다. 이 그림에서 잘 살펴보다 보면, 각 노드의 부모는 일렬로 만든 상태에서 각 노드에 인접해있고, 인접한 노드 중 깊이가 깊은 노드임을 알 수 있습니다. 따라서 배열을 항상 정렬된 상태로 유지하고 노드를 삽입할 때 인접한 칸의 깊이를 빠르게 알 수 있다면, 문제를 해결할 수 있는 것입니다. 문제는,...
-
[BOJ] 소가 길을 건너간 이유 9
BOJ14463 소가 길을 건너간 이유 9 다음과 같은 관찰만 할 수 있다면 아이디어는 간단합니다. A<B를 만족하는 네 정수 A, B, C, D와 A, B를 잇는 선분 X와 C, D를 잇는 선분 Y에 대해 다음과 같은 명제가 성립합니다. Lemma 1. X와 Y가 교차함은 A<C<B<D와 동치이다. 이 두 명제는, 몇가지 케이스를 나눠 살펴봄으로써 관찰할 수 있습니다. Lemma 1에 의해 같은 소가 지나는 점을 잇는 선분을 번호가 작은 점을 기준으로 정렬한다면, 어떤 선분 K에 대해 K와 교차하며 K보다...
-
[BOJ] 등산
BOJ1486 등산 그래프의 간선 가중치에 대해 조금만 생각해보면 핵심적인 아이디어를 떠올릴 수 있습니다. 간선의 존재여부 및 그 가중치를 인접행렬이나 인접리스트로 저장하는 대신, 인접한 두 위치와 그 높이를 갖고 간선 존재여부 및 가중치를 O(1)에 계산할 수 있습니다. 이 격자 그래프에서 노드의 개수는 최대 625개이고, 간선의 수도 이에 선형비례하므로 다익스트라 알고리즘을 사용해 준다면 시작점에서 모든 노드로 가는 최단시간을 파악할 수 있습니다. 한 가지 문제점은 우리가 고려할 경로는 가는 경로뿐만 아니라 오는 경로도 있다는 것이지만, 이는 간선 가중치를...
-
20210709 BOJ 연습
서론 그냥 심심해서 몇 문제 풀었는데 좀 괜찮은 문제 얻어간거 같아서 괜찮은 하루였던 듯. 1. BOJ1043 거짓말 만약 두 파티에 공통된 인원이 있다면, 그 두 파티에서 거짓말을 할 수 있는지는 서로 동일하다. 따라서 두 파티 중 하나에라도 속하는 인원들은 두 파티짜리의 한 덩어리(=독립집합) 인원으로 볼 수 있고, 이 점에서 Union-Find를 쓰면 각각의 독립집합을 형성할 수 있다. 약간의 Union-Find 기술을 쓸 수 있는데, 각 독립집합이 하나의 음 아닌 정수로 표현할 수 있는 특정을 갖는다면 -1배하여 독립집합의...
-
[BOJ] 왕들의 외나무다리 돌게임
BOJ18937 왕들의 외나무다리 돌게임 어제 종료된 Semi-Game Cup의 제일 첫 문제입니다. 열심히 노느라 참가를 하지는 못했지만, 문제가 공개된 후에 풀어보니 A번인 이 문제만큼은 난이도가 평이하고 재밌더군요. 문제에서 제시된 게임은 각 플레이어가 다음과 같은 행동을 취할 수 있는 님게임과 일치합니다. 돌을 임의의 개수만큼 가져온다. 해당 무더기에서 가져온 돌 중 일부를 다시 쌓는다. 이 때, 먼저 모든 무더기의 돌의 개수를 xor한 값이 0이 되게 한 플레이어는 상대방이 돌을 쌓던 돌을 가져가던 다시금 돌의 개수를 xor한 값이 0이...
-
LCS 정복하기 4
BOJ18438 LCS 5 이전에 풀이를 작성한 LCS 1/2/3에 비해 갑자기 난이도가 수직 상승한 문제입니다. (LCS 4는 특수한 케이스니 제외합니다. LCS 4의 풀이는 나중에 다른 글에서 소개하도록 하겠습니다.) 최대 길이 7000의 문자열 두 개의 LCS를 TL 1s, ML 7MB에 구해야합니다. TL은 그럭저럭 평범한 것 같은데, ML이 심상치 않다. 이 ML이 난이도를 D2까지 올려놓은 원인인 셈이죠. LCS 2 문제에서 한 대로 공간복잡도 $O(NM)$에 역추적하려고 하면 최대한 크기가 작은 short형을 사용하더라도 MLE는 피할 수 없습니다. 만약 길이만을 구하는...
-
LCS 정복하기 3
BOJ1958 LCS 3 단순히 생각해서 LCS(A,B,C) = LCS(LCS(A,B),C)라고 생각할 수 있으나 두 문자열의 LCS가 하나가 아닐 수 있다는 점에서 무수히 많은 반례를 만들 수 있습니다. 2166번과 같은 근본적인 접근으로 다음과 같은 점화식을 세울 수 있습니다. DP [i] [j] [k] = DP [i-1] [j-1] [k-1] + 1 when A [i] == B [j] and B[j] == C[k] DP [i] [j] [k] = max(DP [i-1] [j] [k], DP [i] [j-1] [k], DP [i] [j] [k-1]) otherwise 점화식만...
-
LCS 정복하기 2
BOJ9252 LCS 2 NM lcs backtracking 문제입니다. 2166번에서 구한 대로 dp table을 작성한 후 점화식의 특징을 이용하여 backtrack할 수 있습니다. 길이 a,b인 문자열 A,B에 대해 (a,b)에서 시작해 (0,t) 또는 (t,0) 꼴의 좌표에 도달할 때까지 다음의 세 행동 중 하나를 취하며 추적하여 LCS로 가능한 문자열을 추출할 수 있습니다. (x,y)=>(x-1,y) when dp [x] [y] == dp [x-1] [y] (x,y)=>(x,y-1) when dp [x] [y] == dp [x] [y-1] (x,y)=>(x-1,y-1) when a [x] == b [y] dp 점화식에 의해...
-
LCS 정복하기 1
BOJ9251 LCS LCS 정복하기, 그 첫 번째. 가장 기초적인 $O(NM)$ dp로 LCS 길이 구하기입니다. LCS란 Longest Common Subsequence의 약자로, 두 수열의 공통된 부분수열을 의미합니다. 이때 부분수열은 연속하지 않아도 됩니다. 예를 들어 IHATEPIZZA와 ILOVEPIZZA의 LCS는 길이 7인 IEPIZZA라고 할 수 있겠죠. 같은 두 문자열이라고 해도, LCS는 여러 개일 수도 있습니다. IEATCHICKEN과 IAETCHICKEN이 그 예시인데요, 길이 7의 IECHICKEN과 IACHICKEN 모두 LCS임을 알 수 있습니다. 그렇다면 LCS의 길이는 어떻게 구할까요? DP로 생각해봅시다. DP [i] [j] = (A[1..i]와 B[1..j]의...
-
[BOJ] 다각형의 면적
BOJ2166 다각형의 면적 꼭짓점 중 하나를 기준점으로 잡고, 모든 연속한 점쌍에 대해 외적을 구한 후 합하면 됩니다. 외적의 총합이 음수일 수도 있기 때문에 절댓값을 반드시 취해줘야합니다. #include<bits/stdc++.h> using namespace std; using ll=long long; using dot=pair<ll,ll>; dot operator-(dot a,dot b){ return {a.first-b.first,a.second-b.second}; } ll ccw(dot a,dot b,dot c){ dot x=b-a,y=c-a; return x.first*y.second-x.second*y.first; } int main(void){ ios::sync_with_stdio(0);cin.tie(0); int n; cin>>n; vector<dot> v(n); dot f; ll sum=0; for(int i=0;i<n;i++){ cin>>v[i].first>>v[i].second; if(i){ sum+=ccw(f,v[i-1],v[i]); } else{ f=v[i]; } } sum=abs(sum);...
-
[BOJ] 복도 뚫기
BOJ9373 복도 뚫기 센서와 벽을 노드 취급하고, 간선은 두 노드 사이에 들어갈 수 있는 원의 최대 지름으로 합시다. $O(N^2)$번의 연산이 요구되므로 N<=1,000인 이 문제에서는 무리없이 해결 가능합니다. 이 때, 경로가 존재하지 않을 때까지 두 노드 사이를 차단한다고 생각해봅시다. 경로가 하나라도 존재할 때 차단되지 않은 간선의 가중치 최솟값이 그 때 존재하는 경로만을 고려할 때의 답이라고 할 수 있습니다. 그렇다면 이런 가중치의 최솟값을 최대화하면 되는데, 이는 간선을 가중치 기준으로 정렬하고 가중치가 작은 것부터 차단해가며 완전히 모든 경로가...
-
[BOJ] 풍선
BOJ4716 풍선 그리디라는 깔끔하고 우아한 풀이가 있으나 실상은 팀노트가 있는 MCMF를 활용하여 짜는 것이 정신적 스트레스를 덜 받습니다. MCMF로 푸는 경우 노드는 SOURCE / SINK 각 팀 방 A, B 로 설정하고 간선의 가중치와 용량을 적절히 설정해주면 됩니다. 단, MCMF로 풀 때에는 일반적으로 사용하는 느린 MCMF로는 TLE를 받게 되며 커팅을 추가하거나 헬조선 MCMF를 사용하여야 AC를 받을 수 있습니다. #include<bits/stdc++.h> using namespace std; using pi=pair<int,int>; const int MAXN=1010; //Hell-Joseon MCMF struct edg{ int pos, cap, rev,...
-
[BOJ] A+B
BOJ1000 A+B 가장 기초적인 문제입니다. //C #include<stdio.h> int main(void){ int a,b; scanf("%d%d",&a,&b); printf("%d",a+b); } #Python a,b=map(int,input()) print(a+b)