solved.ac 플5 랭작 후기 - 심심해서 끄적이는 글

LAST UPDATE: 2020-02-16

꾸준히 갱신하는 글이다.

갱신이 끝났다. 반 페이지 푼 것 같다.

처음의 계획처럼 한 페이지를 다 풀지는 못했다.

글의 마무리에 어떤 변화가 있었는지 적어두었다.

---

이건 학습용 블로그가 아니고, 알고리즘 일상 블로그라, 풀이를 자세히 적진 않는다.

먼 미래에 누군가가 이 글을 본다면

그냥 코드포스 민트-블루 왔다갔다 하는 사람이 이렇게 공부하고 있구나, 그래서 어떻게 되었구나(아직은 아무것도 되지 않았지만 이 글이 끝나갈 때 즈음에는 결과가 나오지 않을까 싶다) 정도로 참고하면 되지 않을까 사실 이 글 읽을 시간에 한 문제라도 더 푸는 게 이득이다.

 

일단 플5랭작부터 시작하며, 다 풀지는 못할 것 같고 난이도에 익숙해질 때 즈음, 혹은 첫 페이지를 다 풀 때 즈음 플4로 넘어가고자 한다.

 

이 랭작의 목표는 "여러 개념에 익숙해지는 것, 그리고 여러 생각을 접하는 것"인데

중간에 루즈해지지 않는 것이 가장 중요하다고 생각하기에

문제당 길어야 10분 정도만 고민하고, 답보면서 넘어가는 식으로 풀고 있다.

시간낭비를 막기 위해 푼 문제도 구현 전에 답을 찾아보고 구현에 들어가며

또한 처음 구현하는 개념의 코딩은 인터넷의 좋은 소스를 베끼면서 넘어가고 있다.

차례로 모든 문제를 푸는 것을 목표로 하지만, 지나치게 많이 짠 문제(ex. 세그먼트 트리)와 안 조아하는 문제(스페셜 저지, 테스트케이스 문제)는 적당히 넘어가고 있다.

 

---

이것만 풀어도 충분하지 않았나 싶은 것들 모아놔야지. 사실 나중에 내가 볼 용도로 적고 있다.

물론 다른 문제들도 금방 짜는 맛이 있어서 랭작이 덜 심심하당.

 

2140 SCC - SCC 기초 문제! 짜보는 건 처음이라 베꼈다. 생각보다 간단하게 생겨서 놀랐다.

2261 가장 가까운 두 점 - 힘들었다. 아직도 잘 모른다. 백준님 글 보고도 이해가 안가서 코드도 거의 베끼다시피 해서야 알 동 말 동 하다.

11400 단절선 - 단절선 대강 들어는 봤는데 짜는 건 처음이라 보고 베꼈다. 아직도 잘 모르겠다.

9376 탈옥 - 답 보고 허탈했다. 구현은 스스로 했다.

4196 도미노 - 위상정렬인 줄 알았는데 답보니까 SCC였다. SCC 기본 형태인데 2140 푼 지 얼마 안됐어서 구현이 기억에 남아있어서 안 보고 짜봤다.

2842 집배원 한상덕 - 투포인터가 O(N)이라는 사실을 처음 알았다. ㄷ;; 또한 이러한 유형의 문제를 코포에서도 간간히 본 거 같은데 앞으론 틀리지 말아야지. 그나저나 map사용법을 두 개나 잘못 알고 있다는 걸 깨달았다. find연산을 find()를 안주고, map[] 대괄호 안에 key를 넣어서 찾았었는데 이 경우 size()연산에 영향을 준다. 또한 구조체를 key로 사용할 경우 operator 설정을 변수 하나로만 대충했더니 키가 중복 처리됐었다.

13306 트리 - 이건 어릴 때 풀었던 문제다. 쿼리를 뒤에서부터 처리한다는 아이디어가 재미있는 문제다. 구현은 안 어렵다.

8986 전봇대 - 오 삼분탐색 문제 처음 풀어봤다. 구현도 꽤 쉬웠는데(.....남의 코드에 의존해서 풀엇긴 하다 당시에 이분탐색도 잘 못 짰었는지라.....),고등부 3번이라서 의아했다. 0번이어야 하는 거 아닌가 싶을 정도다.

2879 코딩은 예쁘게 - 역시 답보고 풀었다. 변화량을 가지고 새로운 배열을 만든다. 부호로 그룹 나누고 그룹 내에서 최솟값 기준으로 분할정복하는 문제이다. DP할 떄 처리하는 부분은 덧셈밖에 없는데 굳이 DP로 분류하는 이유는 모르겠다.

4716 풍선 - 플로우같은데 공부하고 싶지 않았다. 그게 왜 플5에? 하면서 답 찾아보니 그리디 풀이가 존재했다. 그리디 풀이가 약간 KCPC F번 비슷한 느낌이었는데 그 문제는 틀렸어서 같은 기법인지는 모르겠지만, 차이를 정렬하고 교환하는 기법이, 요즘 자주 보이는 느낌이라 숙지해둬야겠다.

3830 교수님은 기다리지 않는다 - LCA에서 부모 배열에 가중치도 같이 넣고 돌리면 될 거 같긴 한데, 짜기 싫어서 답 찾아보니 역시 더 쉬운 풀이가 존재한다. 신기하네요. 근데 int함수 return 안해줘서 런타임에러 고생했다.

11585 속타는 저녁 메뉴 - 누가봐도 단순 kmp인데 왜 플5인지 의문이다. 그러나 나는 그 kmp를 아직까지 공부하지 않아서 이번에 새로 공부하느라 너무 고생했다. 로직 너무 어려운 것.

11402 이항계수 4 - 루카스 정리 기본형이었다. 이런 신기한 정리 처음 알아간다.

2463 비용 - 13306 트리 비슷하게 뒤집어놓고 생각하는 문제였다. 사용하는 알고리즘은 다르다.

1086 박성원 - 비트마스킹 DP....??!! 비트마스킹 이렇게 하는 건 처읍본다(사실 비트 자체를 많이 안 써보긴 했다.

2532 먹이사슬 - 어릴 때 못 풀었던 매우 추억 많은 문제이다. 이번에는 답보고 풀었다 ㅎㅅㅎ;; 세그 사용법은 볼 때마다 신기하다.

1135 뉴스 전하기 - 적당히 dfs하면서 풀어주면 된다.

9577 토렌트 - 이분매칭이다. 응용해서 써먹는 건 처음인지라 재밌었다.

15559 내 선물을 받아줘 - 누가봐도 Union Find Tree

14444 가장 긴 팰린드롬 부분 문자열 - Manacher 알고리즘 기본형이다. 라빈카프도 태그에 달려있던데, 나중에 공부해야지ㅎㅎ;;

1486 등산 - 1238 파티의 2차원 형태이다. 다익스트라 한 번, 역방향 그래프 다익스트라 한 번 돌려주고 합이 d보다 작은 경우, 높이를 정답과 비교해서 갱신하면 된다. N이 작아서 플로이드도 되고 그냥 다익스트라 죽어라 돌려도 된다고 한다.

 

전부 업로드 하진 않았고, 어느 순간 게을러졌는데, 약 5주간 50문제 정도 풀었다. 답지는 그 중 45개 이상 봤었고, 구현까지 필사한 것도 35문제는 그냥 넘어갈 것 같다.

---

[변화] 답을 많이 보긴 했고, 코드조차 베낀 문제가 정말정말정말 많지만, 나름의 변화가 있었다.

구현이 꽤 편해졌다. 그동안 골드 문제를 풀 때에는 문제 풀이를 생각해도 "이걸 어떻게 짜?" 하면서 구현 못하고 멍때리는 일이 많았는데, 이제 어느 정도 선에서 구현이 가능하다.

코드포스 랭킹도 올랐다. 구현에서 뇌절하는 일이 줄어든 덕분도 있지만, 이전보다 확률적으로 0.7문제 정도 더 해결할 수 있게 된 것 같다.

 

계정은 nemo이다.

 

문제풀이를 시작한지 2주차 즈음에 크게 한 번 오르고, 이렇게 공부해도 되겠다는 확신을 가지고 있었는데

그 이후로 한 달간 미동이 별로 없어서 왜이러나 살짝 힘들어했었다.

엊그제 있었던 라운드에서 크게 한 번 더 올랐다. (1844)

실제로도 Div.2 CD를 접근하는 방식이 개선되었고, 구현도 편해졌으니 만족스러운 성과이다.

---

글은 여기서 끝내고자 한다.

솔직히 아직도 자력으로 플5를 푸는 건 정말 힘든 일이다.

그래도 변화에서 증명했듯이

"답을 봐도 좀 모르겠는 상태"와 "답을 보면 좀 알겠는 상태" 사이에는 분명한 실력의 상승이 있었을 것이라 믿는다.

이런 공부법을 유지한다면 계속 실력(레이팅)은 오를 것 같다.

아직 한 페이지를 다 푼 것도 아니다. 반 페이지 즘 풀었다.

 

그렇지만 빠른 기간 안에 더 어려운 문제를 풀 수 있게 되어야 한다는 강박관념이 생겼다.

무리해서라도 다음 난이도로 넘어가고자 한다. 앞으로 한동안은 플2-플5에 있는 문제를 풀 것 같다.

아직 플1 문제들은 구현조차 못하겠고, 다이아는 답을 봐도 모르겠다. 사실 플5도 그렇다.

그래도 플5를 푸니 플3-4가 이해가 이제 가니까, 플3-4문제들을 보면 언젠가 플1다5도 되지 않을까.

---

후편을 만들었다. 이번에는 1일 1알고하는 글이다. 꾸준히 하는 게 중요한 것 같다. 이번에도 열심히 해야지!