돌이 코딩하는 방

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

지난번 3월 23일 이후로 어떤 것들을 하였고, 어떤 성과를 거두었는지 정리하는 포스팅이다. 일기형식의 글이고 굳이 보실 필요는 없다고 생각한다. 일단 약 두달정도 되는 기간에서 semi-game cup을 빼고 얘기할 수가 없을 것이다. 약 1달 정도 되는 기간을 전부 투자했고, 정말 좋은 경험을 했고, 많은 것들을 얻었지만 그와 반대로 백준 문제나, 코포 등은 신경을 쓸 수가 없었다. 그래도 성공적으로 잘 마무리 되어서 정말 좋았다. BOJ 기록 평균적으로 하루에 한문제 정도 풀었다. 사실 엄청 많은 양은 아니지만, 푼 문제의 난이도나 1달동안 semi-game cup에만 시간을 쏟은것을 생각하면 그렇게... 적다. 사실 그냥 문제량을 좀 더 늘릴 필요는 있다고 생각한다. 요즘은 koi를 돌고 있다. ..

백준 게시판에도 올렸지만 혹시 못보신분들을 위해서 두 버전으로 다시 올려봅니다!!

그냥 주저리 주저리 쓴 글입니다... 가독성이 안 좋을 수 있지만 나름 재밌을 수도 있습니다. 전체 후기 한 달 동안 다른거 줄여가면서 정말 열심히 달려왔다. 지금 이 그림을 머릿속에 그려놓긴 했지만, 이 그림이 현실로 다가올지는 상상도 하지 못했다. 오늘이 생일이라서 더 뜻깊은 것도 있는것 같다. 시작은 그저 아이디어는 조금 있는데 백준 스택 권한이 없어서...도 있었고, 게임문제를 미친듯이 풀어대는 나의 모습을 보고 주위에서 장난식으로 한 번 만들어보라고 했던 이유도 있었다. 무엇보다 사람들의 어그로도 끌고 싶었고, 뜻 깊은 경험이 될 것 같았다. 사실 의지만 가지고 하기에는 좀 많이 벅찬 여정이었다. 최근 대회퀄이 너무 좋았기 때문에, 계속해서 뇌절 아이디어만던져대고 시간은 다가오고, 급박했었다. ..

제가 한동안 포스팅을 하지 못한 이유를 드디어 공개하네요. 일정이 빡빡하여 진행이 힘들 수도 있어서 미리 글을 쓰지는 못했는데, 거의 5.16에 하는 것이 확정된 듯 싶습니다. 최근에 좋은 대회가 많았어서 부담이 좀 많이 되지만 좋은 검수자님들을 많이 둔만큼 좋은 결과를 뽑아내기 위해서 최선을 다해보려고 합니다!! 5.16에 Semi-Game Cup으로 돌아오겠습니다!! 제가 백준에 쓴 Semi-Game Cup 홍보 게시물 링크입니다. https://www.acmicpc.net/board/view/50953

4/16 만들고 싶은 문제는 있는데, BOJ stack 권한이 없었다. 대회를 한 번 만들어 볼까? 라는 이야기를 Blackking26과 나눴다. 게임 문제들 모아서 대회를 열어보라는 말도 조금 들어본 적이 있어서 관심이 생겼다. 4/19 흥분되었다. 생각보다 재미있었고, 아이디어는 가지고 있던 것들이 꽤 많이 나왔다. 사람들도 열심히 모았고, 어느정도 구체화 시켜서 개최 요청 메일을 보내드렸다. 현재까지 만들어진 문제는 왕들의 외나무다리 돌게임, NDSR 게임, 돌 술래잡기 게임, 고인물의 리듬게임, ㄱ 폭탄게임이다. 고인물의 리듬게임은 훌륭한 대장장이 gs18115님에 의해서 강화가 될 예정으로 기초 단계만 만들어 놨고, ㄱ 폭탄 게임은 최근에 엄청난 대회 퀄리티 때문에 부담감을 가져서 풀이 없이 문..

최근에 어려운 문제들을 도전해 보면서 느꼈는데 난 관찰에 제일 강한 것 같다. 그냥 문제에서 얻을 수 있는 단서를 관찰하는 능력도 떨어지지는 않지만, 내가 직접 손으로 예제를 만들고 풀어보면서 답을 찾은 경우가 굉장히 많다. 직접 혼자 게임을 진행하며 승리 방법과 조건을 찾는다던가, 작은 모든 경우에 대해 다 해보면서 방향성이나 중요한 사실들을 관찰하는 경우가 꽤 있었다. 툭툭 던진 말이 중요했던 경우도 꽤 많았고, 애초에 이런 것이 좋아서 시작하게 된 PS이다. 사실 이러한 부분을 제외하면 stonejjun이라는 코더가 그렇게 특별한지도 모르겠고, 엄청 뛰어난지도 모르겠다. 개인대회에 그렇게 강점이 있는지 모르겠다. 스페셜리스트 같은 느낌인것 같기도 하다. 이상한 말들은 그만하고, 이 글의 진짜 목적은..

이번에 다양한 테스트 시즌, 입학 시즌 등등의 이유로 코딩(PS)를 시작하려고 하시는 분들이 꽤나 있을 것 같다. 그러한 분들, 이번 신입생들 등을 위해서 내가 그나마 도움을 줄 수 있는 부분인 DP에 대해서 이야기를 풀어나가 보려고 한다. 전체적으로 DP 문제들에 대한 소개, DP 문제란? DP 문제 푸는 법 등에 대해서는 이 글에서 자세히 말을 했었다. 좋은 글이니 DP 공부를 하려면 한 번 읽어보는 것을 추천한다. 이번 글에서는 DP를 공부하는 법/DP를 잘해지려면? 과 같은 주제에 대해서 다뤄보려고 한다. 0. DP란? DP 문제를 푸는 법 위에서도 언급을 했지만 이 글에서 상당부분 잘 말해주고 있으니 참고하면 될 것 같다. 1. DP 문제의 특징 1.1 아이디어 & 생각 > 구현 일정 수준까지는..

지금까지의 기록들, 지금까지 해온 내용들에 정리해보고 돌아보려고 쓰는 글이다. 그냥 CODER stonejjun에 관한 글이다. 알고리즘이나 문제 풀이글은 다른 좋은글이 많다. BOJ 기록 문제 수 맞은 문제 수 808 문제로 428등에 랭크되어 있다. 400문제까지는 랭작을 하던 때도 있었고, 최근에도 물론 구현연습, 손풀기를 위해 쉬운문제들을 한 두번씩 풀기는 하지만, 겨울 사이에 문제수가 확 늘게 된 것도 사실이다. 생각보다 빠르게 증가하고 있고, 1000문제도 금방 다가갈 수 있을 것 같다. 대회 백준에서 열리는 대회는 생각보다 별로 참가를 하지 않았다. 키파컵에서는 퍼솔을 먹고, 2문제를 풀었지만, 푼 2문제는 각각 번외와 채점 준비중이 되었다. Good bye 2019에서는 4솔.... E정도..

지난번에 이어서 다시 모여서 셋을 돌기로 하였다. 셋 선정에 관해서는 또 rkm0959님께 신세를 졌고, 추천해 주신 셋 중에 갑자기 lotus가 무조건 매운맛으로 돌자고 하는 바람에 2017-2018 ACM-ICPC NEERC Northern Subregional로 돌게 되었다. solved.ac 기준 4다이아 1루비인 무서운 셋! stonejjun,lotus(easrui),karuna 가 같이 돌게 되었다. 백준에서는 https://www.acmicpc.net/category/detail/1795 에서 볼 수 있다. 결과는 다음과 같다. 솔직히 정말 많이 놀랐다. 이정도 성적이면 이대로 바로 대회를 나가도 꽤나 준수한 성적을 거둘 정도의 상황이 나왔다. 셋을 추천해주신 rkm0959님도 조금 놀라시더..