남남서의 블로그

PS 분야의 사람들이 일상적으로 하는 말 중에 자연수 두 개가 요사이 부쩍 눈에 띕니다. 옛날의 제게 물어봤다면 1,000,000,007과 1,000,000,009를 들었겠지만, 아쉽게도 이들은 아닙니다. 998,244,353과 1,048,576도 아닙니다. 훨씬 작은 숫자입니다. 69와 420입니다. 네, PS 분야에 한정된 이야기가 아니라 훨씬 많은 사람들이 공유하는 인터넷 밈이 맞습니다. 그렇지만 콕 집어서 PS 분야를 언급하는 이유가 있습니다. PS 분야에 몸담은 사람이 많아지기는 했으나 커뮤니티에서 활발히 활동하는 사람은 소수입니다. 그리고 이들 사이에서 이게 즐거운 농담에 불과한 것으로 치부되어 간다고 느꼈습니다. 커뮤니티의 분위기는 영향력 강한 소수의 사람들이 좌우하며, 한 번 굳어지고 나면..

sparse table(스파스 테이블)이라고 불리는 기법이 있습니다. 이 기법에 대해 설명하는 글입니다. 예제를 통해 알아봅시다. 방향 그래프가 있습니다. 모든 점마다 나가는 화살표가 꼭 한 개씩 있습니다. 정점 하나에 말을 놓고, 이 말을 한 칸씩 움직일 거예요. 현재 있는 점에서 나가는 화살표가 한 개 있으니, 그걸 타고 새로운 점으로 갑니다. 새로운 점에서, 그 다음으로 갈 수 있는 곳도 하나밖에 없습니다. 나가는 화살표가 한 개니까요. 이렇게 나가는 화살표를 타고 계속 이동할 수 있습니다. 잘 생각해 보면, 무한히 여러 번 이동할 수 있습니다. 그렇다면 어떤 점 v에서 시작해, k번 전진했을 때 어디에 도착할까요? 이 질문에 빠르게 대답할 수 있을까요? 이런 그래프를 functional graph..

꾸준히 대회에 참가해 실력을 키워봅시다. 글에 부족한 부분이 있다면 말씀해주세요! 개인 대회 정기 대회 특정 사이트에서 지속적으로 개최하는 대회입니다. 회차마다 출제자가 달라지기도 합니다. 대부분 레이팅 시스템을 가지고 있습니다. 가입한 후 대회 있을 때 참가하시면 됩니다. TopCoder SRM(Single Round Match) Codeforces: 링크, 블로그 글에도 설명되어 있습니다. (링크) AtCoder: 링크, 블로그 글에도 설명되어 있습니다. (링크) CodeChef: 링크 CSAcademy: 링크, 더 이상 개최 예정이 없는 것 같습니다. 정보 올림피아드 별도의 글에 자세히 설명했습니다. 링크 국제 정보 올림피아드 (IOI) 한국 정보 올림피아드 (KOI) 일본 정보 올림피아드 (JOI..

PS 용어 정리(링크)의 일부였던 글인데 길어져서 분리합니다. "정올"이라고도 줄여서 부르는 정보 올림피아드(Olympiad in Informatics, OI)에 대해 소개하는 글입니다. 정보 올림피아드들은 형식과 문제 유형이 서로 비슷합니다. 때문에 정보 올림피아드에서 출제되는 문제 유형을 'OI 스타일'로 묶어서 지칭합니다. 대회 시간은 길고 문제 수는 적으며, 각각의 난이도가 높고 여러 단계에 걸쳐 생각을 발전시켜야 합니다. 스스로 고민해 풀이에 도달하는 과정을 중요시하기 때문에, 생각해 내기엔 지나치게 어려운 개념(플로우나 FFT 등)을 사용하는 문제는 잘 출제하지 않습니다. 국제 정보 올림피아드 (International Olympiad in Informatics) 공식 사이트는 오른쪽 링크에 ..

PS(Problem Solving), CP(Competitive Programming), 알고리즘 문제 해결, 정보 문제풀이, 올림피아드 문제 풀이, … 이 분야를 지칭하는 표현이 여럿 있습니다. 보통 문제가 주어진다. 이때 이 문제의 일부(실제로 계산해야 하는 수열, 그래프, 그림 등)는 아직 주어지지 않았다. 그 문제를 해결하는 알고리즘을 생각해야 한다. 알고리즘의 모든 과정을 실제로 구현한다. 위에서 말한 '문제의 일부'를 입력받아 문제를 푸는 프로그램을 만든다. 프로그램의 소스 코드를 제출한다. 몇 개의 데이터를 통해 채점하여 옳은가를 확인한다. 위의 과정을 가리킵니다. 알고리즘 기반의 사고 능력 필요로 하기 때문에 '알고리즘'이라는 단어로 지칭하기도 합니다. 알고리즘 및 컴퓨터 프로그래밍 능력은..

Codeforces https://codeforces.com 러시아에 기반을 둔 사이트이다. 마이크 미르자야노프(Mike Mirzayanov)라는 사람이 만들었다. 2019년 기준으로 9살, 10살 하는 나름 오래된 사이트이다. 비슷한 시스템(정기 대회, 레이팅)을 가진 TopCoder에 비해 압도적인 인기를 누리고 있다. 이유는 많다. 탑코더의 인터페이스는 불편하고, 코드포스는 다른 홈페이지처럼 가입하면 바로 활동할 수 있다. 또 코드포스에서는 블로그에 글을 쓰고 댓글을 다는 활동이 활발해서 커뮤니티 자체가 활발하고 자유분방하다. 정기 대회 시스템 정기적으로 대회(Codeforces Round #nnn)가 열린다. 여기에 참가하면 자신의 레이팅(rating) 숫자가 정해진다. 레이팅에 관해서는 뒤에 썼..