문자열 조작(String Manipulation)이란 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다. 문자열 조작은 정보처리, 통신, 프로그래밍 시스템등의 분야에서 많이 사용된다.

String의 주요 특징

• 문자열 슬라이싱이라는 매우 편리하고 내부적으로 매우 빠르게 동작하는 기능을 제공
• 슬라이싱을 통해 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 탐색
• 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리

슬라이싱을 기준으로 한 파이썬 문자열 처리 실행 시간은 아래와 같다.

알고리즘	싱행시간	슬라이싱을 1로 했을 때의 비율
슬라이싱	0.499ms	1
리스트 reverse()	2.46ms	5
reversed() + join()	2.49ms	6
for 반복	5.5ms	12
while 반복	9.4ms	21
재귀	24.3ms	54

파이썬이 제공하는 문자 조작 기능 중 슬라이싱이 속도가 가장 빠르면서 편리하다.

알아두면 좋을 것들(소소한 테크닉)

• collections.defaultdict(list) : key 값이 없어도 바로 .append() 메소드 사용 가능
• ’‘.join(list) : 한 letter씩 있는 list를 한 단어로 합침
• sorted(aa, key=lambda x: (x1, x2)) : 정렬을 할 때 첫 번째로 x1순으로 정렬을 하고, 후순으로 x2순으로 정렬을 한다. 2가지 이상의 조건이 필요할 때 사용하면 좋을 듯(sorted() 메소드의 key값)

정렬 알고리즘과 팀소트(소소한 이야기)

정렬 알고리즘 중 가장 인기있는 알고리즘은 병합 정렬(Merge Sort)이다. 컴퓨터과학 역사상 최고의 천재라고 불리는 존 폰 노이만이 설계했다. 대부분은 퀵 정렬이 더 빠르지만 데이터에 따라 편차가 큰 반면, 병합 정렬은 일정하게 O(nlogn)의 안정적인 성능을 보이며, 무엇보다 안정 정렬(Stable Sort)이라는 점에서 많이 선호되고 있다.

파이썬의 정렬(Sorted())은 팀소트(Temsort)를 사용한다. C로 구현한 알고리즘으로 창안자는 팀 피터스의 이름을 따서 만들었다. 실제 데이터는 대부분 이미 정렬되어 있을 것이다.라는 가정을 하고 실제 데이터에서 고성능을 낼 수 있도록 설계했다.

• 팀소트는 개별적인 단일 알고리즘이 아니라 삽입 정렬과 병합 정렬을 휴리스틱하게 적절히 조합해 사용하는 알고리즘
• 대부분의 정렬은 파이썬의 정렬 함수가 가장 빠르다.

아래는 대표적인 알고리즘의 시간 복잡도이다.

알고리즘	최선	평균	최악
퀵 정렬	O(nlogn)	O(nlogn)	O(n^2)
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)
팀소트	O(n)	O(nlogn)	O(nlogn)