PA 2016. Shuffle 문제에서 주어진 셔플 연산은 카드 덱을 뒤집는 연산과 동일합니다. 이 사실은 수학적 귀납법으로 증명 가능합니다. $2$ 개의 카드에 대해서는 자명히 뒤집는 연산과 동일합니다. $2^k$ 개의 카드에 대해서는, 덱을 절반으로 나눈 후 각각을 뒤집고 둘의 순서를 바꾸는 것이니, 이 역시 뒤집는 연산과 동일합니다. 카드 덱을 두번 뒤집는 건 아무것도 안하는 것과 동일하니, $t$ 가 홀수일 때 배열을 뒤집은 후 출력해 주면 됩니다. ROI 2022 P5. Максимизация выигрыша 입력으로 주어진 문자열의 길이가 $19$ 이하일때만 문제를 해결할 수 있어도 됩니다. 만약 맨 앞 문자가 전체 문자열의 최댓값이 아닐 경우, 가장 가까운 최댓값을 맨 앞 문자로 옮깁니다. ..
https://dl.acm.org/doi/pdf/10.5555/982792.982916 Cut-cycle duality에 의해 $G$ 에서 minimum cut을 찾는 것은 $G^*$ 에서 minimum cycle을 찾는 것과 동일하다. 아이디어는, $G^*$ 에서 적당한 사이클 $C$를 찾은 다음, $C$의 *안* 과 *밖* 에 대해서 분할 정복을 하고, 이후 $C$의 안과 밖을 오가는 사이클을 찾는 것이다. 분할 정복이 성립하려면 일단 $C$가 $G^*$ 의 Face들을 공평하게 쪼개야 할 것이다. 이런 $C$는 $O(n)$ 시간에 찾을 수 있다. $G^*$ 의 모든 Face를 대각선에 $\infty$ 가중치 간선 넣고 대충 triangulate하자. 다음, $G^*$ 에서 아무 정점을 잡고, sho..
대충 이 노트 의 끝자락에서 한 얘기를 정리했다. 그래프가 2-edge-connected 라고 가정하자. (그렇지 않다고 하더라도 코드가 크게 바뀌지 않는다) 알고리즘은 재귀적이다. 그래프 $G$ 의 DFS 트리에 대해서, 특정 서브트리의 노드를 모두 3-connected-component로 바꿔주는 알고리즘이 존재하고, 이 알고리즘을 bottom-up 으로 호출하면서 "서브트리의 답을 합쳐주면" 된다. 2-connected 인 경우를 예시로 생각해 보자. 서브트리를 컴포넌트로 분할하는 알고리즘이 있다면, bottom-up 알고리즘은 절선으로 연결되어 있지 않으며 루트를 포함하는 컴포넌트들을 가져온 후 이들을 합쳐주면 된다. 3-connected 의 경우에는 컴포넌트 하나만 가져올 수는 없으나, 대신 D..
- Total
- Today
- Yesterday