[알고리즘 기초] 03_문자열(string) / Python

[알고리즘 기초] 03_문자열(string) / Python

[알고리즘 기초] 03_문자열(string) / Python

1. 문자의 표현 - 컴퓨터에서의 문자의 표현

1) 코드체계

• 각 문자에 대해서 대응되는 숫자를 정해 놓고 이것을 메모리에 저장하는 방법을 사용
• 영어의 경우 대소문자 합쳐서 52자 이므로 6비트(64 가지)면 모두 표현 할 수 있다. 이를 코드체계라고 한다.

000000 -> 'a'
000001 -> 'b'

 

• 네트워크가 발전하면서 서로간의 정보를 주고 받을 때 정보를 다르게 해석한다는 문제가 발생
  • 지역별 코드 체계가 다르기 때문

 

2) ASCII Code

 

• 표준안을 목적으로 1967년, 미국에서 ASCII(American Standard Code for Information Interchange)라는 문자 인코딩 표준이 제정됨.
• ASCII는 7bit 인코딩으로 128문자를 표현하며 33개의 출력 불가능한 제어 문자들과 공백을 비롯한 95개의 출력 가능한 문자들로 이루어져 있다.

bit : 0 또는 1 나타내는 단위
byte : 영문자 1개를 나타내는 단위 (8bit - ASCII + Parity)

 

 

3) 확장아스키

표준문자 이외의 악센트 문자, 특수 문자, 특수 기호 등 부가적인 문자를 128개 추가할 수 있게 하는 부호

• 확장 아스키는 Byte내의 8bit를 모두 사용하믕로써 추가적인 문자를 표현할 수 있다.
• 확장 아스키는 여러가지 다양한 문장 할당할 수 있도록 하기 때문에 서로 다른 프로그램이나 컴퓨터사이에 교환되지 못한다.
• 확장 아스키는 프로그램이나 컴퓨터 또는 프린터가 그것을 해독할 수 있도록 설계되어 있어야만 올바른 해독이 가능하다.

 

 

4) 유니코드

국가간 정보를 주고 받게 되면서 자국의 코드체계를 타국가가 가지고 있지 않으면 정보를 잘못 해석 할 수 밖에 없는 문제를 해결하기 위해 다국어 처리를 위해 마련한 표준

• 유니코드는 Character Set으로 분류된다.
  • USC-2 (Universal Character Set 2)
  • USC-4 (Universal Character Set 4)
• 유니코드를 저장하는 변수의 크기를 정의, 바이트 순서에 대해 표준화 하지 못함
• 파일 인식 시, USC-2와 USC-4를 구분해서 다르게 구현해야 하는 문제가 발생하여 외부 인코딩이 필요하게 됨

 

• big-endian

0001 0010 / 0011 0100 -> ox12 ox34

 

• little-endian

0001 0010 / 0011 0100 -> ox34 ox12 (큰수 먼저 표기)

 

 

 

5) 유니코드 인코딩 (UTF : Unicode Transformation Format)

• UTF-8 (in web)
  • MIN : 8bit
  • MAX : 32bit(1byte *4)

• UTF-16 (in windows, java)
  • MIN : 16bit
  • MAX : 32bit(2 byte *2)

• UTF-32 (in unix)
  • MIN : 32bit
  • MAX : 32bit(4 byte *1)

 

 

 

6) Python 인코딩

 

• 2.X 버전 - ASCII - #--coidng: utf-8 -- (첫 줄에 명시)
• 3.X 버전 - 유니코드 UTF-8 (생략가능)
• 다른 인코딩 방식으로 처리 시 첫 줄에 작성하는 위 항목에 원하는 인코딩 방식을 지정해주면 됨

 

 

 

 

2. 문자열

1) Python에서의 문자열 처리

• char 타입 없음
• 텍스트 데이터의 취급방법이 통일되어 있음

• 문자열 기호
  • ' ', " ", ''' ''', """ """
  • +:연결
  • *:반복
• 문자열은 시퀀스 자료형으로 분류되고, 시퀀스 자료형에서 사용할 수 있는 인덱싱, 슬라이싱 연산들을 사용할 수 있음
• 문자열은 튜플과 같이 요소값을 변경 할 수 없음(immutable)
  • 문자열을 인덱스로 접근하여 변경이 불가능하다

 

 

2) 문자열 뒤집기

• 자기 문자열에서 뒤집는 방법, 새로운 빈 문자열을 만들어서 소스의 뒤에서부터 읽어서 쓰는 방법이 있다.
• Python은 Reverse 함수 혹은 slice notation을 이용하여 구하면 된다.

 

 

3) 문자열 비교

• 파이썬에서는 == 연산자와 is 연산자를 제공한다.
  • == 연산자는 내부적으로 특수 메서드 __eq__()를 호출

 

 

4) 문자열 숫자를 정수로 변환하기

• 파이썬에서는 숫자와 문자변환 함수를 제공한다.

ex) int("123"), float("3.14"), str(123,) repr(123)

 

 

 

5) 문자열 교체하기

• chr(--int--) => int 에 해당하는 ASCII Code 문자를 출력
• ord(--str--) => str 에 해당하는 ASCII Code Number를 출력

 

 

 

 

3. 패턴 매칭

1) 고지식한 알고리즘(Brute Force)

• 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일히 비교하는 방식으로 동작
• 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨

 

 

2) KMP 알고리즘

• 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행
• 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화 함
  • next[m] : 불일치가 발생했을 경우 이동할 다음 위치
• 시간 복잡도 : O(M+N)

 

 

3) 보이어-무어 알고리즘

• 오른쪽에서 왼쪽으로 비교 ( 문자열의 뒤에서 앞으로 비교 )
• 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘
• 패턴 오른쪽 끝에 있는 문자가 불일치 하고 이 문자가 패턴 내에 존재하지 않는 경우, 패턴의 길이 만큼 이동하여 시행한다.
• 오른쪽 끝에 있는 문자가 불일치 하고 이 문자가 패턴 내에 존재할 경우, 패턴에 일치하는 문자로 이동하여 시행한다.

 

 

4) 문자열 매칭 알고리즘 비교

• 찾고자 하는 문자열 패턴의 길이 m, 총 문자열 길이 n
• 고지식한 패턴 검색 알고리즘: 수해이간 O(mc)
• 카프-라빈 알고리즘: 수행시간 O(n)
• KMP 알고리즘: 수행시간 O(n)
• 보이어-무어 알고리즘: 일반적으로 O(n)보다 시간이 덜 든다.
  
  

 

 

5) 문자열 압축

• Run-length encoding 알고리즘
  • 같은 값이 몇번 반복되는가를 나타냄으로써 압축
  • 이미지 파일 포멧 중 BMP 파일포맷의 압축 방법