Lazy 검색 결과

해당 글 2건
regex lazy quantifier에 대해 간단하게 알아봅시다.

regex에서 lazy quantifier가 어떻게 동작하는지 간단하게 알아봅시다. 먼저 R{2,} 뒤에 ?를 붙였습니다. 이 때 ?는 lazy quantifier 역할을 합니다. match as few character as possible이라 되어 있는데요. 가능한 적은 문자를 match 한다고 되어 있습니다. greedy 속성과는 정반대임을 알 수 있습니다. RRRRR, RR이 있는데요. R{2,}에 매치되는데, 가능한 적은 문자로 매치되는 패턴은 어떤 것인가요? RRRRR에서는 RR입니다. 그 다음에 RRR에서 RR이 또 매치가 됩니다. 그렇기 때문에, RRRRR에서는 2개가 match 되고, RRR에서는 RR 하나만 매치가 됩니다. 이는, 패턴 R{2,}와는 다른데요. 요래 입력하고 패턴을 찾아..
REGEX 2022. 10. 29. 00:53
세그먼트 트리 구조에서 lazy propagation을 적용하는 코드를 뜯어봅시다.

안녕하세요. 백준에서 활동하고 있는 chogahui05입니다. 저번 lazy propagation 시간에는 변환을 합성한다는 관점에서 접근했습니다. 이번에는, 그것을 알고 있다는 전제 하에서, 어떻게 코드를 이해하셔야 할 지 설명을 해 보도록 하겠습니다. 이 글에 있는 코드는 설명을 위해 중요 부분만 간략화 한 것임을 참고해 주시면 감사하겠습니다. 먼저, lazy는 누적된 변환이라는 것이 핵심이라고 했습니다. 그러면, 누적된 변환이라는 개념이 왜 나왔는지부터 생각해 봅시다. 그 전에, 연속된 k개의 구간을 어떻게 처리할 것인지부터 고민해 봅시다. 보통의 segment Tree에서 연속된 k개의 구간을 업데이트 하는 연산은 klogn번만큼 수행이 됩니다. 문제는, 이런 쿼리가 50만개 들어왔다고 생각해 봅..
자료알고/자료구조 2020. 3. 31. 00:34