전체 글
-
근황Trivia 2024. 12. 30. 01:23
2023년 10월에 친구의 권유를 받아 회사에 들어갔습니다. 작은 스타트업이지만 나쁘지 않은 환경인 것 같아서 계속 다니고 있습니다. JS 문법도 모른 채로 입사했는데, 어느덧 C++보다 JS와 파이썬이 익숙한 훌륭한 사축이 되어있습니다. 2024년 4월에 ICPC World Finals를 다녀왔습니다. 저희 팀(DO Solve)은 21년도의 서울 리저널에서 2위를 하여 월파행 티켓을 땄는데, 코로나 등으로 인해 미뤄지고 미뤄지다가 이제야 대회가 열렸습니다. 대회 자체의 결과는 별로 좋지 않았지만, 좋은 경험이었다고 생각합니다. 다만 귀국길에서 지갑을 잃어버려서 슬펐습니다. 회사 일이 바쁘고, 아직은 남은 월파행 티켓을 찢기 아깝다고 생각하여 올해 ICPC는 참전하지 않았습니다. 비슷한 이유로 SCPC도..
-
Fragmented TreeProblem Solving/Algorithm 2023. 9. 3. 21:43
Codeforces를 돌아다니다가 흥미로운 글을 하나 읽었다. Sqrt Fragmented Tree라는 자료구조로, 글 자체는 7년 전의 것이지만 한국에서 잘 알려지지 않았기에 설명하는 글을 작성한다. Approach 업데이트가 있는 트리 DP는 Centroid Decomposition Tree나, Euler Tour Trick과 HLD를 사용한 소위 Dynamic Tree DP등을 통해서 할 수 있음이 알려져 있다. 물론, 이러한 자료구조들은 구현이 어렵고, 최소한의 생각을 해야 문제가 풀리기 때문에 머리가 아프다. 트리에서 Square Root Decomposition을 사용할 수 있을까라는 생각을 해본 적이 있을 것이다. 트리는 connected component로 나누면 component의 크기 ..
-
근황Trivia 2023. 9. 1. 20:54
주기적인 발작이 왔습니다. PS병이란 건데, 다른 할/하고싶은 일이 없을 때 하루종일 PS를 하는 병입니다. 삶의 즐거움이 되었던 아케이드 리듬게임은 완전히 접었고, 메이플도 완전히 접었습니다. 아마 둘 다 다시 안 하지 않을까... 싶네요. 물론 메이플은 한 열번 정도 접었다 폈다 했습니다. 이번엔 진짜 접을거에요 여튼, 다른 할 일이 완전히 사라졌기에, 당분간 PS를 좀 열심히 하지 않을까 싶어요. 문제를 가리지 않고 마구 풀고 있습니다. 끔찍한 구현의 기하라던지, 제 두뇌론 풀 수 없는 애드혹/컨스트럭티브 문제라던지, 정신이 아득해지는 case work 문제라던지... 티어 범위로만 문제를 뽑아서 대충 거의 다 풀고 있는 것 같네요. 선대나 생성함수와 같은, 제가 아예 모르는 분야 빼고요. 그런 문..
-
MST 이야기Problem Solving 2023. 8. 8. 05:53
어떤 그래프의 Minimum Spanning Tree란, 모든 정점을 연결하는 / 간선들의 cost합이 최소인 / 주어진 그래프의 부분그래프이다. MST에는 흥미로운 성질들이 꽤나 많이 존재하며, 이를 이용한 문제들도 꽤나 많이 존재한다. 내가 문제를 많이 풀어본 것은 아니나, 지금까지 공부한 문제중에서 이를 사용하는 흥미로운 문제 두 개를 소개한다. BOJ 8632. Byteland (from JPOI 2007) 각 간선에 대하여, 해당 간선을 포함하는 MST가 하나라도 존재하는지를 판별하는 문제이다. 다들 알다시피, 하나의 그래프에서는 여러 개의 MST가 존재할 수 있다. Kruscal Algorithm을 생각해 보면, 간선들의 cost를 정렬하고 순서대로 각 간선들을 확인해본다. 여기서 다음의 성질..
-
알고리즘 과외 합니다.Problem Solving 2023. 2. 20. 22:36
현재는 과외 문의를 받고 있지 않습니다. 죄송합니다. 안녕하세요. KAIST 수리과학부 소속 김세린입니다. 아래 링크에서 제 프로필을 확인할 수 있습니다. BOJ: serin solvedac: serin (3103, Master) Codeforces: Serin 모집 대상 KOI, IOI, USACO, NYPC, ICPC 등 경시대회를 준비하는, 특히 대회 상위권을 목표로 하는 학생 영재고, 과학고 등의 내신 수업이나 수행평가를 준비하는 학생 기타 알고리즘 과외가 필요한 분 모집 조건 C언어 문법에 이해도가 있는 학생 수업시간 이외에도 매 주 최소 3시간 이상을 투자할 수 있는 학생 수업 내용 학생이 목표로 하는 바에 따라 수업 내용을 정합니다. C++ STL 자료구조 및 알고리즘 코드의 구현 방식 문제..
-
Journey to TST 문제 셋 공유Problem Solving 2023. 2. 18. 19:36
BOJ 그룹(https://www.acmicpc.net/group/16794)에서 2주 동안 총 44(+2) 문제의 연습 셋을 공유했다. 11일 간 매일 선발고사 난이도에 맞추어 4문제씩 셋을 만들었다. 모든 문제에서 얻어갈 내용이 있으며, 내 9년간의 PS 인생의 정수만 뽑은 문제들이기에(!!) 넷상에 공개되면 좋을 것 같아 글로 작성한다. 문제들의 풀이 또한 본 블로그에 장기간에 걸쳐 적을 예정이다. 아마 한 달 정도 걸리지 않을까 싶다. 난이도는 solved.ac 기준 (플래티넘 상위 ~ 다이아 하위) 한 문제, (다이아 하위) 한 문제, (다이아 중위 ~ 다이아 상위) 한 문제, (다이아 상위 ~ 루비) 한 문제씩 뽑아서 넣었다. 문제 순서는 번호순이며, 결코 난이도순이 아님에 유의하자. 02/0..
-
내가 알고리즘 문제풀이를 공부한 방법Problem Solving 2023. 2. 7. 08:57
기존에도 koosaga님의 글이라던가 남남서님의 블로그에 각종 글들이 있었지만, 자료의 최신화와 내가 겪은 시행착오를 공유하기 위해 작성한다. 특히 첫 번째 링크의 글은 5년이 다 되어가는 글이기 때문에... 내가 스스로 겪고, 공부한 방식에 대해서 방법론 위주로 작성한다. solved.ac 18년도랑 비교하여 23년 2월 현재 PS 환경에서 가장 크게 바뀐 점은 역시 solved.ac라고 할 수 있을 것 같다. 사실 현재 한국에서 알고리즘 공부를 하는 사람중에 solved.ac를 모르는 사람이 얼마나 될지는 모르겠다. 그만큼 solved.ac는 편리하고, 관리가 잘 되고, 자신의 수준에 맞거나 알고리즘에 맞는 문제를 고를 수 있는 시스템이다. AC Rating : 소위 말하는 레이팅작이다. 기본적으로 ..
-
2020년도 대한민국 국제정보올림피아드 선발고사 풀이 (Day 2)Problem Solving/Solution Sketch 2023. 2. 4. 22:02
Day 1: https://dsstar.tistory.com/48 이어서 작성한다. Day 2 1. 마법의 다이얼(BOJ 25012) Solution 각 행에 대해, 해당 행에서 i에 다이얼이 오도록 맞추는 비용을 생각해보면, 함수의 개형은 지그재그 꼴이 된다. 다이얼이 처음 상태에서 위치한 곳의 함수값은 0, 거기서부터 시작해서 좌우로 함수의 기울기가 왼쪽으로 -1, 오른쪽으로 1인 그래프가 되고, 다른 직선과 만나게 된다면 끊기게 된다. 더 정확히 설명하자면, $s$, $e$ 사이의 그래프는 s에서 기울기가 1 증가, $\lfloor (s+e)/2 \rfloor$에서 기울기가 1 감소, $\lceil (s+e)/2 \rceil$에서 기울기가 1 감소, e에서 기울기가 1 증가한다. 기울기가 변하는 점..