ps이론 (11) 썸네일형 리스트형 [궁극의 웰노운 알고리즘] 10. Square Counting Technique 굉장히 오랜 시간이 지나고, 드디어 10번째? 맞나? 아무튼 글을 쓴다. 사실 이렇게 글을 올리는 시간이 늦어진 데에는 타당한 이유가 있는데, 그만큼 필자가 배울 수 있으면서 아주 웰노운은 아닌 아이디어들이 줄어들고 있다는 것이다... 솔직히 쓰라고 하면 쓸 수 있는 것들을 많긴 하지만 그동안 여러개의 주제를 하나로 묶어서 글을 올렸다보니 소재가 빨리 고갈되었다고 생각한다. 따라서 앞으로는 그냥 하나의 주제를 올리는 대신 조금 더 글을 작성하는 기간을 단축해볼까한다. 아무튼, 이번 글에서 다룰 테크닉은 사실 그 이름이 실제로 존재하는 테크닉은 아니고, 그냥 general idea중 하나로 생각할 수도 있다. 그러나 이 아이디어를 발상하지 못하는 이상 문제를 해결하기 극도로 어렵기 때문에 이렇게 정형화.. [궁극의 웰노운 알고리즘] 9. SMAWK, min-plus convolution(convex and convex), min-plus convolution(convex and arbitrary) 사실, 이 글의 독자들은 내가 굉장히 자주 주제들만을 적어두고 나중에 채워야 할 글들을 유기하고 있다는 사실을 알 가능성이 꽤 있다. 이러한 부분에 대해서는 굉장히 미안하지만, 일부 주제들의 경우에는 채워지는데에 굉장히 오랜 시간이 들 수 있음을 미리 전한다. 아마도 생각보다 적을 것이 너무 적고 이미 내가 알던 것이거나, 혹은 50장짜리 논문처럼 이해하기에 심히 난해한 알고리즘들이 그러한 경우에 속할 것이다... 아무튼 이번에 다룰 알고리즘들은 최근에 문제를 풀면서 굉장히 깊은 인상을 받았기 때문에 아마도 글이 처음부터 완성본으로 올라갈 것으로 예상된다.[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution - Codeforces [Tutorial] .. [궁극의 웰노운 알고리즘] 8. 제곱근 분할법, MOs Algorithm, 3D MO, Regions Trick, Sweepline MO 굉장히 오랜만에 돌아왔다. 그동안 굉장히 바쁜 일이 있었다...기보다는 그냥 기본기만 단련하느라 새로운 알고리즘을 공부하는걸 소홀히 한 것 같다. 뭐 덕분에 그 사이에 찐렌지를 찍었다거나 루비를 찍었다거나 하는 등의 변화는 있긴 하다. 어쨌든, 앞으로는 최대한 자주 글을 써보도록 노력할 것이다. 이 포스팅 앞에 있는 무수히 많은 설명하지 않은 알고리즘들도 아.....마도 조만간 채워지지 않을까싶다. 어쨌든, 오늘 쓸 것은 크게 "제곱근 분할법"이라는 범주 안에 들어가는 것들에 대한 설명이다. 나도 제곱근분할법이랑 모스밖에 아직은 모르긴 하는데, 나머지 뒤에 있는 것들도 배워봐야겠다. 1. 제곱근 분할법 뭐어... 제곱근 분할법은 이 포스팅을 제외하고도 굉장히 많은 설명글이 있기 때문에 다른 글을 참고할 .. [궁극의 웰노운 알고리즘] 7. Ear decomposition, Steiner tree problem, Boruvka's Algorithm, Dominator tree, Erdos Gallai Theorem 무엇을 기대했는가? 아직 지난번 포스팅을 완료하지도 않은 상태이다. 물론 배우고 서술하는게 그리 어려운 알고리즘들은 아니라고 생각되긴 하는데... 아무튼 새로운 알고리즘을 배우고 싶었기 때문에 이렇게 주제를 선정하게 되었다. 보기만 해도 웰노운의 향기가 풀풀 나지 않는가? 아무튼 나는 위의 내용들중 어떠한 것도 모르기 때문에 일단 배우러 가야할 것 같다... 여담으로 메이드 인 어비스를 봤는데 굉장히 재밌는 것 같다. 특히 어비스의 저주를 받아 고통받는 모습이 일품인 것 같다. 극장판 봐야하는데 어디서보지 1. Ear decomposition 우리는 앞서 단절점과 단절선의 정의에 대해 확인하였고, 이로부터 2-edge connectivity와 2-vertex connectivity에 대해 알아보았다. 물.. 뇌풀이 일지 230912 쓰라는 궁극의 웰노운 알고리즘은 버리고 왜 이런 글을 올렸냐 하면, PS의 공부법에 대한 회의감에 의해 그렇다고 볼 수 있다. 보통 PS '공부'를 한다고 하면, 알고리즘을 배우고 짜보고, 혹은 대회를 전부 업솔빙해보거나 문제를 푸는 등의 행동을 할 수 있다. 그런데 사실 이런 공부법을 취한다면 구현이 굉장히 오래 걸리거나 하는 등의 문제에 의해 효율이 낮아지는 경우가 많다고 생각한다. 물론, 구현도 굉장히 중요한 부분이다. PS를 두 개의 부분으로 나누면 '발상'과 '구현'일 정도이며, 구현이 따라주지 않는다면 아무것도 불가능하다. 그런데 사실, '발상' 단계와 '구현' 단계는 차이점이 있다. '발상'은 일단 일반적인 직관에 따르면, 주로 문제의 난이도를 결정한다. 물론 오직 구현만으로 어려운 문제들도.. [궁극의 웰노운 알고리즘] 6. LGV lemma, Expected Value powers Technique, SPFA, 음이 아닌 다변수 선형 디오판토스 방정식의 해(congruence shortest-path problem) 아주 오랫만에 새로운 글을 팠다...이번에는 조금 더 재미있는 수학을 하려고 수학적인 테마의 주제들을 가지고 왔다. 하지만 이 글이 써져있을 것을 기대하진 않을것이다... 왜냐하면 보통 내가 글을 처음 올린 시점에서는 대부분의 내용들이 비어있기 때문이다. 흠지금보니첫번째포스팅이랑이미지가겹치는군 바로 수정해야겠다. 뭐넣지 흠근데 수식이 뭔가 잘 안써지네 $1$ \( 1 \) 오 이렇게 하니까 되는군 1. LGV lemma 방금 배우고 왔는데, 굉장히 인상깊고 강력한 claim을 기반으로 하는 아이디어이다. 일단, 우리가 풀고자 하는 가장 주된 문제는 다음과 같다: DAG가 주어지고, a_i에서 b_i로 가는 경로들의 쌍 \((P_1,...,P_n)\)의 개수를 세고 싶은데, 한 쌍 내에 존재하는 각 경로들.. [궁극의 웰노운 알고리즘] 5. connected component dp, open and closed interval trick, X2 +1 trick, aliens trick, hirschberg algorithm 이번에 다룰 주제들은 dp이다. 물론 앞으로도 수많은 dp 포스팅을 써야겠지만...아무튼 이번에는 굉장히 웰노운적인 dp 트릭들을 다룰 예정이다. 사실 나도 그냥 이름이 신기해보여서 가져온거긴 한데 aliens trick 빼고는 뭔지 몰라서 공부해야 한다. 물론 이번에도 4번째 포스팅과 3번째 포스팅을 유기하고 왔지만, 뭘 기대하고 들어왔냐는 말은 싹아지가 없어보여서 그냥 안했다. 일단 3번째 포스팅은 거의 다 했고, 4번째 포스팅은 곰국에 막혀서 던졌다. 따라서 5번부터 시작한다. 1. aliens trick 뭐 여기에서 다루는 주제중에서는 가장 유명하고 웰노운인 것 같다. 일단 백준 태그가 정식으로 있는 시점에서부터... 아무튼, 기본적으로 trick의 이름이 붙은 문제에 대해 설명하는 것이 가장 정.. [궁극의 웰노운 알고리즘] 4. tree MO, 단절점 단절선 전반(k-간선 연결성, 온라인 단절점, 단절선, 블록 컷 트리) 뭘 기대하고 들어왔는가? 아직 3번 포스팅을 전부 쓰지도 않았다. 굉장히 나태했던것 같긴 한데...조만간 3번 포스팅을 전부 구현하고 작성하고 나면 시작할 것이다. ...라고 하기엔 3번 포스팅을 작성할 엄두가 나질 않는다. 대충 비츠랑 wavelet tree정도가 남았는데 wavelet tree는 이해는 했는데 안짜봤고, 비츠는 음...사실 대충 감은 잡고 있긴 한데 귀찮다. 병렬로 해도 별일 없겠지 억겁의 시간이 지난 9월 2일...비츠는 쓰긴 했고 wavelet tree는 써야 하긴 하는데...wavelet tree에 대한 motivation을 발견하지 못한 채 방황하고 있다. 그래서 그냥 이 글부터 다시 쓰기로 했다. 1. tree에서의 모스 알고리즘 솔직히 이걸 배우고 조금 감회가 새로웠다. 아.. 이전 1 2 다음
