Syphon의 자기개발 일지

저녁 6시의 대회다. 이른 시간에 대회를 치게 되니 느낌이 색다르다. 정신이 더 맑은 것 같기도? A: Three swimmers Trivial. AC: 3분 B: Card Deck 어렵지 않게 최대한 큰 lexicographic 값을 만드는 문제임을 알 수 있다. 따라서 간단한 greedy 문제가 된다. 덱에서 제일 큰 숫자 기준으로 옮기기를 반복하면 된다. AC: 9분 C: Maximum width 이런 형식의 문제에 약한 듯 하다. 앞으로 최대한 붙여서 완성할 때 필요한 길이 배열과, 뒤로 최대한 붙여서 완성할 때 필요한 길이 배열을 각각 계산해 둔다면, 각 위치의 간격을 최대화했을 때의 간격을 $O(1)$ 복잡도로 구할 수 있다. 앞으로 붙인 글자 $i$개, 뒤로 붙인 글자 $n - i$개일 때 ..

자다 깨서 정신없이 시작한 대회. A: Shifting Stacks 블록은 오른쪽으로만 이동 가능하므로, 첫번째 stack부터 $i$번째까지 스택까지의 구간에 블록이 충분한지를 모든 $i$에 대해 확인해주면 된다. AC: 5분 B: Eastern Exhibition 택시거리 총합을 최소화시키는 문제인데, 택시거리 특성상 $x$축 방향 거리와 $y$축 방향 거리가 서로 독립적임을 알아차린다면 금방 끝나는 문제이다. 각 축에 대해서 값을 정렬한 후, 중앙값 하나 혹은 중앙값 두개 사이가 모두 최솟값이 된다. 하지만 나는 각 축의 거리가 독립적이라는 사실을 정말 정말 늦게 파악했고, 대회 마감 직전에 풀이를 코딩했다. 심지어 풀이도 앞서 서술한 정해와는 조금 다른데, 우연히 같은 결과가 나와서 맞았다. 대회 ..

대회가 언제였더라? ㅋㅋㅋㅋㅋㅋ 2 주 미루다 이제서야 후기를 쓴다. 이번 후기부터는 자동 생성된 템플릿을 쓴다! 대회 링크를 입력해주면 문항들을 알아서 크롤링해와서 아래와 같이 각 문항 이름과 링크가 자동으로 걸리도록 코딩하였다. 매번 문제 이름들을 복붙하고 링크를 걸어주는 것이 귀찮아서 후기를 미루게 됐었는데, 이제는 정말 간편하게 후기를 쓸 수 있게 되었다. A: Space Navigation 정말 간단한 문제임에도 불구하고 생각을 여러 차례 잘못하는 바람에 많은 지체가 있었다. AC: 10분 B: New Colony 잠시 살펴보면 그냥 구현 문제임을 확인할 수 있다. $k$ 값이 매우 큰 경우는 직접 확인할 필요가 없기 때문이다. AC: 20분 구현이 꼬여서 세번이나 틀렸다. C: Fence Pa..

인생에 한번밖에 없는 대학생활이다. 몇달 전에 교내 커뮤니티에서 익명의 컴공과 선배가 컴공 전공과목들의 후기를 남긴 것을 발견하였다. 졸업을 앞둔 상황에서 자신이 들었던 모든 과목들의 후기를 남긴 것이었는데, 나도 저렇게 기록을 남기지 않는다면 대학에서 수강한 수많은 강의들에 대한 기억이 사라지는 것이 아닌가 싶었다. 그래서 나는 졸업 직전이 아니라 지금, 2학년을 마친 현재부터라도 수강한 모든 강좌에 대한 후기를 남기도록 하겠다. 인생에 한번밖에 없는 대학생활이다. 강의 후기 시작! [ 보다 솔직한 강의평을 위해 글들은 비공개로 처리할 예정입니다 ] [ 궁금한 강의가 있다면 개인적으로 연락 주세요 ㅎㅎ ]

개요 군 문제는 대학을 진학함과 동시에 고민하게 되는 부분이다. 본인은 컴공으로 입학했을 때부터 전공을 살려 군 복무를 하는 방법을 알아봤었는데, 산업기능요원으로 빠지는 방법을 제외한다면 SW 개발병과 정보보호병이라는 두 병과가 있었다. SW 개발병의 경우, 상대적으로 소수의 인원을 뽑고 무조건 좋은 곳(?)으로 배치되는 것 같다. 반면 정보보호병의 경우 상대적으로 많은(매년 150명 정도인 듯 하다) 인원을 선발하는 대신, 배치되는 부대에 따라 열악한 환경에서 근무하게 될 수도 있다고 한다. 하는 일 또한 상당히 차이가 있는데, SW 개발병의 경우 군 관련 SW를 유지/보수/개발한다고 하며, 정보보호병의 경우 CERT에 들어가서 관제 업무를 주로 하게 된다고 한다. 본인은 아직 입대는 커녕 합격도 하지..

간만에 망치지 않은 대회다. A: K-divisible Sum 어렵지 않다. AC: 4분 B: Inflation Greedy이다. AC: 14분 C: Longest Simple Cycle 얘도 어렵지 않다. $O(n)$으로 greedy하게 cycle들을 찾아주면 된다. 전 단계에서 만들어둔 cycle에 이어서 연장하는지, 아니면 새로운 cycle을 현재 위치에서부터 시작할 지 greedy하게 결정해주면 된다. AC: 30분 예외처리를 제대로 못해서 WA를 한번 받았다. D: Journey 시작 위치에서 RLRLRL 처럼 번갈아 길이 깔려 있는 위치까지만 도달 가능하다. RLRL / LRLR에서처럼 같은 방향이 연속해서 나타나는 지점들의 위치를 배열에 저장해두고, 각 시작 위치에 대해 좌우로 이진 탐색을 ..

빨리 풀어야 하는 대회에서는 항상 한 문제에서 막혀버린다. A: Nezzar and Colorful Balls 제일 많이 중복되는 경우만 확인하면 된다. AC: 1분 B: Nezzar and Lucky Number 럭키넘버 $d$에 대해, $a$가 $11d$ 이상이기만 하면 무조건 문제의 조건대로 표현할 수 있다. 1의 자릿수가 $d$인 숫자 하나, 10의 자릿수가 $d$인 숫자 하나로 분해하면 무조건 가능해지기 때문이다. $11d$ 이하일 경우, $d$를 몇번 뺄 수 없기 때문에 그냥 다 해보도록 구현했다. AC: 45분 놀랍게도 이게 44분이 걸렸다. C: Nezzar and Symmetric Array $d$를 정렬한 후 생각하면 된다. 배열 $a$의 값들을 수직선 위에 표시했을 때, 각 구간 값들..

오르긴 하지만 살짝 아쉬운 대회이다. A: Puzzle From the Future 요즘 코포가 어렵다. 내가 알던 A가 아니다 ㅋㅋㅋㅋㅋ 자릿수가 줄어들면 안되고, 높은 자리수가 큰 숫자가 장땡이니 greedy하게 짜면 된다. AC: 5분 B: Different Divisors 문제가 신박해서 잠시 어... 이건 뭘까... 하고 있다가 바로 직관적인 greedy 풀이가 떠올랐다. $pq$ 형태로 소수 두개가 곱해진 형태의 수를 찾는데, $p$는 $1 + d$ 이상인 숫자부터, $q$는 $p + d$ 이상인 숫자부터 찾으면 된다. 엄밀한 증명은 사실 안해봤다. (대회에서는 직관이 최고다) AC: 12분 C: Array Destruction 구현에서 자꾸 꼬여서 풀기까지 오래걸린... 것도 맞지만, 구현 ..

또 떨어진다... A: Replacing Elements 쉬운데 어렵게 생각하다가 3분이나 걸렸다. 지금 생각하면 1분컷 문제... 3분: AC B: String LCM 직관적으로 풀이가 떠올랐다. 두 문자열의 길이를 기준으로 lcm이 되도록 곱해준 후, 두 문자열이 일치하는지 확인하면 된다. 8분: AC C: No More Inversions 오늘 레이팅 하락의 원인. 문제를 잘못 이해해서 50분가량을 날렸고, 제대로 읽은 이후에도 풀이가 떠오르지 않아서 결국 D로 넘어갔다. D를 해결하고 돌아와서야 제대로 된 접근을 시작했지만, 남은 시간이 너무 짧아서 대회 시간 이내에 해결하지 못하였다. Constructive algorithm 문제들은 너무 운빨을 많이 타는 것 같다.. D: Program $x$..

역대급으로 당황스러웠던 대회. A: Wizard of Orz A치고 어려웠다. 문제 맘에 안든다. 8분: AC B: Hills And Valleys $O(n)$ 구현문제인데, 다른 틀린 풀이를 붙잡고 이게 왜 안되지??? 하다가 끝났다. 그런데 해결한 사람 숫자를 보면 나만 못푼 것 같지는 않다. 얘도 문제 맘에 안든다. 5 WA C: Three Bags Constructive algorithm이다. 답을 알면 간단한 문제인데, 딱히 좋은 문제로 느껴지지는 않았다. 그래서 설명도 안할거다 ㅎ (절대 귀찮아서 아님) 1시간 22분에 AC 총평 One hour into the competition인데 A밖에 못푼 상황이었어서 엄청 당황스러웠었다. 그런데 그 상황에서의 레이팅 하락이 20정도밖에 안돼서 더 당..