풀캠정글러

친구에게서 이런 말을 들었다. 핀토스는 엄청 빡센데 그래도 하려면 할만한가 싶다가, 후반부에 지옥도가 펼쳐진다. 정글이 끝나기까지 아직 2달 반정도의 시간이 남아있지만, 뭔가를 따로 할 여유는 이제 그리 없다는 의미일 것이다. 원래 목표는 1월 중순쯤에 P1, 2월 나만의무기 시작 전까지 D5를 다는 것이었다. 하지만 지금 생각해보면 늦어도 1월 첫째주 안에는 D5까지 가서 알건 다 알고 내려와 스킬적인 부분을 키워야 하겠다는 생각이 든다. 요즘은 지식을 늘고있지만 그걸 다루는 테크닉은 한참 못미치는 것을 느끼고 있다. 지금은 새로운 심화 알고리즘들을 배우는 단계이다 보니 문제해결력이 없어도 알고리즘만 이해하면 기초문제를 쑥쑥 풀 수 있지만, 응용과 조합을 요구하는 다이아 문제들은 거의 손도 못대겠다. ..

12.16 ~ 12.22 KMP 이분 매칭 문제와 DFS 솔루션 최대 유량 문제와 BFS 솔루션 (에드몬드 카프) 뫼비우스 함수 6주차가 애매하게 어려워서 자꾸 그쪽만 파다보니 PS를 할 시간이 없었다면, 이번주는 정반대였다. 원래 뭔가 막히는 부분이 있으면 낭비하게 되는 시간이 싫어서 잠시 옆에 치워두고 다른 걸 손대는 편이다. 개인적으론 7주차 과제인 웹 서버가 지금까지중에 제일 어렵고 깊게 들어갔다고 생각하는데, 그래서인지 매일같이 알고리즘에 자꾸 손이 가서 오히려 문제를 푸는 시간이 더 많아지는 선순환? 같은 일이 벌어져서 결국 풀다보니 40문제 넘게 풀었다. 이번주에 다룬 주제는 크게 KMP, 이분매칭, 최대유량 이 셋인데, 이분 매칭은 세그먼트 트리처럼 일단 베이스만 이해해도 테크닉적인 부분만..

KMP 정복완료와 동시에 티어랑 클래스 업 다이아 달고 CLASS 8이면 지엽적인 고난도 알고리즘들 외에 범용적으로 쓰이는건 다 아는 셈이라는데 12월안에 P2, 1월중순에 P1까지 가면 2월에 나만의무기 시작하기 전에 다이아를 달수있지 않을?까? 그리고 텐서플로우로 그럴듯한 딥러닝 프로젝트를 개발해서 보이저엑스에 지원하는 행복한 미래...

12.09 ~ 12.15 세그먼트 트리의 구현과 응용 ??? : 이번주 과제는 지난주보다 구현량이 없어보이니 알고리즘도 꾸준히 해야지 6주차의 원래 목표는 세그먼트 트리 + KMP였는데 세그먼트 트리만 익히고 KMP는 보지도 못했다. 간단하게 이론을 볼땐 구간합을 저장한다길래 아 뭔가 아무튼 지엽적인 문제에 솔루션을 제공하는 자료구조겠구나 싶었는데, 정작 파보니 구간 합뿐만 아니라 정말 모든 종류의 'sub'에 대한 데이터를 다룰 수 있었다. 일단 세그먼트 트리를 구현하는법을 배워도 노드에 무엇을 저장할지, 어떤 노드 취합함수로 쿼리를 해결할지가 다 다르니까 한두문제 푸는걸로는 응용력에 도움이 안돼서 가능한 많은 문제를 풀어봤다. 세그먼트 트리 문제를 풀면서 느낀게, 단기간에 많은 개념을 머리속에 때려넣..

페르마의 소정리를 이용한 큰 수의 모듈러 연산 역원 찾기 (combination 계산에 이용) https://uneducatedjungler.tistory.com/120 밀러 라빈 알고리즘을 이용한 소수 판별 (큰 수에서는 확률적, 1e15 이하 작은 수에서는 확정적 판별 가능) https://uneducatedjungler.tistory.com/121 폴라드 로 알고리즘을 이용한 소인수분해 (유사난수와의 비교로 구한 랜덤인수를 밀러 라빈으로 소수 판별) https://uneducatedjungler.tistory.com/133 오일러 피 함수 (소인수분해를 이용한 빠른 계산) class 6에 정수론 관련 문제가 좀 있어 이쪽을 파다보니 조금 깊게 들어간 것 같다. 풀 수 있는 P1~D4 문제가 몇개 생..

1~4주차에 정글에서 한 방법이 나랑 잘 맞는것 같아서 비슷한걸 만들어봤다. 5주차 C언어 들어가기 전 수요일에 시간남을때 만든 건데, 연두색은 그새 푼 문제들이다. 코치님은 상중하 난이도를 제시하셨는데, 당연하지만 내가 몰라서 푸는 문제에 난이도를 매길 능력은 없어서 solved.ac 티어를 참고했다. 우측 태그의 개념들은 일단 무슨얘기인지 설명만 훑어봤는데, 이해하는데 필요할 것 같은 양의 문제수를 표에 넣었다. 좀 보면 알것같은 개념들은 조금만 넣고, 개론만 봐도 살짝 빡세보이거나 개념을 알아도 응용력이 필요해보이는 세그먼트트리 같은건 문제를 좀 많이 넣는 식. 이해하고 나면 위의 리스트 외에도 풀 수 있는 문제들이 생길텐데 그쪽도 풀어볼 계획이다. class 6 이상은 구현력은 일단 있다는 전제 ..

플래티넘 4주컷 이게 되네... 그냥 아무튼 플래가 찍고싶어서 4주동안 배운걸로 풀 수 있는 문제만 붙잡고 계속 풀다보니 구멍이 많다. 위상, 좌표, 수치해석, 정수론같이 전공빨을 좀 타는 문제는 플래 위로도 잘 풀리는데, 코딩 스킬이 필요한 자료구조나 구현 태그쪽 문제는 골드 5만 돼도 턱 막히고 1시간 이상씩 걸리는 것 같다. 아예 모르는 개념도 많고. 알고리즘 문제는 특정한 알고리즘을 모르면 못푸는 '모르면 맞아야지'식 문제가 많으니 앞으로는 구멍을 메우는 식으로 풀어봐야겠다. 일단 목표는 월마다 1~2티어씩 올려서 정글이 끝날때쯤 다이아를 다는것이다. 코치님도 알고리즘은 꾸준히 풀라 하셨으니 가능한 한 위까지 올라가봐야겠다. 수학과에서 배운걸 본격적으로 쓰는 문제들은 플~다에 있기도 하고, 그쪽을..

수학과 지식을 이용해서 분수에 맞지 않는(?) 문제 몇개에 매달린 덕분에 뜬금없이 골드가 되었다... 학부시절에 정수론 이산수학같이 PS에 크리티컬한 과목들이 C였는데 그래도 막상 쓸때가 되니 다 기억이 나긴 하는게 신기하다. 자료구조나 알고리즘 이해해서 쓰는 문제는 실~골 정도가 내 수준에 맞는 문제 난이도이고 플래부터 좀 버거운 것 같다. 다음주차는 문제 수가 이번주보다 적다고 한다. 혹시 시간이 남으면 이전 주차의 플래 문제들을 풀면서 봉우리에서 하산하는 절차를 밟아보자.