노력하는 공대생의 공부일지

어제 대회에서 나온 문제 https://codeforces.com/contest/1700/problem/C 대회 때는 그리디가 될거 같았는데, 자꾸 최근에 글을 올렸듯이 차이를 보는 것이 생각이 나서, 그렇게 생각을 하다보니까 조금 오래걸렸다. 이 문제도 차이를 보는 방식으로 하면 쉽게 풀린다. 왜 그렇나면, 연속된 구간에 1을 더하거나 전체 구간에 1을 빼는 방식은 다루기 까다롭다. 그런데, 현재 i번째 값과 i-1번째 값의 차를 새로운 dif[i]로 정의하면 쉽게 풀수가 있는데, 1~i까지 1을 더하는 방식은 dif[1]에 1을 더하고 dif[i+1]에 1을 빼는것과 동일하고, i부터 n까지 1을 더하는 것은 dif[i]에 1을 더하는 것과 동일하기 때문이다. 그리고 전체 구간에 1을 빼는 것은 di..

사실 별건 아닌데, 내가 애초에 세그 트리를 비재귀로 구현하다 보니가, 레이지가 너무 안 익숙해서 정리한다. 레이지는 대부분 재귀로 구현하고 (비재귀 방식도 있다고는 한다...) 그렇다 보니까 구현도 길어지고 그러는데, 나중에 scpc같은 곳에서 팀노트 없을 때 빠르게 구현해 낼 자신이 없을 때 가끔 써먹어야 겠다... 아 근데 (금광 + 레이지) 세그 비재귀로 짤때는 잘 써먹고 있다. 시간복잡도는 O(nloglogn)인데, 다음과 같은 방식을 이용한다. 1. 업데이트: 구간 [L,R]에 c만큼 더하기. 세그트리 base이기 때문에 최대 특정 길이의 구간은 logN개의 노드로 분할된다. 현재 노드를 x라 하자. 이 노드에 다음과 같은 작업을 할 것이다. 이 노드의 자식 노드들을 업데이트 하지는 않는다. ..

도 땄다. 다행이다!

최근 코포에서 이런 문제가 나왔었다. https://codeforces.com/contest/1687/problem/C 어려운 문제였는데, 아이디어 자체가 발상적이기도 하고 몇번 본거 같아서 적어본다. (사실 대회때는 나올때마다 틀렸음.) 두 수열에 관한 연산을 시행할 때 두 수을 보는게 아니라, 두 수열의 차이를 보자. 라는게 핵심 아이디어 이다. 위의 관찰만 하게 되면, 구간의 연산들이 어떻게 바뀌는지 쉽게 살펴볼 수 있다. 두 구간의 합이 같을 때, Ai=Bi를 시행하는 것은 Ci=Ai-Bi라는 수열을 생각하면, Ci의 구간합이 0이되는 구간에, Ci들을 전부 0으로 바꿔준다는 것이다. 이를 이용하면 문제가 새롭게 바뀌게 되고, 쉽게 풀린다. https://codeforces.com/problems..

술을 마신 김에 써본다. 오늘은 5월 14일 청정수컵 본대회가 있던 날이었다. 대회 후기같은 경우는 dong_gas 의 블로그를 참고해주기를 바란다. 드디어 코드포스 오렌지를 찍었다. 나는 개인적으로 코드포스 블루 이상부터, 어느정도 알고리즘 공부를 했고, 알고리즘 문제 풀이 능력이 뛰어난 사람으로 인식하기 시작한다. 내가 오렌지를 찍는데는, 코드포스를 시작한지 21개월, 알고리즘 문제풀이를 시작한지 대략 2년 하고도 2개월 정도가 걸렸다. 코드포스 오렌지는 고수와 중수의 경계선 부근이라고 나는 생각한다. 오렌지와 레드간의 간격이 되게 넓고 크기에, 그 간격을 뚫기가 매우 어려워, 많은 수의 고수 분들이 오렌지에 머물러 있고는 한다. 그래서 나같은 "가짜 오렌지"와 "진짜 오렌지"의 차이가 명확하게 드러..

gold 에 있는 n binary search 불가 Q : 시작점을 고정시켰을 때 길이가 클 수록 좋은 구간의 값은 커지는가? A : 커진다. 그렇다면 다음 2가지 sub문제로 바꿔보자. 1. 특정 구간이 주어졌을 때 이 구간이 좋은 구간인지를 어떻게 판정할 것인가? 2. 좋은 구간이 주어졌을 때 이 구간의 값을 어떻게 판정할 것인가? 1번은 의외로 쉽게 할 수 있는데, 구간을 정렬하고, 앞에서 부터 합쳐주면서 홀 수 component가 되지 않으면 된다. 이 풀이의 정당성은 쉽게 증명 된다. 2번도 1번에서 파생되어 나온다. 합쳐나가면서 마지막으로 남는 수가 구간의 값이라는 것을 쉽게 알 수 있다. 그렇다면 본 문제를 풀어보자. 이제 핵심 아이디어는 1~39 까지 i를 순회하면서 i가 1일때는 연속된 ..

를 땄다. 이 자격증은 왜 존재할까. 실기를 따야겠다... 응시료 78000원이라 열심히 공부해야겠다.

계산 문제. 아래에 과정을 올려두었다.

f'(x)=0 이라는 건 극값을 갖는 곳. g(f(1))=2라는 건, f(x)의 극값이 t t+2에서 2개 나타나게 하는 t가 존재한다는 것. 따라서 f(x)는 극 값을 2개 가지는 꼴. 삼차함수의 개형을 잘 살펴보면 g(y)=2가 되게하는 y는 유일하므로 f(1)=f(4). (가)조건은 너무 쉬운 조건: 극값을 가지는 f(x)의 x좌표 차가 2일 수 밖에 없다. 따라서 식을 세워 보면, f(x)=(1/2) *(x-a)^2*(x-a+3)+c (a,c는 상수) f(1)=f(4)때려박으면 a=2 or a=1이다. 이때 g(f(0))=1을 이용해 a=1를 찾으면 된다.

은 나다. 최근들어 정신적인 스트레스가 알게 모르게 쌓인게 많은 것 같다. 나는 고등학교때 입시 공부를 하면서 몸이 너무 힘들었는데, 의외로 그때는 정신적으로는 맑았다고 요즘에 느낀다. 내신 공부와 수능 공부라는 뚜렷한 목표가 있는 쳇바퀴속에서 구르고 있을때는 마음이 편했던 것이다. 요즘은 망망대해를 걷는 기분이다. 남의 행복한 모습/일상을 접하게 되면 한없이 침전하게 되는 내 자신을 발견했을 때 특히 내가 꼬여있다는 걸 더 느꼈다. 평생 살아오면서 SNS를 한번도 해본 적이 없는데, 매우 잘한 선택인 것 같다. 우연히 보게 되는 몇 몇 사람들의 행복한 일상은 나에게 너무 독인거 같다. 글을 보고 있는 당신은 나에게 왜 그렇게 비교를 하고 자신을 깎아내리냐고 할 수 있는데, 역설적이게도 나는 스스로 느끼..