Lua 테이블 처리 기법
Lua는 높은 효율성을 자랑하며, 이 중 테이블 구현이 큰 역할을 했습니다. Lua의 테이블은 배열과 해시 맵의 두 가지 기능을 동시에 제공하므로, 이러한 특성을 고려하여 배열로 사용할 때도 효율 감소를 최소화하도록 설계되었습니다.
Lua는 테이블을 배열 부분과 해시 부분으로 나눕니다. 숫자 키는 일반적으로 배열 부분에 저장되며, 초기화되지 않은 키 값은 nil로 설 ...
8월 19일 07:46에 게시됨
문자열 해시와 선분 트리, 트리 DP, 비트셋을 활용한 정사각형 탐색 문제 풀이
문제 1: 동적 문자열 집합에서 고유 문자열 수 계산
여러 개의 동일 길이 문자열이 주어지고, 각 쿼리마다 특정 문자열의 부분 구간을 같은 문자로 덮어쓴 후, 전체 집합 내 서로 다른 문자열의 개수를 출력해야 한다.
해결 핵심은 다음과 같다:
각 문자열의 해시 값을 효율적으로 갱신하기 위해 게으른 전파(lazy propagation)가 가능한 선분 트리를 사용한다.
해시 ...
7월 20일 20:48에 게시됨