0616

벌써 6월 중순이라닛

백준: キャピタリゼーション

문제편식하기 (사실 문제까지도 아님.)
근데 이거 하다가 궁금한게 생겼습니다

re.sub와 str.replace의 차이

• re.sub는 파이썬 레벨에서 파이썬 레벨에서 정규 표현식을 사용하여 매칭 후 치환

• str.replace는 c 레벨에서 단순 문자열만을 직접 치환

• 만약 메서드 안 쓰고 풀려면?

def replace(s, old, new):  
	res = ""  
	i = 0  
	while i < len(s):  
		if s[i:i+len(old)] == old:  
			res += new  
			i += len(old)  
		else:  
			res += s[i]  
			i += 1  
	return res

정규표현식

• 정규표현식은 왜 느린가?

  • 정규표현식은 두 가지 알고리즘으로 구현 될 수 있음
  • nfa 기반 백트래킹 알고리즘 또는 (python의 기본 모듈인 re에서 해당 방식 차용)
  • 모든 상태를 하나로 미리 계산해놓고 dfa로 구현하는법

• dfa는 뭐고 nfa는 뭔가?

  • dfa (Deterministic Finite Automaton)
    • 어떤 상태든 입력 기호에 대해 정확히 하나의 전이만 가능
  • nfa (Non-deterministic Finite Automaton)
    • 하나의 상태에서 같은 입력에 대해 여러 전이가 가능

• 왜 일부언어의 정규표현식에선 dfa를 쓰는가?

  • nfa는 여러 경로를 동시에 추적해야하는 반면
    dfa는 하나의 상태만 보기때문에 메모리 사용량이 일정하고 예측 가능함
  • 또한 nfa는 백트래킹 기반이라 ReDoS가 일어날 수 있음
    (ReDoS란 말그대로 정규표현식을 활용했을 때 일어날 수 있는 보안 문제)
  • 그래서 Go나 Rust같은 언어는 dfa를 씀.
    왜? 두 언어는 보통 서버나 시스템에서 주로 사용되는 언어기 때문에

• 그럼 왜 파이썬은 dfa를 안 쓰고 nfa 기반 백트래킹으로 정규식을 만든건가?

  • 파이썬은 모든 것이 객체로 선언되기에 메모리 사용량이 많은 언어임
    다른 c++나 rust는 개발자가 직접 메모리를 해제할 수 있지만
    파이썬은 가비지 컬렉션을 사용하기에 사용자가 직접 메모리를 제어하기 어려움
  • 근데 dfa는 복잡한 패턴에선 상태 수가 기하급수적으로 증가함
  • 고로 백트래킹으로 정규표현식을 구현한 것 같다 (추측)

• 그럼 파이썬에서 정규표현식 쓸 때는 무조건 다 느리냐?

  • 입력값이 하나일때는 똑같겠지만,
    테스트 케이스가 여러개일때는 re.complie()을 써서
    미리 정규표현식으로 매칭 후 치환하면 그나마 좀 낫겠죵
  • https://news.ycombinator.com/item?id=12132348

맺음말

오늘은 이력서 정리하면서 좀 쉬었는데
옛날 과제물 보고 스스로 놀랐어욤
어케 만들었지 ㅋㅋㅋㅋ
블렌더 재밌었는데......