돌이 코딩하는 방

우상을 바라보며 당신이 별들을 노래했듯이 당신이 희망을 노래했듯이 시간을 노래해보려 합니다. 현재를 노래해보려 합니다. 어떤 삶을 살아오신 겁니까 어떤 절망을 경험하신 겁니까 얼마나 고통스러우셨길래 그러한 희망을 노래하신 겁니까 저는 현재를 노래하려 합니다 저는 시간을 노래하려 합니다 당신이 죽어가는 모든 것을 사랑하듯이 모든 것을 죽어가게 만드는 시간도 사랑하려 합니다 더 이상 과거에 살 수 없고 미래에 살아보지도 않은 제가 감히 시간을 노래해 봐도 되는 겁니까 과거에 살아봤고 미래에 살 것이기 때문에 감히 시간을 노래해보려 합니다

완벽한 하루 완벽한 오늘만을 꿈꿔왔는데 한 달을, 일 년을, 혹은 그 이상을 오늘만을 위해서 달려왔는데 그 수많은 시간조차 오늘 하루와 맞바꿀 수 없었습니다. 나는 그것을 왜 몰랐을까요 나는 왜 그러한 판단을 했을까요 오늘 하루를 머릿속에 다시 그려볼수록 아쉬움만이 머릿속에 피어납니다 아침으로 다시 돌아가고 싶지만 그럴 수 없다는 것을 알고 있기에 야속하게도 우리는 일방통행 길을 걸어가기에 오늘도 다시 완벽한 어떤 미래의 하루를 꿈꿔봅니다

시간은 모순이다 시간은 모순이다 나랑 제일 가까이 있는 것 같지만 제일 멀리 있는 것 같다 나에게 행복한 추억을 주지만 아쉬움과 후회를 주기도 한다 내가 시작할 수 있게 도와주지만 끝이라는 곳으로 데려가 버린다 내가 빨리 가자고 하면 천천히 가지만, 내가 천천히 가라고 하면 빨리 간다 시간은 언제나 정확해서 나에게 더 커다란 모순을 남긴다 시간이 만든 모순… 그리고 사람이 만든 시간…

문제 링크 : https://www.acmicpc.net/problem/15907 문제 설명 n개의 수들 중에서 최대한 많은 수를 포함하는 ax+b (a는 2이상의 정수, b,x 는 정수) 꼴을 찾아내야 한다. 이때 그 꼴으로 표현할 수 있는 수의 갯수를 출력하면 된다. 문제 풀이 ax+b 꼴에 최대한 많은 수를 포함시켜야 한다. 생각을 해보자. 2로 나눈 나머지로 수들을 분리하는것이 무조건 4,6,8,10..등으로 수를 분리하는 것보다 이득이다. 이는 3,4,5... 등에 대해서도 모두 적용되는 논리이다. i로 분리해서 확인하면 ki꼴의 수에 대해서는 확인하지 않는 것이 이득이다. 이러면 무엇이 떠오르는가? 당연히 소수이다. 즉, 소수에 대해서만 판별을 하면 된다는 것이다. 2000000만까지의 모든 ..

정말 유용한 줄 모르고 정말 늦게까지 쓰고 있지 않았던 자료구조다. priority queue에는 정말 얽힌 사연도 많다. 이 때문에 내가 얼마나 고생을 했는지도 모르겠다. 정말 애증의 관계이다. Prioirty Queue 한국어로는 우선순위 큐라고 불리는 priority queue이다.(줄여서 pq라고도 쓴다) 큐는 큐인데 우선순위가 있는 큐이다. 스택은 마지막에 넣은 것이 가장 먼저 나오고 큐는 가장 먼저 넣은 것이 가장 먼저 나오지만, 우선순위 큐는 기존에 설정이 되어있는 우선순위에 따라서 가장 먼저 나오는 원소가 결정된다. 어떤 상황에서는 집합에서 가장 조건에 부합하는 원소를 찾을 수 있고, 내부는 일종의 항시 정렬된 상태라고 생각하면 편하다. 따라서 삽입 삭제에 시간복잡도가 $O(lgN)$이 걸..

문제 링크 : https://www.acmicpc.net/problem/15311 문제 풀이 친구가 재밌는 문제라고 풀어보라고 했던 문제가 백준에, 심지어는 나는코더다 2017 송년대회에 있을줄은 몰랐다. 아이디어성 문제이다. 루트, 버킷에 익숙한 사람은 좀 더 쉽게 보일 수도 있다. 사실 풀이를 어떻게 써야할지 모르겠다. 그래도 최대한 사고의 흐름을 써보려고 한다. 맨 처음에는 이진법을 생각했다. 모든 값을 다 표기하는데 이진법만큼 쉽고 간단한 방법이 떠오르지 않았다. 하지만 이진법은 자릿수가 계속 올라간다는 문제가 있었다. 1 2 1 4 2 1 뭐 이런식으로 할 수도 없었고, 자릿수가 많은 표기법은 좋지 못하다는 생각을 했다. 2000과 1000000을 계속 생각해봤다. $n^k=1000000$이고 ..

6~7월 두 달 동안 무엇을 하였는지, 앞으로 무엇을 할 것인지를 정리하고, 또 다짐하는 정기 컨텐츠이다. Codeforces 2등. 대기록. 이제 다시 코포를 열심히 할 때가 온 것 같다. 코포를 너무 하나도 안했다. 거의 두 달 가까이 코포를 쉬었고, 이제 다시 시간이 많을테니 열심히 달려봐야겠다. 2등 코포 글은 여기서 볼 수 있다. BOJ 중간고사와 기말고사가 거의 붙어있어서 6~7월에 시험을 두개나 보게 되었다. 그래서 전체적으로 문제 수가 많지 않다. 지난번 이후로 약 63개 정도 늘었으며 하루에 딱 한 문제씩 푼 꼴이다. 근데 실버 - 골드 문제를 너무 많이 풀어서 다음과 같이 보이는 것이다. 실제로 70문제를 푸는 데 걸린 시간을 다 합치면 얼마 안 될 것이라고 생각한다. Solved.ac..

문제 링크 : https://www.acmicpc.net/problem/1395 문제 태그 더보기 Segment Tree Lazy Propagation 문제 풀이 문제를 보자. 거의 Segment Tree Lazy Propagation 연습문제라고 해도 될 정도로 기본적인 연산을 요구하고 있다. 구간의 값을 바꾸는 연산과 구간의 값을 구하는 연산. 값을 바꾸는 연산은 구간 내의 1을 모두 0으로 바꾸고 0을 모두 1로 바꾸는 연산이다. 이때 기존의 s~e 구간을 담당하고 있는 구간의 값이 val이라면 연산을 한 후 새로운 값은 e-s+1-val 로 쉽게 구할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

서론 SCC(Strongly Connected Components)를 구할 때는 크게 타잔 알고리즘과 코사라주 알고리즘을 사용한다. 그 중에서도 코사라주 알고리즘을 사용하는 편이다. 최근에 코사라주 알고리즘의 정당성에 대한 증명을 알게 되어서, 나의 블로그에는 알고리즘의 정당성에 관한 내용이 하나도 없는 것 같아서 글을 적어보려고 한다. 먼저 읽고 와야하는 글 - SCC와 코사라주 알고리즘 - DFS ordering (혹은 Euler Tour. 꼭 이 글 안 봐도 됨) 사전 준비 왼쪽과 같은 그래프에서 오른쪽과 같이 색깔별로 그룹을 묶었다. 이는 위의 글에서도 알 수 있듯이 코사라주 알고리즘을 통해 얻은 결과이며, 이 그룹이 SCC가 맞음을 증명할 것이다. 어떤 그룹이 SCC가 맞다는 것을 증명하기 위해..

문제 링크 : https://www.acmicpc.net/problem/17167 문제 설명 두 숫자 a,b 가 주어져 있을 때, 5000번 이하의 a+=b, a+=a, b+=b, b+=a의 4가지 행동을 통해서 a와 b를 똑같게 만들 것이다. 이때 걸리는 횟수와 그 방법을 출력하시오. 문제 풀이 일단 범위를 줄이는 데 집중을 해보자. 3,9로 수를 시작하는 것과, 1,3으로 수를 시작하는 것은 다른 결과가 나올까? 라는 질문으로 시작을 하게 되면 아니라는 결론이 나오게 된다. 좀 더 확장시켜서 생각을 해보면 항상 a,b를 같게 만드는 일련의 행동들은 c=gcd(a,b)인 c에 대해서 a/c, b/c를 같게 만들 수 있다. 물론 반대도 성립한다. a+=a는 a를 두 배 시키는 것과 동치이다. 따라서 b가..