SW 문제해결 기본 - String

모든 내용은 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AV184ApaI7kCFAZN 에 저작권이 있습니다. 

 

1. String

1) 문자 표현

메모리는 숫자만 저장할 수 있기에 각 문자에 대응되는 숫자를 정한 후 메모리에 저장하는 방법을 사용한다. 예를 들어, 000000은 'a'이다. 미국에서 네트워크가 발전하며 지역별로 상이한 코드체계로 인해 정보를 다르게 해석하게 되는 문제가 발생했다. 이를 해결하기 위해 ASCII(American Standard Code for Information Intercharge)라는 표준안을 사용했다.

 아스키는 문자 인코딩의 표준이다. 7bit 인코딩으로 128문자를 표현한다. A는 65이다. 확장 아스키 코드도 존재한다. 부가적인 문자를 128개 추가할 수 있게 한다. 1Byte(8bit)를 모두 사용해서 추가적인 문자를 표현할 수 있다. 표준 아스키와 다르게 다른 프로그램이나 컴퓨터 사이 교환이 불가하며, 프로그램이나 컴퓨터/프린터가 그것을 해석할 수 있게 설계되어야 해독이 가능하다.

 유니코드는 다국어 처리를 위한 표준이다. 국가별 코드체계가 만들어지자 ASCII 코드가 만들어진 상황과 같은 상황이 국가간에 발생하여 만들어졌다.

 유니코드는 UCS-2, UCS-4라는, 유니코드를 저장하는 변수의 크기를 정의하는 Character Set이 있다. 파일을 인식시 어느 것인지 구분해야 했다. 유니코드 인코딩 용으로 생긴 것이 UTF(Unicode Transformation Format)이다. 유니코드의 바이트 인코딩 순서를 결정한다. 우리가 자주 사용하는 UTF-8은 최소 8비트, 최대 32비트까지 사용 가능하다.

 

2)  String의 분류

문자열 - 고정 길이

             - 가변 길이 - 길이 조절 (Java)

                                 - 구분자 (C)

 

Java.lang.String 클래스에는 기본적인 객체 메타 데이터 외에도 네 가지 필드가 있다. hash, count(길이), offset(String 데이터의 시작점), value(실제 String 배열에 대한 참조). 즉, 자바에서는 String이 String 길이를 관리하는 가변 길이 구조를 가진다. 자바는  String 데이터를 저장, 처리해주는 클래스를 제공한다. String을 저장할 때 UTF-16, 2byte로 저장한다. "홍길동"은 3byte이다.

 

(C는 String 마칠 때 '\0' 반드시 넣어야 한다. 아스키 코드로 저장한다. "홍길동"은 6byte이다.)

 

2. 패턴 매칭

1) String 교체하기

브루트포스 알고리즘

본문 String을 처음부터 끝까지 차례대로 순회하며 패턴 내의 문자를 일일이 비교한다.

최악의 경우, 시간 복잡도는 O(mn)이 된다. 

길이가 10000인 String에서 길이 80의 패턴을 찾을 때, 최악의 경우 10000*80 = 800000번의 비교가 발생한다.

 

 

 

KMP 알고리즘

불일치가 발생한 text String의 앞 부분에 어떤 문자가 있는지 알고 있으므로, 앞 부분과 다시 비교하지 않고 매칭을 진행한다.

시간복잡도 : O(n)

 

 

 

 

보이어-무어 알고리즘

오른쪽에서 왼쪽으로 비교한다. 대부분의 상용 소프트웨어에서 채택하고 있다. 왜냐면 보통 뒷 부분에서 틀리기 때문이다!

패턴의 오른쪽 끝에 있는 문자가 불일치하고, 이 문자가 패턴 내에 존재하지 않는 경우, 이동거리는 패턴의 길이 만큼이 된다.

텍스트를 모두 보지 않아도 검색 가능

시간복잡도 : 최악의 경우 O(mn), 일반적으로는 O(n)보다 적다.