Syphon의 자기개발 일지

몰아쓰는 후기 #3 이번 주는 대회가 많다. A: Three Strings 빨리 Div. 1에 안착해서 이런 문제 후기들 생략하고 앉아있지 않아도 되면 좋겠다. 3분에 AC B: Motarack's Birthday 몇몇 칸이 비어있는 정수 배열이 입력으로 들어온다. 그 비어있는 칸들은 일관되게 $k$로 채울 것이다. 인접한 값들 사이의 차의 최댓값을 $m$이라고 할 때, $m$을 최소화하는 $k$값을 구해 $m$과 $k$ 모두 출력해야 한다. 다들 이진탐색으로 많이 푼 것 같고 problem tag에도 binary search가 있지만 나는 이 문제를 왜 그렇게 푸는지도 모르겠고 어떻게 그렇게 푸는지도 모르겠다. 그냥 빈 칸과 인접한 수들 중 제일 큰 값과 제일 작은 값 중간의 값을 $k$로 택하면 된다..

몰아쓰는 후기 #2 A: Erasing Zeroes 이진 문자열. 1 사이에 낀 0들의 개수를 출력하면 된다. 2분에 AC B: National Project $n$칸짜리 highway 수리를 해야 하는데, 하루에 $1$칸 이하만 수리할 수 있다. 수리를 시작하는 날부터 좋은 날 $g$일과 나쁜 날 $b$일의 주기가 반복된다. 좋은 날에 수리한 highway의 비율이 절반 이상이기 위해서 필요한 최소 날의 수는? 그냥 대놓고 이진탐색이다. 1 WA 후 15분에 AC 이진탐색의 범위를 잘못 잡아서 WA를 한번 띄웠다. C: Perfect Keyboard 26개 알파벳을 일렬로 배열해 키보드를 만들어야 하는데, 입력으로 들어오는 문자열에서 인접한 알파벳은 키보드에서도 인접해야 한다. 일렬로 배열할 경우 한 ..

몰아쓰는 후기 #1 A: Non-zero 정수의 배열이 있다. 배열의 한 원소에 1을 더하는 것을 하나의 operation으로 정의할 때, 배열의 sum과 product가 모두 0이 아니기 위해서 필요한 operation의 최소 횟수를 구해야 한다. Product가 0이 되지 않기 위해서는 배열 내의 0들을 우선 치워야 한다. 1씩 더해서 치운 후에 배열의 sum이 0이 아니라면, 아무 곳에서 1을 얹어주면 될 일이다. 5분에 AC B: Assigning to Classes 주어진 숫자들을 두 그룹으로 나누어 각 그룹의 median의 차이를 최소화해야 한다. 모든 숫자들을 정렬해 나열해놓고, 그 중에서 두번째 그룹의 median값으로 만들고자 하는 숫자를 정하고, 방금 정한 median값의 좌우로 하나씩..

오늘은 귀찮다. 사실 오늘만 귀찮은 것은 아니다. 대회를 한지도 벌써 일주일이다. 일주일동안 귀찮았고, 오늘도 귀찮다. 그래서 이번 후기는 대충 쓰려고 한다 ㅎ 문제 설명 생략한다. 문제 링크 생략한다. 대회 링크는 그래도 있어야겠지. A 그냥 홀수 digit이 두개 이상 있는지 확인하면 되는 것을 괜히 숫자들을 지워나가며 조건을 충족시키려고 하다가 4 WA에 1 RTE를 띄우고서야 뻘짓을 멈추고 풀이를 떠올렸다. 17분 AC. B 그려보고 조금 생각을 해보니 양쪽 끝에서부터 최소 1 씩 증가하면서 중간 어딘가에서 최고점을 찍어야 했다. 증가하도록 깍을 수 있는 부분과 감소하도록 깍을 수 있는 부분을 양쪽 끝에서 확인하고 두 부분이 겹치는지 확인하면 된다. 별 문제 없이 풀이를 떠올렸고, 구현까지 총 1..

현재 Github, Stack Overflow, 백준, Codeforces 등등에서 사용하고 있는 Syphon이라는 handle은 2018년, 그러니까 고등학교 3학년 때 야자시간에 딴짓을 하며 만든 것이다. (호칭으로서 쓰이는 온라인 ID를 handle이라고 부른다) 수면의 높이가 같아질 때까지 물을 이동시키는 syphon처럼, 내가 가진 것을 나누는 삶, 배워서 남 주는 인생을 살자는 마음으로 지은 이름이다. (https://en.wikipedia.org/wiki/Siphon, syphon이라는 스펠링도 사용된다) 영어 보통명사이면서 흔하지 않고, 뜻을 담을 수 있으면서 깔끔한 디자인이 가능한 이름을 찾다가 정하게 되었다. 당시에 내 본명, 온라인 핸들, 그리고 음악활동용 이름 세 가지의 로고를 만들..

다시 논문을 읽으러 가겠다고 선언한지도 3개월이다. 그 사이에 있었던 일은 대략 다음과 같다: 1. 논문을 다시 읽었다. 2. ISMCTS를 다시 이해했다. 3. AI 코드를 작성하던 중, game logic의 구현 방법이 마음에 들지 않았다. 예외처리가 너무 많아졌다. 4. 이에 game logic 모듈을 조금 더 객체지향적으로 refactor할 필요성이 생겼다. 5. 시간이 많이 지나 다시 ISMCTS를 잊어버렸다. 6. 그래도 refactoring은 성공적으로 마쳤다. 이전의 카드 / 문양 등등이 전부 다 문자열이었던 것에 반해 새로운 구현은 모든 것이 class이다. AI 구현 중에 가장 큰 문제가 되었던 것이 play 처리의 어려움이었다. Play를 단순한 (플레이어, 카드) 튜플로 처리하기에는..

맞웨틀(맞앗는대 웨 틀렷지?) A: Display The Number LCD 패널에서 흔히 볼 수 있는 7 segment display가 있다. $n$개의 segment만 활성화 시킬 수 있을 때, display 가능한 최대의 수를 출력해야 한다. 생각과정: 가성비가 최고로 좋은 9를 최대한 많이 출력해야겠다 -> 한 숫자의 가성비가 중요한 것이 아니라 자릿수가 최대한 많아야겠군 -> 1만 잔뜩 출력하다가 segment 개수가 남으면 첫 자리수를 키우자! 1 WA 후 11분에 AC A 치고는 쉽지 않은 편이었으나 11분이나 걸린 것은 unacceptable이다. B: Infinite Prefixes 주어진 이진문자열 $s$가 무한히 반복되는 문자열 $S=sssss...$와 주어진 정수 $x$가 있다. 임..

지난 대회에서 파이썬당한 이후 이번에는 C++로 C와 D를 풀려고 했으나 파이썬의 유혹을 이기지 못하고 이번에도 전부 다 파이썬으로 해결하였다. 하지만 오히려 파이썬을 씀으로써 D에서의 오버플로우 문제를 피해갈 수 있었다. A: ConneR and the A.R.C. Markland-N $0$으로 채워진 배열이 있고 배열에서의 현재 위치가 정해져 있다. 이 배열의 특정 위치들을 $1$로 바꿔놓았을 때, 현재 위치로부터 $0$이 있는 위치까지의 최단거리를 구해야 한다(사실 주어진 문제의 형식은 이와 좀 다르지만 앞의 설명과 본질적으로 같은 내용이다). 단순히 현재 위치로부터 양 옆으로 linear 하게 탐색하였다. 4분에 AC B: JOE is on TV! $n$명의 사람들을 대회에서 탈락시켜야 한다. 사..

밖에 나와있는 관계로 대회를 치지 못할 것 같았지만, 11시 6분에 대회를 뛰자는 Nyso의 연락을 받고 갑자기 필을 받아서 허겁지겁 집으로 향했다. 음주를 꽤나 한 상태였고, 집에 들어와서 컴퓨터를 켰을 때는 이미 13분가량 늦은 상태였지만 지난번에도 조금 늦어 포기한 대회가 매우 아쉬웠던 경험이 있어서 이번에는 핸디캡에도 불구하고 참여하기로 했다. A: Deadline 정수 $n$과 $d$가 정해졌을 때, 부등식 $x+\lceil \frac {d}{x+1} \rceil \leq n$를 만족하는 정수 $x$의 존재성 판별 문제이다. 부등식의 좌변을 ceiling function을 무시하고 미분해 극소가 되는 실수 $x$값을 찾은 후, 그 주변의 정수 2000개를 조사하는 방식으로 해결했다. 19분에 A..

새해의 첫 대회이다. 구사과님의 출제로 오랜만에 코포에서 한글을 본다. A: New Year and Naming 매우 한국적인 주제의 등장에 웃겼다. 연도가 주어지면 육십갑자를 출력하면 된다. 2분에 AC B: New Year and Ascent Sequence 배열 $n$개가 들어온다. 이들 중 두개를 중복을 허용하여 골라 concatenate했을때, 연속된 두 숫자 중 증가하는 숫자가 있다면 이는 ascent sequence이다. (사실 ascent sequence의 조건은 $i