문자열은 의상 입은 배열이야

"문자열은 그냥 문자 배열이야. 유일한 반전은, Python 에선 그걸 편집할 수 없다는 거고 — 그 규칙 하나가 유명한 성능 함정을 만들어."

밑은 배열이야

배열에 대해 배운 모든 게 문자열에 적용돼, 문자열이 문자 배열 이니까. s[3] 은 O(1) 주소 산술. 문자 찾으려 문자열 훑기는 O(n). s[2:7] 슬라이싱은 그 범위를 복사, O(k). "첫 모음 찾기" 나 "이 단어 뒤집기" 를 배열 문제로 대하면, 이 트랙 전체의 기법이 곧장 넘어와.

유일한 반전: 불변성

여기서 문자열이 리스트랑 갈라져: Python 에서 문자열은 불변 (immutable) 이야. 문자를 제자리에서 못 바꿔 — s[0] = 'x' 는 에러야. 어떤 "수정" 이든 사실 완전히 새 문자열을 지어. 무해하게 들리는데 반복문 안에서 하면, 입문 Python 에서 가장 유명한 성능 자폭이 돼.

+= 함정

반복해서 이어붙여 큰 문자열 짓는 걸 생각해: 반복문 안 result += piece. 문자열이 불변이라, 각 += 는 기존 문자열을 못 늘려 — 완전히 새 문자열을 할당하고 지금까지 모든 문자를 복사해. 길이 k 문자열에 append 하면 k 문자를 복사해. 그걸 n 번 하면 1 + 2 + 3 + … + n ≈ n²/2 문자를 복사한 거야. 네 순진한 반복문이 몰래 O(n²) 이야.

고침은 한 줄 반사신경이야: 조각을 리스트에 모으고 (append 가 O(1)), "".join(pieces) 로 한 번에 녹여, 그게 O(n) 한 패스야. 같은 출력, O(n²) 대신 O(n). 이게 배열 렌즈가 값을 하는 거야 — 넌 이미 리스트-append 가 싸고 문자열-재건이 안 싼 걸 알잖아.

문자열은 불변 문자 배열이야. 인덱싱과 슬라이싱은 배열처럼 행동해; 근데 모든 '편집' 은 문자열 전체를 다시 지어. 리스트 + join 으로 지어, 반복문 안 += 로는 절대.

대체 왜 불변으로 만들어?

불변성은 벌이 아니야 — 진짜 걸 사줘. 문자열이 절대 안 바뀌어서, 해시 가능 (hashable) 할 수 있어 (그래서 dict 키나 set 멤버가 될 수 있어 — 다음 트랙 전체가 이거에 달림). 누가 밑에서 바꿀까 걱정 없이 프로그램 부분들 사이에 공유해도 안전해. 그리고 똑같은 문자열은 인터닝 될 수 있어 (한 번 저장하고 재사용). += 함정은 그 값이고; 해시 가능하고 공유 가능하고 안전한 문자열이 그걸로 산 거야.

피파의 고백

내 첫 텍스트 조립 함수는 수천 행을 도는 반복문에서 report += line 으로 거대 리포트를 지었어. 테스트 파일에선 즉시였고; 진짜 export 에선 꼬박 1분을 기었어. 아빠가 한 번 보고: "매 줄마다 리포트 전체를 다시 짓고 있잖아." 리스트랑 끝에 join 하나로 바꾸니 — 1분이 밀리초가 됐어. 어떤 강의보다 단단히 박혔어: 불변성은 제곱이 되기 전까진 안 보여.

Code

+= 함정과 join 고침·python

# 문자열은 읽기엔 배열처럼 행동해...
s = "pippa"
print(s[0], s[-1], s[1:4])   # 'p' 'a' 'ipp' — 인덱스 & 슬라이스, 배열처럼
print("p" in s)              # True — 근데 이건 O(n) 훑기

# ...근데 불변이라, '편집' 은 전체를 다시 지어.
# s[0] = "P"   # TypeError: 'str' object does not support item assignment

# 함정: 반복문 안 += 는 O(n^2), 매 단계가 앞 문자 전부를 복사하니까.
def build_bad(n):
    out = ""
    for i in range(n):
        out += str(i)          # 매번 새 문자열 할당 -> 총 O(n^2)
    return out

# 고침: 리스트에 모으고 (O(1) append), 한 번 join (O(n)).
def build_good(n):
    parts = []
    for i in range(n):
        parts.append(str(i))   # 리스트 append 는 분할 상환 O(1)
    return "".join(parts)      # O(n) 한 번 녹이기

assert build_bad(1000) == build_good(1000)   # 같은 답
# 같은 출력. build_bad 는 O(n^2); build_good 은 O(n). 큰 n 에선 격차가 잔혹해.

Exercise

n 개 행마다 csv += row + "\n" 로 CSV 문자열을 짓는 함수를 받았어. 진짜 복잡도랑 왜인지 말하고, O(n) 으로 다시 써. 그다음 답해: 문자열은 왜 dict 키로 쓸 수 있는데 리스트는 못 써?

Hint

+= 버전은 O(n²) — 매 append 가 커지는 문자열 전체를 복사. 행을 리스트에 모아 '\n'.join 해. 문자열은 불변 (해시 가능) 이라 dict 키가 되고; 리스트는 가변이라 해시 불가능해.

밑은 배열이야

유일한 반전: 불변성

+= 함정

대체 왜 불변으로 만들어?

피파의 고백

Code

External links

Exercise

Progress

댓글 0