알고리즘 (16) 썸네일형 리스트형 boj 20641. Sleeping Cows www.acmicpc.net/problem/20641 USACO 문제입니다. Dynamic programming 으로 해결할 수 있는 문제입니다. 문제 해결 관찰) 1. $ s_{j} $ 가 $ t_{i} $ 안에 배정되는 모든 barn 의 크기를 오름차순 시키고 배정할 때 괄호문자열처럼 되어야 합니다. $ s_{i} $ 는 ( $ t_{i} $ 는 ) 2. 배정되지 못한 barn 들은 $ max(t_{i}) $ < $ min(s_{i}) $ 를 만족해야 합니다. 즉 $ t_{i} $ 가 쭉 주어지다 $ s_{i} $ 가 주어져야 합니다. 주어진 $ s_{i} $ 와 $ t_{i} $ 를 모두 합쳐서 정렬을 합니다 ( $ s_{i} $ 와 $ t_{i} $ 의 값이 같다면 $ s_{i} $ 가 먼저 오도.. Atcoder Regular 110 F - Esoswap atcoder.jp/contests/arc110/tasks/arc110_f F - Esoswap AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 구성적 문제인데 감탄스러워서 적어봅니다. 문제 해결 방법은 두 가지 관찰이 필요합니다. 1. $ N $ 과 $ N - 1 $ 은 서로소이고 서로소이면 어떤 인덱스에 있든 아무 인덱스로 갈 수 있습니다. 2. $ X $ 의 수가 $ X $ 인덱스로 가기 위해선 $ 0 $ 번째 인덱스에 위치해야 갈 수 있습니다. 이 두 가지 관찰을 잘 이용해봅시다. 그럼 처음 $ N - 1 $ 수를.. DSU tree DSU 트리는 DSU 로 만들어진 집합에서 세그먼트트리를 돌리기 위해 만들어진 트리입니다. 1. merge 부분 merge 를 할 때 일반적으로는 두 정점의 boss 정점이 다르면 그냥 두 정점의 boss 를 이어주는 식으로 해결했지만 DSU tree 에서는 새 정점을 만든 뒤 두 정점의 boss 를 새 정점으로 이어주고 간선도 만들어줍니다. 수도 코드로 표현하면 이렇습니다. void merge(int x,int y){ x = find(x); y = find(y); if(x!=y){ n++; uf[n] = n; uf[x] = n; uf[y] = n; v[n].push_back(x); v[n].push_back(y); } } 그렇게 되면 boss 정점을 기준으로 tree 가 만들어지게됩니다. 2. find.. 백준 1536번 Dance, Dance 개인적으로 정확한 그래프 모델링을 하기 어려웠습니다 ㅠㅠ 제가 아직 플로우에 좀 약해서 좀 어려웠네요 처음에 짠 그래프 모델링을 갈아엎고 또 갈아엎고 하다 결국 AC 를 맞았습니다 흑흑 ㅠㅠ solved.ac 기준으로 플레4 이던데 다른 유량 문제들 티어에 비교하면 플레1은 족히 받아야 하지 않나 싶습니다. 일단 최대 라운드는 $ N $ 번까지가 최대이라는 것을 알 수 있습니다. 즉 $ x $ 번 라운드까지 갈 수 있다는 것은 그래프 모델링을 하고 유량을 흘려줬을 때 유량 값이 $ x*n $이면 갈 수 있다는 것을 의미합니다. $ x $ 번 라운드가 가능한지 볼 때 그래프모델링을 잘 해줘서 유량을 판단하는 문제라고 할 수 있습니다. 그래프 모델링을 하는 방법은 $ S $ 에서 각각 $ 1 $ ~ $ N .. 조금 신기한 분할정복 1 ~ n 개의 좌표가 있고 q 개의 쿼리가 들어오는데 $ 1 \leq l \leq r \leq n $ 인 $ l $ , $ r $ 이 주어진다고 하겠습니다. 우리가 구할 쿼리는 $ l $ , $ r $ 사이에 있는 값을 xor maximization 하는 겁니다. 왼쪽의 basis 랑 오른쪽 basis 를 합하는 방법을 저는 모르기때문에 seg를 못 쓴다고 하겠습니다. 그럼 분할정복으로 풀어야 되는데 분할정복으로 넘어가도 왼쪽 basis 랑 오른쪽 basis를 합해줘야 할 것 같습니다. 하지만 선형적으로 계산하는 방법이 있습니다. 쿼리가 주어지면 처음 $ 1 $ ~ $ N $ 로 구간을 본다고 생각하겠습니다. 그럼 $ mid $ 값을 정해서 $ 1 $ ~ $ mid $ , $ (mid +1) $ ~ $.. SCPC 3회 1차 2차 예선 풀이 재밌는 문제들도 많았고 특히 오래달리기 저 문제를 통해 확장 유클리드를 공부할 수 있어서 좋았네요 Monotone 문제는 풀려있어서 풀지 않았습니다 ㅠ 1. 괄호 $ DP[x] $ 를 x 번째에서 끝나는 가장 긴 괄호의 개수라고 정의합시다. 그럼 stack 에 ( , { , [ 가 나타난 위치를 저장한 뒤 ) , } , ] 를 만날 때 스택에서 한 개를 pop 해줍니다. 그리고 pop 되어진거랑 지금 닫힌 문자랑 매칭되는 것이면 dp[pop 된 위치 - 1] + pop 된 문자열의 길이를 dp[현재 위치] 에다 저장해줍니다. 당연히 매칭이 안되면 스택을 그냥 초기화 시켜주면 됩니다. 2. 주식거래 그리디하게 풀 수 있습니다. 사는 경우에는 그 전의 주식의 값이 지금 주식의 값보다 크면 바꿔치기 합니다. .. SCPC 4회 1차 2차 예선 풀이 곧 있으면 SCPC 2차 예선이라 4회 예선 문제들을 쭉 풀어보았습니다. 버스타기 회문인 수의 합은 풀려있어서 그 외에 것들을 다 풀어보았습니다. 1. 우주정거장 처음에 이 문제를 삼각형 개수 찾는 문제로 생각해버려서 혼자 삼각형 개수를 $ N * log N $ 만에 찾으려고 쌩쇼했던 기억이 납니다... 하지만 당연하게도 그렇게 푸는 것이 아니고 더 쉽게 풀 수 있습니다. ( 애초에 그게 답도 아니다 ㅋㅋ ) 생각을 전환시켜서 제일 마지막에 만들어지는 $ X $ 를 생각해봅시다. 그럼 그 $ X $ 는 당연히 정점 두 개만 연결되어 있을 것입니다. $ X $ 와 연결된 두 정점을 찾아봅시다. 그 두 개의 정점을 $ A $ $ B $ 라고 했을 때 $ A $ 와 $ B $ 가 연결이 되어있으면 $ X $ .. Boj 11991. Fenced in https://www.acmicpc.net/problem/11991 USACO 문제입니다 그리고 재밌는 문제입니다. 아이디어가 중요한 문제인데 이 문제를 풀 기 위해선 Disjoint-set 개념을 살짝만 가지고 있으면 됩니다. $ (N+1)*(M+1) $ 의 방이 있고 상하좌우 벽들을 잘 뿌셔서 모든 방이 연결되게 하는데 뿌시는 벽의 길이를 최소화 시키는 문제입니다. 즉 $ (N+1)*(M+1) $ 의 정점을 만들고 인접한 정점끼리의 가중치를 사이에 있는 벽의 길이로 하고 크루스칼을 돌리면 됩니다. 엇! 하지만 $ N $ $ M $ 이 둘다 25000이네요 무조건 터질 것이 예상되기에 더 줄여봅시다. 조금 생각을 해보면 크루스칼의 원리에 따라 작은 가중치부터 처리될 것이라는 것이 명백합니다. 즉 어떠한.. 이전 1 2 다음
