일상경험 [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번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net DP문제의 정수였다고 본다. 모든 상황을 고려하여 DP를 제대로 작성할 수 있는지에 따라 풀이가 갈렸고, 수많은 테스트 케이스를 토대로 겨우 풀 수 있었다. 찾기 problem : https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m www.acmicpc.net KMP 그 자체를 구현하는 문제. KMP는 알고리즘의 직관성과 구현 방법에 거리가 있는 것 같다. 까먹어서.. 다시 이 문제를 풀라고 하면 풀지 못할 것 같다. CLASS 7부터 본격적으로 KMP로 사람을 조지는 문제가 여럿 나오는 것 같으니, 체계적으로 복습하는 게 중요해보인다! 영화 수집 / 공장 problem : https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net problem 2 : https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 세그먼트 트리를 확장하는 문제 중에 제일 창의적의고 재밌었던 것 같다. 세그먼트 트리 아닌 척하는 문제들? 이 문제들에서 시행착오를 겪으면서 제일 실력이 느는 게 느껴졌다. 공유하기 게시글 관리 마젠티노's 저작자표시 비영리 동일조건 '일상경험' 카테고리의 다른 글 어느 날, 월요일의 일상 (0) 2024.11.11 [2023년 정산특집] 백준 Class 7 달성 / Platinum 1 달성 (0) 2023.12.31 [2023년 정산특집] 백준 Platinum 100문제 채우기 (1) 2023.12.21 프로그래머스 순위가 올라갔습니다 (0) 2023.04.06 새해 복 많이 받으세요! (0) 2023.01.01 Contents 당신이 좋아할만한 콘텐츠 어느 날, 월요일의 일상 2024.11.11 [2023년 정산특집] 백준 Class 7 달성 / Platinum 1 달성 2023.12.31 [2023년 정산특집] 백준 Platinum 100문제 채우기 2023.12.21 프로그래머스 순위가 올라갔습니다 2023.04.06 댓글 1 + 이전 댓글 더보기