문자열 (String)

---

목차

1. 코드 체계
2. 문자열
3. Python 문자열 입력과 기본 처리
4. 문자열 연산
5. 패턴 매칭
6. 고지식한 패턴 검색 (Brute Force)
7. KMP 알고리즘
8. 보이어-무어 알고리즘
9. 문자열 암호화
10. 문자열 압축

1. 코드 체계

코드체계는 문자에 대응되는 숫자를 정한 것이다.

• 바이트(Byte): 주소가 부여되는 최소 단위
• 컴퓨터는 문자를 그대로 저장하는 것이 아니라 숫자로 바꾸어 저장한다.

코드 체계의 개선

지역마다 서로 다른 코드체계를 사용하면 같은 숫자를 서로 다른 문자로 해석할 수 있다. 이런 혼동을 줄이기 위 해 표준 문자 인코딩 체계가 만들어졌다.

ASCII

• 미국에서 제정된 문자 인코딩 표준이다.
• 7-bit 인코딩으로 128 개의 문자를 표현한다.
• 영문 대소문자, 숫자, 기호, 제어 문자 등을 포함한다.

# 문자와 코드 값 확인 예시
print(ord('A')) # 65
print(chr(65)) # A

확장 아스키 (Extended ASCII)

• 표준 ASCII 문자 외에 악센트 문자, 도형 문자, 특수 문자 등을 128 개 추가한 형태이다.
• 1Byte의 8-bit 를 모두 사용하여 최대 256 개의 값을 표현한다.
• 확장 영역은 프로그램이나 환경에 따라 문자 대응이 다를 수 있다.

유니코드 (Unicode)

• 다국어 처리를 위한 표준 코드체계이다.
• 각 나라의 문자 체계가 달라 생기는 호환 문제를 줄이기 위해 만들어졌다.
• 이모지(Emoji)도 유니코드 문자에 포함된다.

자료에서는 유니코드 Character Set 으로 UCS-2 와 UCS-4를 소개하고, 저장 변수의 크기와 바이트 순서 문제 를 함께 설명한다.

바이트 단위 저장 순서 (Endian)

• Big-endian: 상위 바이트(MSB)를 가장 낮은 주소에 저장한다.
• Little-endian: 하위 바이트(LSB)를 가장 낮은 주소에 저장한다.

핵심 같은 여러 바이트 데이터라도 저장 순서를 서로 다르게 해석하면 전혀 다른 값으로 읽힐 수 있다.

유니코드 인코딩 (UTF)

방식	자료의 설명	크기
UTF-8	Web 에서 주로 사용	MIN 8-bit, MAX 32-bit (1Byte × 4)
UTF-16	Windows, Java	MIN 16-bit, MAX 32-bit (2Byte × 2)
UTF-32	Unix	32-bit (4Byte × 1)

• UTF-8 은 필요한 문자 크기에 따라 $1 \sim 4$ 바이트를 사용한다.
• 인코딩이 다르면 같은 파일을 읽어도 문자가 깨질 수 있다.
• 웹 문서에서는
  처럼 문자 인코딩을 지정할 수 있다.

줄바꿈 문자와 OS

• Windows: CR(13) + LF(10)
• Unix / macOS: LF(10)

강의자료는 PyCharm 등의 상태 표시줄에서 파일 인코딩과 줄바꿈 형식을 확인할 수 있음을 예로 든다.

Python 인코딩

• 자료에서는 Python 2.x에서 UTF-8 사용 시 코드 첫 줄에 인코딩 주석이 필요하다고 설명한다.

-- coding: utf-8 --

• Python 3.x 에서는 UTF-8 방식이 기본이므로 표시를 생략할 수 있다고 설명한다.

2. 문자열

문자열(String)은 문자들이 순서대로 나열된 데이터이다. 문장, 단어, 기호 등의 텍스트를 표현하거나 처리할 때사용한다.

문자열의 분류

1. Length-Controlled 문자열
   • 문자열의 길이 정보를 함께 저장하고, 그 길이만큼 문자 데이터를 읽는 방식이다.
   • Java, Python, 네트워크 패킷 등에 사용된다.
2. Delimited 문자열
   • 문자열 끝을 나타내는 특정 구분자(Delimiter)가 나올 때까지 문자열로 인식한다.
   • C 언어에서는 널 문자(null, ‘W0’)를 사용한다.

언어별 문자열 표현

언어	자료의 핵심 설명
C	문자 배열로 문자열을 저장하며 문자열 끝에 널 문자가 필 요하다. strlen(), strcpy(), strcmp() 등의 함수 사용
Java	String 클래스로 문자열을 다루고 +, length(), replace(), split(), substring() 등을 제공
Python3	유니코드 기반 문자열을 사용하며 인덱싱•슬라이싱•문자열 메 서드를 사용할 수 있다. 문자열은 immutable

Python 에서 문자열

• 문자열은 데이터의 순서가 구분되는 시퀀스 자료형이다.
• 인덱싱과 슬라이싱을 사용할 수 있다.
• replace(), split(), isalpha(), find() 등의 메서드를 제공한다.
• 문자열은 튜플처럼 요소 값을 직접 변경할 수 없는 immutable 자료형이다.

s = "abc"
print(s[1]) # b
print(s[0:2]) # ab
# s[0] = "A" # TypeError: 문자열 요소는 직접 변경할 수 없음

문자열 생성과 기본 연산

• 작은따옴표(’‘), 큰따옴표(““), 삼중따옴표(”’ ““,”“” “““)로 문자열을 만들 수 있다.
• +: 문자열 연결(Concatenation)
• : 문자열 반복

print('ab' + 'c') # abc
print('ab' * 3) # ababab

3. Python 문자열 입력과 기본 처리

문자열 한 줄 입력

text = input()

input()은 입력된 한 줄을 문자열로 읽어 들인다. 공백이 포함되어 있어도 한 줄 전체가 문자열에 저장된다.

문자를 리스트로 입력

text = list(input())
# 예: Hello -> ['H', 'e', 'l', 'l', 'o']

각 문자를 리스트의 원소로 따로 다루고 싶을 때 사용할 수 있다.

여러 줄 문자열 입력

N = int(input())
arr = [input() for _ in range(N)]

각 줄을 문자열 한 개로 저장한다.

문자 단위 2 차원 리스트

N = int(input())
arr = [list(input()) for _ in range(N)]

$\mathrm{N} \times \mathrm{N}$ 문자 지도처럼 각 칸의 문자를 직접 확인하거나 변경해야 할 때 사용하기 편하다.

특정 문자 존재 여부 확인

text = input()
for char in text:
    if char == "Z":
        print("Z 가 존재합니다.")

4. 문자열 연산

문자열 뒤집기
문자열을 역순으로 재정의하는 것이다.

s = "Reverse this strings"
s = s[::-1]
print(s) # sgnirts siht esreveR

리스트로 변환한 뒤 reverse()를 사용하고 다시 문자열로 합칠 수도 있다.

s = "abcd"
s = list(s)
s.reverse()
s = "".join(s)
print(s) # dcba

회문 (Palindrome)

기러기, 토마토처럼 앞에서 읽어도 뒤에서 읽어도 같은 문자열을 회문이라고 한다. 문자열 길이의 절반만 비교하면 된다.

def is_palindrome(txt):
    # 앞쪽 절반만 확인
    for i in range(len(txt) // 2):
        # 앞쪽 문자와 뒤쪽 문자가 다르면 회문이 아님
        if txt[i] != txt[len(txt) - 1 - i]:
            return False
    return True

인덱스 핵심 앞쪽 $\mathrm{txt}[\mathrm{i}]$ 와 뒤쪽 $\mathrm{txt}[\operatorname{len}(\mathrm{txt})-1$ - i]를 짝지어 비교한다.

문자열 비교: == 와 is

• == : 두 값(value)이 같은지 비교한다. 내부적으로 eq()를 호출한다.
• is : 두 변수가 같은 객체(identity), 즉 같은 메모리 객체를 가리키는지 비교한다.

str1 = "abc"
str2 = "abc"
str4 = str1
str5 = str1[:2] + "c"
print(str1 = str2) # True
print(str1 is str2) # 실행 환경에 따라 같은 객체로 재사용 될 수 있음
print(str4 == str5) # True
print(str4 is str5) # False 가 될 수 있음

주의 문자열 내용 비교에는 ==를 사용한다. is 는 값 비교용이 아니라 객체 동일성 비교용이다.

사전 순서 비교
문자열은 <, > 연산자로 사전 순서를 비교할 수 있으며 자료에서는 유니코드 값을 기준으로 비교한다고 설명한다.

def my_strcmp(str1, str2):
    if str1 < str2:
        return -1
    elif str1 > str2:
        return 1

else:
return 0

• 예: ‘Apple’ < ‘apple’ 은 True
• 예: ‘Zebra’ < ‘apple’ 은 True

문자열 ↔︎ 숫자 변환

# 문자열 -> 숫자
a = int("123")
b = float("3.14")
c = int("A0", 16) # 문자열 A0를 16진법으로 해석
# 숫자 -> 문자열
d = str(123)
e = str(3.14)

5. 패턴 매칭

패턴 매칭은 본문 문자열(Text) 안에서 찾고 싶은 문자열(Pattern)이 존재하는지, 존재한다면 어느 위치에 있는지 찾는 과정이다.

기호	의미
T 또는 t	본문 문자열(Text)
P 또는 p	찾을 패턴(Pattern)
N	본문 길이
M	패턴 길이

강의자료에서는 고지식한 패턴 검색, KMP, 보이어-무어 알고리즘을 비교한다.

6. 고지식한 패턴 검색 (Brute Force)

본문 문자열의 처음부터 끝까지 순회하면서 패턴의 문자들을 일일이 비교하는 가장 단순한 방법이다.

• 문자가 같으면 본문 인덱스 i 와 패턴 인덱스 j 를 함께 증가시킨다.
• 실패하면 비교를 시작했던 위치의 다음 칸으로 돌아가고, 패턴 인덱스는 처음부터 다시 시작한다.

def brute_force(p, t):
    # p: 찾을 패턴, t: 본문 문자열
    i = 0
    j = 0
    M = len(p)
    N = len(t)
    while j < M and i < N:
        if t[i] != p[j]:
            # 시작 위치의 다음 칸으로 이동하도록 복원
            i = i - j
            j = -1
        i += 1
        j += 1
    if j = m:
        return i - M # 검색 성공: 시작 인덱스
    else:
        return -1 # 검색 실패

시간 복잡도

• 최악의 경우 본문의 거의 모든 위치에서 패턴 전체를 비교할 수 있다.
• 본문 길이 N, 패턴 길이 M 일 때 O(MN)

자료의 예에서는 길이 10,000 인 문자열에서 길이 80 인 패턴을 찾는 경우 최악 약 800,000 번 비교가 필요할수 있다고 설명한다.

7. KMP 알고리즘

KMP 는 Knuth, Morris, Pratt 세 사람의 이름에서 유래한 문자열 검색 알고리즘이다.

핵심 아이디어

• 패턴의 각 위치에서 매칭에 실패했을 때 돌아갈 위치를 미리 계산한다.
• 불일치가 발생하기 전까지 이미 일치했던 정보를 버리지 않고 재사용한다.
• 따라서 불일치한 앞부분을 다시 처음부터 비교하는 일을 줄일 수 있다.

LPS 배열

LPS 는 Longest Prefix which is also Suffix 의 약자로, 패턴의 각 위치까지 보았을 때 접두사(prefix)와 접미사 (suffix)가 같은 최대 길이를 저장한다. 자료에서는 next 또는 pi 배열이라고도 설명한다.

패턴: a b c d a b c e f
LPS : 0 0 0 0 1 2 3 0 0

역할 비교 중 실패했을 때 패턴 인덱스를 무조건 0 으로 되돌리지 않고, LPS 값을 이용해 다음 비교 위치를 정한 다.

시간 복잡도

• 패턴 전처리: $\mathrm{O}(\mathrm{M})$
• 본문 검색: $\mathrm{O}(\mathrm{N})$
• 전체: $\mathrm{O}(\mathrm{M}+\mathrm{N})$
• 자료에서는 패턴 길이 M 이 매우 짧고 고정된 경우 평균적으로 $\Theta(\mathrm{N})$ 에 가깝다고 설명한다.

8. 보이어-무어 알고리즘

보이어-무어(Boyer-Moore)는 실제 문자열 검색 소프트웨어에서도 채택되는 빠른 검색 알고리즘으로 소개된다.

핵심 특징

• 패턴의 오른쪽 끝에서부터 비교한다.
• 오른쪽 끝에서 불일치가 발생하면 한 칸씩만 이동하지 않고 여러 칸을 한 번에 건너뒬 수 있다.

불일치 문자 휴리스틱 (Bad-Character Heuristic)

패턴의 오른쪽 끝 문자와 본문의 문자가 불일치할 때, 그 본문 문자가 패턴 안에 존재하는지 확인해서 이동 거리 를 정한다.

• 불일치 문자가 패턴에 없으면 패턴 길이만큼 크게 이동할 수 있다.
• 패턴 안에 있으면 해당 문자가 오른쪽 끝과 일치하도록 패턴을 이동한다.

Skip 배열 예

자료의 ‘rithm’ 패턴 예에서는 다음과 같은 이동 값을 사용한다.

문자	r	i	t	h	m	그외
Skip	4	3	2	1	0	5

문자열 매칭 알고리즘 비교

알고리즘	비교 방향 / 핵심	자료의 복잡도 설명
Brute Force	왼쪽부터 단순 비교, 실패 시 한 칸 이동	O(MN)
KMP	LPS 배열로 이미 비교한 정보를 재사용	$\mathrm{O}(\mathrm{M}+\mathrm{N})$
Boyer-Moore	오른쪽부터 비교, Skip 으로 크게 이동	최악 $\mathrm{O}(\mathrm{MN})$ 가능, 일반적으로 비교 횟 수가 적음

기억법 Brute Force = 처음부터 / KMP = 앞에서 얻은 정보 재사용 / Boyer-Moore = 오른쪽부터 보고 크게 점프

9. 문자열 암호화

시저 암호 (Caesar Cipher)
율리우스 시저가 사용했다고 알려진 암호 방식으로, 평문에 사용된 알파벳을 일정한 문자 수만큼 평행 이동시켜암호화한다.

키 = 1
A -> B
B -> C
C -> D
...

자료의 예에서는 “SAVE PRIVATE RYAN”을 일정한 키 값으로 이동한 암호문을 보여준다. 암호화할 때 사용한이동 값을 키(Key)라고 한다.

전사 공격 (Brute Force Attack)
시저 암호는 가능한 키의 수가 적기 때문에 키 값을 하나씩 모두 적용해 원문이 나오는지 확인할 수 있다.

키 1 2 적용
키 25 적용

• 가능한 모든 경우를 하나씩 시도하는 방식이 전사 공격이다.

단일 치환 암호
각 알파벳 하나를 다른 고정된 알파벳 하나로 대응시키는 방식이다. 시저 암호처럼 일정한 거리로 이동하는 것이아니라 문자 변환표 자체를 사용한다.

A -> Q
B -> H
C -> C
D -> B
...

가능한 키의 수
알파벳 26 개를 서로 다르게 배치하는 경우의 수는 다음과 같다.

26 x 25 × 24 × ... × 1 = 26!

자료에서는 초당 매우 많은 키를 적용하더라도 전부 확인하는 데 매우 긴 시간이 걸린다고 설명한다.
빈도 분석
전사 공격이 어려워도 언어의 통계적 특성을 활용할 수 있다. 영어 평문에서 자주 나오는 문자를 추정해 암호문에서 빈도가 높은 문자와 대응시키는 방식이다.

• 자료에서는 영어에서 많이 쓰이는 글자 예로 E, T, A 등을 든다.

1. 문자열 압축

Run-Length Encoding (RLE)
같은 값이 몇 번 반복되는지를 나타내는 방식이다. 반복이 많은 데이터에서 효과적이다.
원본: ABBBBBBBBA
압축: A1B8A1

• 자료에서는 이미지 파일 포맷 중 BMP 의 압축 방식 중 하나로 사용된다고 설명한다.

허프만 코딩 (Huffman Coding)

대표적인 압축 방법으로, 등장 빈도에 따라 서로 다른 길이의 코드를 부여한다.

• 자주 나오는 문자 -> 짧은 코드
• 드물게 나오는 문자 -> 긴 코드

결과적으로 전체 데이터의 평균 코드 길이를 줄이는 방식이다.

자주 쓰는 Python 코드 모음

문자열 뒤집기
s[::-1]
회문 간단 확인
s == s[::-1]
문자열 찾기
s.find("abc")
문자열 치환
s.replace("a", "b")
문자열 분리
s.split()
리스트 → 문자열
"".join(arr)
문자 코드
ord('A')
chr(65)
문자열 → 숫자
int("123")
float("3.14")
int("A0", 16)
숫자 → 문자열
str(123)

복습 체크

• UTF-8은 가변 길이 인코딩이며 자료에서는 최대 4Byte 까지 사용한다고 설명한다.
• 문자열은 ordered 시퀀스 자료형이며 immutable 이다.
• find()는 특정 문자가 처음 등장하는 인덱스를 찾는 데 사용할 수 있다.
• count()는 특정 문자열/문자의 등장 횟수를 셀 때 사용할 수 있다.
• upper()는 문자열을 대문자로 변환한 새 문자열을 반환한다.
• strip()은 문자열의 앞뒤 공백을 제거한다.
• join()은 리스트 등의 문자열 원소를 특정 구분자로 이어 붙인다.