ps:start
PS / Algorithm
목표
- 즐거운 PS (강조!!)
- 대회에 참가할 것도 아니고, 기업의 코딩테스트를 볼 것도 아니다. 그냥 나에게 PS는 취미인데, 취미라면 즐거워야 한다.
- 따라서, 코딩테스트 수준의 문제로 난이도를 한정지을 필요도 없다. 시간에 맞춰서 푸는 연습을 할 필요도 없다.
- 어차피 재미로 하는 거니, 활용할 일이 거의 없을 것 같은 알고리즘도 공부해보자
- 실력이 쪼렙에서 안늘더라도 스트레스는 받지 말자. 어차피 목표는 고수가 되는게 아니다. 능력도 안되지만, 고수를 목표로 빡공할 시간 여유도 없다.
- Python으로 풀이
- 물론 C++보다 많이 느리고, 그러다보니 심지어는 python으로는 시간내에 풀 수 없는 문제도 있어서 PS를 본격적으로 하기에는 부적합하지만, 파이썬만의 코딩하는 재미가 있다. 재미가 중요하다.
- 사실 Julia도 얼핏 보기엔 꽤나 재미있어 보여서 시도해보고 싶었지만, 지원해주는 사이트가 없다 ㅜㅜ
- 최적 알고리즘으로 풀이
- 코드가 통과되었더라도, 다른 사람의 코드를 보고 더 최적의 솔루션이 있는지 확인해 보자.
- 가독성 있는 코드를 작성
- 가능한 경우에는 범용적이고 재사용가능한 함수나 클래스를 만든다 (Teferi library)
2023년 목표
- 2023년에는 탈PS!
- 진짜 완전히 접는거는 아니지만.. PS에 투자하는 시간을 확 낮출것이다. 그시간에 게임을 하든 만화책을 보든 좀더 생산적인 활동을 하겠다. PS는 솔브닥 스트릭유지 정도만..
- 2023년 상반기까지 목표를 마무리하고 PS를 접도록 하자.
- ⇒ 상반기가 지났지만 달성한 목표가 아무것도 없다 ㅜㅜ 목표를 수정하고 2023년 말까지 탈PS 하도록 하자
목표가 아닌 것
- 정해진 시간 안에 빠르게 코드를 작성
- 대회를 위한 연습이라면, 가독성을 다소 희생하고 필요하면 미리 만든 매크로등을 동원하는 등의 방법으로 빠르게 코드를 짜는 것도 필요하겠지만, 나의 경우는 아니다.
- 극도의 최적화
- 최적화는 시간복잡도를 줄이는 경우에만 의미를 둔다. 상수항을 줄이기 위해서 노력할 필요는 없다..
- 상수항을 줄이는 테크닉이 범용적으로 사용되는 테크닉이거나, 목표 로직이 공통 함수라면 고려할 여지는 있다..
- 특히 파이썬은 생각지도 않은 부분에서 속도 차이가 나는 경우가 많아서, 실제 수행속도가 가장 빠른 코드를 찾는 것은 너무 많은 노력이 든다.
- 인터프리터 언어이다 보니, 보통은 컴파일러가 알아서 최적화해주는 부분들을 못해주는 경우가 많고, 의외의 곳에서 시간 손실이 생기는 경우가 많다.
- 한 예로, 전역변수에 접근하는 시간이 로컬 변수에 접근하는 시간보다 유의미하게 느리다
- c언어로 구현된 라이브러리 함수는, 파이썬으로 재구현했을 경우 그 속도를 따라잡기가 거의 불가능하다.
- 숏코딩
- 코드를 짧게 쓰려고 노력할 필요는 없다. 가독성 있는 코드를 만든다
- 멋있는 코드
- 비슷한 맥락으로, 막 신박한 테크닉을 사용해서 멋있게 코드를 짤 필요는 없다. 멋있는 코드보다 예쁜 코드를 짜자!
- 이미 라이브러리에 존재하는 로직을 재구현
- 만약, 전혀 모르는 알고리즘이라면 공부 차원에서 새로 구현해 볼 수도 있지만, 라이브러리에 포함될 정도의 알고리즘/자료구조를 모르는 경우는 없을 듯. 그러니 그냥 라이브러리에 구현되어있는 알고리즘을 사용하자
- 많은 문제를 풀기
- 다른 사람한테 보여줄 것도 아니고.. 푼 문제 수에 집착해서 쉬운 문제만 푸는 것은 별 도움이 안된다.
사이트에 업로드 규칙
- 문제 사이트마다 다른 서브 카테고리를 만들고, 그 안에 문제별로 문서를 만든다.
- 문제별 문서에 코드를 올릴때는 Import Inliner를 적용하기 이전 상태의 코드를 올린다. 대신 사용한 teflib 함수들에 대해서는 따로 링크를 걸어둔다.
- 이렇게 코드를 올리면 바로 코드를 복붙해서 제출할 수는 없다는 단점이 있지만, 공통 라이브러리 로직과 문제별 로직을 구분해서 보기 쉽고, 그래서 깔끔하고 이해도 쉽다. 바로 코드를 복붙해서 제출할 수는 없다는 점도 생각해보면 장점인거 같기도 하다.
- 다이아몬드 이상의 문제에는 코드를 붙이지 않는다. 어차피 그 정도의 문제를 고민할 레벨의 사람들에게는 코드는 있으나 없으나 별 문제가 안된다.
관련 페이지
참고 사이트
- 요즘에는 PS/알고리즘과 관련된 블로그가 엄청 많아졌다. 초보자들 부터 초고수까지 다양한 사람들이 블로그를 운영하고 있다. 발견한 곳들중 도움이 되는 곳들은 여기에 모아두자.
-
- 다양한 토픽들이 체계적으로 정리가 잘 되어있다. 웬만한 책보다 훌륭하다.
-
- 역시 다양한 토픽에 대해서 외부 자료 / 코드 / 관련 문제가 체계적으로 잘 정리되어있다
-
- 기본적인 알고리즘은 대충 다 정리되어있다.
-
- 정수론 특화
-
- 블로그 강좌에 맞춰서 만들어 놓은 문제집도 있다 - https://www.acmicpc.net/workbook/by/rkm0959
-
ps/start.txt · 마지막으로 수정됨: 2023/08/04 15:21 저자 teferi
토론