[2023년 정산특집] CLASS 6 완전정복

드디어 졸업!

 

지난 번에 이어, 이번에는 CLASS 6을 마무리하는 시간을 가졌다. 연말내에 끝내겠다는 목표를 잡고 하다 보니 조금은 시간을 과투자했던 것 같지만... 그래도 어디인가! 뿌듯한건 어쩔 수 없나보다.

 

CLASS 6부터 딱 플래티넘 구간 초입의 문제를 제공하고, 이런 종류의 개념들을 테스트하고자 했던 것 같다. 복습 겸, 문제들을 떠올릴 겸 한 번 정리해보기로 했다.

 

 

• 고급 DP
  • 비트마스킹 이용하기
  • 다양한 조건 분기 활용
  • 중간에서 만나기
  • 트리 DP
• KMP 기초(KMP는 아직도 약한 것 같다...)
• 세그먼트 트리 기초
  • 이분 탐색 결과 활용
• SCC와 파생 문제
  • 2-SAT 문제
• Convex Hull
• 단절점 / 단절선
• 희소 배열 이용 문제
  • LCA(최소 공통 조상 문제)
• 분할 정복 문제
  • 분할 정복을 이용한 거듭제곱 형태
  • 분할 정복을 통한 히스토그램 면적 구하기 형태
• 라인스위핑
• 위상 정렬
• 오일러 피 함수 (RSA와 뤼카 알고리즘에서 다시 다루어 보아야 할 내용이다!)
• 포함 배제의 원리
• 페르마의 소정리
  • 이항 계수 문제
• 트리와 트라이

 

...정도로 정리할 수 있고, 이들을 제대로 이해하고 적용할 수 있다면 문제를 풀 수 있겠다.

이 중 개인적으로 가장 어려웠던 문제/흥미로웠던 문들을 하나씩 꼽고, 복습하는 시간을 가져 보려 한다.

 

---

 

습격자 초라기

 

problem : https://www.acmicpc.net/problem/1006

1006번: 습격자 초라기

 

DP문제의 정수였다고 본다. 모든 상황을 고려하여 DP를 제대로 작성할 수 있는지에 따라 풀이가 갈렸고, 수많은 테스트 케이스를 토대로 겨우 풀 수 있었다.

 

 

 

찾기

 

problem : https://www.acmicpc.net/problem/1786

1786번: 찾기

 

KMP 그 자체를 구현하는 문제. KMP는 알고리즘의 직관성과 구현 방법에 거리가 있는 것 같다. 까먹어서.. 다시 이 문제를 풀라고 하면 풀지 못할 것 같다. CLASS 7부터 본격적으로 KMP로 사람을 조지는 문제가 여럿 나오는 것 같으니, 체계적으로 복습하는 게 중요해보인다!

 

 

 

 

영화 수집 / 공장

 

problem : https://www.acmicpc.net/problem/3653

3653번: 영화 수집

 

problem 2 : https://www.acmicpc.net/problem/7578

7578번: 공장

 

세그먼트 트리를 확장하는 문제 중에 제일 창의적의고 재밌었던 것 같다. 세그먼트 트리 아닌 척하는 문제들? 이 문제들에서 시행착오를 겪으면서 제일 실력이 느는 게 느껴졌다.