설 연휴(01.28~01.31) 맞이 플3± 밀기

01.27

• USACO Gold Contest를 11시~15시까지 돌리고
• SUAPC 강의가 19시 30분~21시까지 듣고
• 너무 졸려서 좀 자고서 24시에 일어나서 시작한다... 원래는 4일 계획이었는데 3일 계획으로 축소 ㅋㅋ

 

01.28 (00:00 ~ 03:30)

• #1 [P3] 성대나라의 물탱크(http:boj.kr/18227) : 루트 주면서 너무 티 안 낸게 악질적이다
• #2 [P3] MT(http:boj.kr/10265) : 재밌는 편인 것 같다
• #3 [P3] 롤러코스터(http:boj.kr/2873) : 앞 두 개보다 어렵고 재미있다 / 엄밀한 증명은 깊게 생각해보지 않았는데 증명도 재밌을 것 같다 / case work를 엄청 했는데 한 번에 맞았다 만약 디버깅을 해야 했다면 심각했을 듯
• #4 [P3] 동전 게임(http:boj.kr/6000) : 골드인 것 같은데 기여창이 온통 플3 기여다 왜 그런지 잘 모르겠다
• #5 [P3] 괄호 문자열(http:boj.kr/1023) : 파라매트릭 + DP로 풀었는데, 어렵게 돌아간 것 같다 / 이 풀이는 떠올리기 어렵지 않지만 새삼 신기하다

01.28 (12:00 ~ 14:00)

• #6 [P3] 팀 선발(http:boj.kr/1044) : 별로다 / 디버깅이 꽤 오래걸렸다 / 좀 졸았다

01.28 (15:00 ~ 17:00)

• #7 [P2] 넴모넴모 (Hard)(http:boj.kr/14700) : N×M 제한이 있어서 N, M 스왑하면 열 길이가 작아서 비트 타일링 DP 각이 바로 나온다. 이 유형 기본 문제가 P4였던 것 같은데 티어가 왜 더 높은지 모르겠다.
• #8 [P3] 샷(http:boj.kr/1273) : 펜윅은 신이네
• 너무 피곤하네
• 자리를 카페로 좀 옮겨보죠

01.28 (18:30 ~ 21:20)

• 카페도착
• #9 [P4] 기둥만들기(http:boj.kr/2598) : 1, 2, 3, 4를 순서대로 놓는다는걸 잘못 읽음 + 순열 숫자를 잘못 적어둠 / 너무 오래 디버깅 했다

01.28 (23:00 ~ 02:00?)

• 치맥 조지고 24시 카페에 왔다
• 오늘 안에 16문제 채우고 집 가야지
• 잡설인데, 10년 넘은 유사코는 대부분 쉬운 것 같다... 오래 묵은 아이디어들이라 다 거기서 거기로 보이는 듯. 2016년도 문제들부터는 동일 티어라도 훨씬 어렵고 재미있는 듯. KOI도 궁금해서 둘러봤는데 2013년부터 다 퀄리티가 괜찮아 보인다.
• 아니 딴짓하면 안 되는데 괜히 궁금해서 BOI도 봤는데.. 그냥 백준에 올라온 2000년대 문제가 다 괜찮은 것 같다.
• 그냥 옛날이어도 어려운 문제들은 각각의 독특한 성질이 있어서 녹슬지 않는 것 같고... 애매한 플래 중위 이하는 이제는 국밥이 되어버린 것들이 많은 듯...
• 아무튼 USACO는 앞으로 뽑을 때 좀 2016년 이후꺼로만 뽑아야겠다.

 

• 아니 어려운 문제만 남은건가 너무 졸리고 어렵네요 ㅈㅈ 내일 마저 합니다..
• 문제들이라도 미리 읽어두죠..

01.29 (19:00 ~ )

• 너무 푹 자고 일어나버렸다.. 흠...
• 그리고 하루 종일 아무것도 안 했네..

01.30 (00:00 ~ 08:00)

• 피씨방 가서 피파랑 PS랑 번갈아 했다.
• 효율이 그다지 좋진 않았나 보다.
• #10 [P3] 물류창고(http:boj.kr/28296) : 하는 김에 스몰투라지 구현법을 다듬었다
• #11 [P3] 꼬리달린 박성원숭이(http:boj.kr/2105) : 좀 어려운 풀이법으로 푼 것 같은데... 나는 유니온 파인드 트리 구성해서 풀었다
• #12 [P4] 블록 쌓기(http:boj.kr/2388) : 깔끔하고 재밌는 문제다. 국대 훈련 문제집에서 뽑은건데 왜 뽑아놨는지 알 것 같다
• #13 [P3] 삻의 질(http:boj.kr/10227) : 3년 전에 풀었던 당시에 풀이를 까고 충격받았던 어떤 골1과 메인 아이디어를 공유해서 비교적 쉽게 해결할 수 있었다. 그럼에도 재밌다 :)

 

• 며칠간 P3을 몰아서 푸니까 느낀 점이 있다면, 확실히 뇌를 깨우는 문제가 있고 머슬메모리로 푸는 문제가 있다는 것이다.
• 머슬메모리 늘리는 것도 구현력 느니까 당연히 나쁠 거 없긴 한데, 이런거 대충 풀고 히히 오늘도 대충 스트릭 때움 이러면 안 되는 느낌이다.
• 하나를 풀어도 좋은 출처의 문제를 푸는게 생각 이상으로 중요하다는 느낌을 받았다.

01.30 (21:00 ~ 22:30)

• 또또 대충 누워있다가 일어나서 씻고 닭갈비 시켜서 대충 먹으면서 풀기 시작했다.
• #14 [P3] 스티커 수집(http:boj.kr/1093) : 너무나도 간단한 MITM 문제다. 왜 골드가 아닌지 잘 모르겠다..
• #15 [P3] Farmer John Solves 3SUM(http:boj.kr/18317) : 그냥 적당한 DP. 구간 포함배제 형태의 점화식을 모르는 사람이라면 교육적일 듯.

01.31 (20:00 ~ 22:00)

• 사실 카페 온 지는 꽤 됐는데 사실상 자고 있었다. 20시부터 시작한 듯.
• #16 [P2] 반 나누기(http:boj.kr/1741) : 몇가지 도움이 될 만한 관찰들을 하긴 했는데 슬슬 힘들어서 풀이를 검색해서 "제일 차수가 작은 정점"이라는 키워드를 보고 풀었다. 왜 이 생각을 못했나 싶다. 제일 차수가 작은 정점을 잡는 그런 흐름이 '일시적으로만 도움이 되고 어차피 계산량 대부분을 줄여주지는 못할 것'이라고 느끼고서 가장 큰 컴포넌트 크기의 상한이 작다 이런거 관찰하고 있었다. 랜덤 풀이도 좀 고민해보고... 이런것들도 팩트는 팩트긴 한데... 그래프의 정점을 비둘기집이라고 생각하는 그 발상을 종종 해야되겠다.
• #17 [P3] 콜라 줍기(http:boj.kr/25623) : 대각선 방향으로 스윕하면서 DP 해주면 된다. 재밌다!

 

 

후기

꾸준히 많은 문제를 푸는게 생각보다 더 어렵다는 걸 느꼈다.

한동안 P3~P2 문제들을 일정을 잘 쪼개서 많이 풀어보도록 해봐야겠다.