본문 바로가기

PS

1일 1알고 하는 글 - 실패

LAST UPDATE 2020-03-16

꾸준히 갱신되는 글이다!

갱신이 끝났다.

요즘 갑자기 많이 공부해서 지친 것 같다.

중간에 많이 게을러져서 망한 글(...)이다.

개강해서 바빠져서 그냥 망한 글로 둬야지.

사람의 계획은 언제나 성공할 수 있는 게 아니다 ㅎ..ㅎ


1월에는 solved.ac 플5 랭작(https://nemo-algorithm.tistory.com/3)을 진행했으며, 민트에서 블루 중반까지 오를 수 있었다.

실력이 올랐는지 모르겠는데, 일단 레이팅은 올랐으니 한동안은 알고리즘 이론을 늘리고자 한다.

 

알고리즘 설명해주는 블로그 아니고, 블루 중후반에 있는 누군가가 적는 공부 일지이다.

알고리즘 설명할 레벨도 안된다 ㅎㅎ 구글링하면 다른 똑똑한 분들이 적은 좋은 글들이 많다.

글의 업데이트가 끝날 때 즈음에는, 어떤 변화가 있었는지 기록할 것이다. 이번에도 그럴 수 있기를 바란다.

 

응용력 여전히 떨어지고, 문법 여전히 잘 모른다. 그렇지만 잘하는 사람들은 공통적으로 지식이 많다는 점에서, 일단 알고리즘을 많이 아는 게 중요하다고 판단했다.

약간 억측일 수도 있으나, 실력을 설명할 수 있는 요인이 머리가 안 좋아서라면 정말 답이 없는 거니까, 답이 존재하는 가설을 믿어보자.

 

알고리즘을 많이 공부하다보면, 각 알고리즘들이 가지는 독특한 특성이나 구현법을 깨닫게 되며 실력도 늘지 않을까?


작년까지

 

민트였던 내가 기존에 알고 있던 알고리즘에는  Dijkstra / Segment Tree & Lazy Propagation / Union-Find / SCC / bitmask DP / Convex Hull (Monotone) / Minimum Spanning Tree / 등이 있다. 이외에도 Li-Chao와 Flow 모델링하는 문제를 풀어본 적이 있었다. 


겨울방학부터 글을 처음 작성하는 시점까지 (약 6주)

 

기본 문제 하나씩만 풀고 넘어갔으며, 첫 구현이기에 구현을 많이 완전히 베꼈다.

하루를 쏟아도 이해가 안가는 알고리즘들이 많았는데, 루즈해지지 않기 위해(...) 하루가 끝나갈 때 즈음에는 이해를 포기하고 베꼈다. 그래서 아직도 크누스와 dnc opti는 모르고, 다른 것들도 많이 까먹어서 다시 짜라고 하면 못 짠다.

Manacher / CHT / 2-SAT (값 지정해주는거 안 함) / PBS / Knuth Opti / BCC / DnC Opti / PST / 트리의 지름&중심&반지름 / LIS O(NlgN) / LCS O(NMlgNM) / Aho-Corasick / Centroid Decomposition

 

이외에도 MCMF를 복붙해서 간단하게 모델링하는 문제를 풀어봤다.


이제 이 글의 메인이자 앞으로 꾸준히 업데이트 될 부분이다.

 

2020-02-26 HLD #13510 트리와 쿼리1

 

첫 구현이다. 설명은 이 블로그를 구현은 이 블로그를 추천한다. 여러 블로그를 봤는데 두 번째 블로그의 구현이 정말 좋다. 구현에서 흥미로웠던 점은 구간의 head의 dfsn을 chain number로 사용함으로써, 동시에 세그트리 인덱스로 쓰는 것이다. 이 방식으로 세그트리를 하나만 짜도 된다(하나의 세그트리를 각 구간이 나눠쓴다.). 또한 저 블로그의 의사코드가 정말 좋은게 LCA를 짜지 않아도 된다.

나는 보통 처음 구현하는 개념은 full코드를 보고 짜는데 베끼는데 이번에 구현을 참고한 블로그는 코드를 완전히 제공해주지 않음에도 불구하고, 핵심적인 부분을 스스로 짤 수 있게끔 설명이 좋다. 10번 틀렸다. 보통 이만큼 틀리면 스스로 잘 못 고치는데, CLion이란 IDE로 디버깅 하니까 디버깅이 너무너무 편해서 결국 고쳤다. 진작 쓸 걸 그랬다.

 

알고리즘의 동작 이해(3시간) -> 구현(2시간) -> 디버깅(3시간)

 

알고리즘을 학습하는 데에는 8시간이 걸렸다.

집중력의 문제일 수도 있지만, 이해를 하지 못했을 때 집중력이 크게 흐트러지기 때문에, 이 역시도 실력 같다.


2020-02-27 Rotating Calipus #1310 달리기 코스

 

첫 학습&첫 구현이다. 설명 및 구현 모두 이 블로그를 추천한다. 컨벡스헐을 짜봤다면 내용 이해하기는 어렵지 않다. Rotating Calipus 부분의 구현이 맞왜맞스럽고 내 머리로는 왠지 반례가 있을 것 같지만, 별로 안 기니 일단 외우자.

컨벡스헐 (거의 기본) 문제인 #17403 가장 높고 넓은 성을 짜고 학습에 들어갔다.

 

컨벡스헐 재학습(1시간) -> 알고리즘 동작 이해(30분) -> 구현 (1시간) -> 디버깅(6시간;;)

 

디버깅으로 인해 약 9시간이 걸렸다.

알고 구현할 때까지만 해도, 오늘의 알고를 일찍 보고 다른 응용 문제를 풀 수 있을 거라 좋아했으나 디버깅 무엇;;

로테이팅 캘리퍼스 부분이 틀린 줄 알고, 감히 갓의 블로그를 의심하다가 많은 시간을 썼다;;

알고보니 내가 짠 컨벡스헐 부분의 문제였다. 나는 모노톤 알고리즘을 쓰는데, up_hull과 down_hull을 합쳐서 convex_hull 배열을 만들어주는 과정에서, down_hull의 순서를 거꾸로 해서 넣어주었다. 그리고 그 내용을 한참이나 못 찾았다. 하루가 다 갔네 ㅎㅅㅎ


2020-02-28 2D Segment Tree #11658 구간 합 구하기 3 (Naive)

 

첫 학습&첫 구현이다. 설명은 이 블로그를 추천한다. 세그먼트 트리를 안다면 구현은 스스로 할 수 있다. 세그에 세그 박는 거, 더 어렵게 생각할 것도 없다. 문제는 그냥 구현하는 경우 공간복잡도가 N^2이기 때문에, 너무 Naive 하니 Dynamic Segment Tree를 이용해서 N을 하나 떼고 lgQ를 붙일 수도 있다.

내 이해가 맞는 지 확인할 겸 위의 링크에 있는 Bottom Up방식의 세그도 익힐 겸해서 Naive한 구간 합 구하기 3번 문제를 풀었다.

 

Bottom Up 세그 학습(1시간) -> 구간합 구하기 3 (Naive하게 짜기, 1시간) -> 디버깅(1시간)

 

Dynamic Segment Tree로 짜는 게 2Dseg의 정수인 거 같지만, 하루를 잉여롭게 쓰기도 했고, 내일은 내일의 알고가 기다리고 있으니 넘어가려고 한다.


2020-02-29 LR-Flow #13332 Project Team

 

첫 학습&첫 구현이다. 관련 블로그가 너무 적어서 추천은 잘 모르겠지만, 설명은 이 블로그를 문제풀이는 이 블로그를 참고했다. 근데 오늘 날짜 기준으로는 저 블로그 숫자 하나(member1->plan1)가 잘못된 거 같다. 하한의 합을 구해주었을 때 블로그의 그래프 상에서는 15가 나오는데, 실제로는 16이다. 모델링하면서 주의해야할 사항은 일하는 사람이 아닌 쉬는 사람 기준으로 edge를 만들어줘야 한다. 일하는 사람으로 만들면 people->plan을 나타내는 edge에서 하한이 아닌 상한이 잡힌다.

 

구현은 디닉을 복붙한 후, add_lrEdge함수만 새로 작성해주면 된다.

 

1
2
3
4
5
6
7
8
9
int L=0;//goal
//0:new source 1:new sink
//add_edge(from, to, cap);
void add_lredge(int from, int to, int l, int r){
    add_edge(0,to,l);
    add_edge(from,1,l);
    add_edge(from,to,r-l);
    L+=l;
}
cs

 

이론습득(2시간) -> 구현(2시간) -> 디버깅(4시간)

 

알고리즘을 습득하는 데에는 8시간이 걸렸다.

구현이 거의 디닉 복붙이고, 모델링만 하면 되서 그렇게 어려운 건 아닌데, 디닉을 외워서 짜보느라 구현이 살짝 오래 걸렸고, 아무 생각 없이 일하는 사람 기준으로 모델링한 걸 깨닫지 못해서 디버깅도 오래 걸렸다.


2020-03-01 휴식

 

집안일 하다가 낮잠자고 나가서 밥먹고 산책하고로 하루를 보냈다.

공휴일인데다가 일요일인데 열심히 일한 두뇌님 휴가 보내드렸다 ㅎㅎ;;

그래도 나름의 의무감에 코포는 쳤는데 퍼플이 되었다.

퍼플 후기글은 따로 썼다.

공부한 보람이 있네.


2020-03-02 CHT #4008 특공대

 

복습이긴 한데, 살면서 두 번째로 보는 거다. 으 대수 짱시러 ㅠㅠ 점화식 구하려다가 분리 어떻게 할 지 고민하다가 답봤다 ㅋㅋ 구현도 까먹어서 많이 베꼈다. 이 깃헙 구현 참 좋네. 저 동네 코드는 구조체로 되어있어서 한 번만 이해해두면 코포할 때 등등 복붙이 가능하다 ㅎㅅㅎ;;

 

사실 전날 레이팅 업데이트 되는 걸 보느라 늦게 자기도 했고, 드디어 보라도리가 되었다는 성취감에 너무 행복해서 하루가 많이 날아갔다. 아무것도 안 하기는 뭐해서, 저녁에 슬쩍 복습하고 열심히 공부한 척 하기 ~ ㅎㅅㅎ;;


2020-03-04 MCMF #1258 문제 할당

 

첫 학습&첫 구현이다. Sink를 Synk라고 적어두는 오타가 있지만 이 블로그 괜찮았다. 동아리 24시간 대회에서 한 번 출제된 적이 있다. 플로우 느낌이 물씬 풍기는 문제였다. 모델링 하고난 뒤 "이건 플로우다" 라는 느낌이 들어서 Max-Cost를 구하는 방법을 찾아보니 있길래 복붙해서 풀었던 기억이 있다.

구현은 처음이다. 이번 기회에 SPFA도 처음 익혔다.


2020-03-05 금광 #10167 금광

 

첫 학습&첫 구현이다. 알고리즘 이라기엔 테크닉에 가깝지만, 워낙 웰노운이라고 하니까 1일 1알고에 넣어주자.

이 블로그를 보며 공부했는데 다 비슷할 것 같다.

 

학습에는 의외로 3-4시간 밖에 걸리지 않았다. 구현이 세그에 기반해서, 디버깅에 시간을 안 쏟은 덕분이다.


2020-03-08 DnC optimization #13261 탈옥

 

복습이다. dnc opti를 처음 공부할 때 1일 1알고를 채우기 위해 하나도 모르는 채로 넘어갔었는데, 다시보니 조금 이해가 된다. 하지만 구현할 때 한 번 잘못 생각해서, 디버깅에서 4시간 이상을 썼다.


내일은 내일의 알고를 봐야지!

이 날 이후로 안 봤다고 한다 (...)
여름의 나에게 여름의 알고가 있길 바란다