Problem Solving/Baekjoon OJ (24) 썸네일형 리스트형 Class 9 수준 높고 멋진 셋이지만 이 이상은 풀 엄두가 안 난다.. 나는 16998번 「It's a Mod, Mod, Mod World」를 가장 재밌게 풀었다. 정말 오래전부터 고민했던 문제인데, 8483번을 풀고 나니 쉽더라 :) [BOJ 20188] 등산 마니아 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 무난한 트리 DP라고 생각했는데 풀고 나니 DP를 쓰지 않았더라. 나처럼 푼 사람이 거의 없는 듯해서 풀이를 한번 소개해보려 한다. (어쩐지 어렵더라) 더보기 풀이의 전체적인 틀은 트리 dp할 때와 비슷하다. dfs를 돌면서 서브 트리에 대해 문제를 해결한 다음, 이를 합쳐서 전체 트리에 대한 문제를 해결한다. 하지만 이때 서브 트리에서 전해주는 값이 조금 다를 뿐이다. 다음과 같은 상황을 가정해보자. 깊이가 $d$인 노드 $p$를 루트 노드로 하는 서브 트.. Diamond I 달성 '다이아 2 달성' 글을 올린 지 대략 한 달 만에 다시 글을 쓰게 되었다. 시험 기간을 제외하면 2~3주 정도 걸린 것 같다. 내 solved.ac 히스토리를 보면 시험이 언제였는지 한눈에 찾을 수 있을 듯하다. 시험 기간 중에는 코딩을 거의 하지 않았지만 풀고 싶거나 배우고 싶은 문제와 알고리즘들을 따로 모아 두고 틈틈이 고민했다. 이 문제들을 시험이 끝나자마자 쭉 풀어버렸고, 그래서 레이팅이 급상승한 것 같다. (물론 아직 풀지 못한 문제들도 많다.) 마지막으로 푼 문제는 제곱수의 합 2 (More Huge)으로, 출제자가 소멤 블로그에 쓴 글을 참고하여 해결했다. 세 달 전에 제곱수의 합 (More Huge)를 해결했을 때부터 풀고 싶었고 최근에 학교에서 (개인적으로) 가우스 정수를 공부하고 나서.. [BOJ 2867] 수열의 값 2867번: 수열의 값 첫째 줄에 수열의 크기 N(2 n; vector sn(n+1),sx(n+1); ll x,ans=0; stack stn,stx; stn.push({0,0}); stx.push({(ll)1e9+1,0}); for(int i=1;i> x; while(stn.top().val>x) stn.pop(); while(stx.top().val Diamond II 달성 레이지 세그를 배우고 나서 세그 비츠를 잡았고 생각보다 공부가 빨리 끝났다. 사실 시간 복잡도 증명은 느낌만 알고 넘어가긴 했는데, 갓들도 이해를 완벽히 하신 것은 아닌 것 같아서 그냥 넘어가기로 했다. (이러면 경험치 날먹 아닌가?) 2021.06.05 추가 : https://algoshitpo.github.io/2020/03/23/PotentialMethod/ 읽어보자. 그리고 세그 비츠 덕분에 자료구조 경험치가 떡!상해서 solved.ac 시작 이후 처음으로 수학 태그가 경험치 2등의 자리로 내려왔다. 수학은 나의 상징이자 자존심이었는데 자료구조한테 진걸 보자니 조금 속상했다... 조만간 날 잡고 수학 셋을 밀어야겠다. 이전 1 2 3 4 5 다음
