[2024 동계 모각코] 5주차 계획
5주차 계획
개요
5주차(1. 29~ 2. 4)의 계획입니다.
- 16장 비트마스크
- 문제: GRADUATION
- 17장 부분 합
- 문제: CHRISTMAS
- 18장 선형 자료 구조
- 문제: JOSEPHUS
- 19장 큐와 스택, 데크
- 문제: BRACKETS2
- 문제: ITES
- 20장 문자열
- 문제: NAMING
- 문제: PALINDROMIZE
- 문제: JAEHASAFE
- 문제: HABIT
16장 비트마스크
문제: GRADUATION
어떤 것을 고르고/고르지 않는 문제를 풀 때, 우리는 이를 bool 집합으로 변환할 수 있습니다.
bool 집합 간에 연산을 해야 할 때, bool 집합의 원소를 비트 하나로 인식할 수 있습니다.
따라서 크기가 적당하다면 bool 집합을 integer나 long으로 변환이 가능합니다. 이를 비트마스킹이라고 합니다.
DP와 비트마스크가 결합된 문제를 풀어봅시다.
17장 부분 합
문제: CHRISTMAS
부분 합을 이해해보는 문제입니다.
문제는 부분 합과 모듈로 연산이 섞인 문제에 약간의 DP가 첨가된 문제입니다.
부분 합 문제를 풀면서 느낀 생각으로는, 문제를 수식으로 명확히 정의해서 이를 쉽게 변형하여 풀어야한다고 생각했습니다.
18장 선형 자료 구조
문제: JOSEPHUS
요세푸스 문제를 쉽게 풀기 위해 Circular Linked list의 원리를 이용하는 문제입니다.
이 자료구조의 원리를 이용하면 $O(n^2)$시간 안에 빠르게 풀 수 있습니다만,
세그먼트 트리를 이용하면 $O(n \log n)$시간 안에 푸는 게 가능합니다.
19장 큐와 스택, 데크
문제: BRACKETS2
스택의 성질을 이용해서 푸는 Bracket Match Problem입니다.
문제: ITES
연속 부분 수열의 합이 특정 값 K가 되는 경우의 수를 찾는 문제입니다.
투 포인터와 큐를 이용해 풀 수 있는 문제입니다.
조금 더 빠르게 구현하려면, 큐를 사용하지 않고, (push/pop 오버헤드가 존재합니다.)
큐의 head와 tail부분의 수를 알고 있으면 공식에 따라 다음 수를 만들 수 있으니,
결과적으로 큐를 사용하지 않을 수 있습니다.
20장 문자열
서론
문자열 알고리즘이 이리 어려운지는 처음 알았다. 특히 KMP 알고리즘은 몇 번 복습해야할것 같다.
문제: NAMING
문자열 $s$의 접미사와 접두사가 같을 때의 모든 길이를 출력하시오. KMP알고리즘의 failure()를 이용한다.
문제: PALINDROMIZE
문자열 $s$가 주어지면 $s[i…]$중 가장 길이가 긴 palindrome 수열을 찾는 알고리즘입니다.
문자열 $s$와 $s$를 뒤집은 $s’$를 이용해 $haystack$과 $needle$간의 매칭으로 문제를 바꿔버릴 수 있습니다.
문제를 바꿨으니 KMP알고리즘을 이용해 $O(n)$시간 안에 동작하는 알고리즘을 만듭니다.
문제: JAEHASAFE
문자열을 찾는 문제이나, 이번에는 회전 문자열(Circular string)에 대해 풀어봅시다.
문제: HABIT
문자열 문제를 풀기 위한 접미사 배열(suffix array)을 배우고 이것에 대한 장점.
접미사 배열을 만드는 알고리즘 중 그나마 쉬운 맨버-마이어스 알고리즘을 배우고
접미사 배열을 이용해서 겹치는 $substring$의 최대 길이를 구합니다.