Skip to content

Latest commit

 

History

History
232 lines (146 loc) · 9.56 KB

String.md

File metadata and controls

232 lines (146 loc) · 9.56 KB
Raw

String

Algorithm 기본 파트 3. 문자열 (string)

1. 문자열?

  • 컴퓨터에서 문자표현

    메모리는 숫자만 저장할 수 있으므로 (이진수) 각 문자에 대응되는 숫자를 정해놓고 이것을 메모리에 저장하는 방식으로 사용

    즉, 각 문자를 코드 형식으로 맞춰서 표현하는 방법인 코드체계를 사용한다.

    단, 코드 체계를 각각의 지역 / 단체에서 자신만의 코드를 사용하게 되면 타 지역 / 단체와 통신시 정보 불일치가 일어난다.

    실제로 미국에서 네트워크가 통용되기 전 각 지역별 코드체계를 사용하다가 정보가 달리 해석되는 문제가 발생했다.

    이런 불상사를 막기 위해 표준안으로 ASCII 코드라는 문자 인코딩 표준이 제정되었다.

    ASCII는 7bit 인코딩으로 128문자를 표현하며 33개의 출력 불가능한 제어 문자와 95개의 출력가능한 문자로 나타난다.

    ※ 참고
ASCII 0번: '\0' # null 문자
ASCII 65번: 대문자 A
ASCII 97번: 소문자 a
1bit: 정보를 나타내는 단위
1Byte(8bit): 영문자 1개를 나타내는 단위

! 참고로 1Byte(8bit)가 영문자 1개를 나타내는 단위인데 ASCII는 7bit를 사용한다.
나머지 1bit는 패리티 비트로 해당 문자의 오류를 검출하기 위해 사용한다.

    위 ASCII 코드는 표준으로 제정되어 세계적으로 사용되고 있다. 단, 1비트를 정보표현에 사용하지 않으므로 이를 사용하는 확장 ASCII 코드가 생겼다.(단, 현재 거의 사용되지 않음)

  • Unicode

    위 ASCII 코드는 영문자를 표현하기 위해 사용된다. 하지만 컴퓨터는 미국 뿐만 아니라 다른 나라에서도 사용하므로 각 국가에서 자신의 언어를 표현하기 위해 코드체계를 만들기 시작했다.

    우리나라도 한글 코드체계로 조합형 / 완성형 두가지를 가지고 있었다.

    때문에 미국에 처음에 겪은 문제처럼 정보 교환에서 정보의 불일치가 발생했다. 이를 해결하기 위해 Unicode를 만들어 다국어 처리를 위한 표준을 마련했다.

    Unicode는 2Byte를 사용하여 65536개의 문자를 표현할 수 있다.

    참고로 한글은 11000여개를 유니코드에서 배정받았다.

    Unicode도 다시 Character Set으로 분류된다. (UCS-2, UCS-4)

    위 Character Set은 유니코드를 저장하는 변수의 크기를 정의한다. 단, 바이트 순서를 표준화하지 못하여 파일을 인식할 때 UCS-2와 UCS-4인지 인식하고 각 경우를 구분하여 모두 다르게 구현해야 하는 불편함이 발생했다.

    2바이트가 Unicode를 표현하지만 컴퓨터에 따라 바이트를 달리 읽을 수 있다.

    때문에 Unicode의 외부 인코딩이 필요하게 되었다.

    Unicode Transformation Format (UTF-8)

    유니코드 인코딩 방식

    UTF-8: Web에서 주로 사용, MIN: 8bit / MAX: 32bit (1 Byte * 4)

    UTF-16: windows와 Java에서 주로 사용, MIN: 16bit / MAX: 32bit (2 Byte * 2)

    UTF-32: Unix에서 주로 사용, MIN: 32bit / MAX: 32bit (4 Byte * 1)

  • Endian

    • Big-endian

      바이트 순서가 큰 단위가 앞으로 나타남

      보통 대형 컴퓨터

    • Little-endian

      바이트 순서가 작은 단위가 앞으로 나타남

      보통 일반 컴퓨터

    ex) 0x1234

    Big-endian: 0001 0010 0011 0100

    Little-endian: 0011 0100 0001 0010

  • 문자열의 분류

    문자열에는 고정길이 방식과 가변길이 방식으로 나뉜다.

    가변길이 방식은length controlled(Java에서 문자열 방식)와 delimited(c 언어에서 문자열)로 나뉜다.

  • Python에서 String

    python에서는 문자열을 >, <를 통해서 비교가 가능하다.

    python 3는 각 문자를 unicode를 사용하여 비교를 하기 때문에 사전순으로 비교한다.

    python 문자열 비교 참고

  • 참고! 컴퓨터에서 수를 표현하는 방법

    • 정수

      컴퓨터에서 정수는 이진수를 통해 표현한다. 맨 앞자리를 통해 부호와 절대치를 표현한다.

      3bit가 있다고 가정

양수 : 000 - 0 / 001 - 1 / 010 - 2 / 011 - 3
음수 : 100 - -0 / 101 - -1 / 110 - -2 / 111 - -3

      단, 위 경우 0을 표현하는 방법이 2가지가 된다 (000 / 100)

      때문에 2의 보수로 수를 표현하는 방법이 등장했다.

      2의 보수는 1의 보수에서 1을 더한 값이다.

      3bit에서 2의 보수로 표현하는 방법

      정수 1의 보수 2의 보수
      0 111 / 000 000
      1 001 001
      2 010 010
      3 011 011
      -1 110 111
      -2 101 110
      -3 100 101
      -4 표현불가 100

      이렇게 1의 보수가 아닌 2의 보수를 쓰게 되면 0을 2번 표현하는 문제를 해결할 수 있으며 음수 하나를 더 표현할 수 있다.

      또한, 나타나는 또다른 장점으로는 음수 계산이 가능하게 된다!

2. 패턴 매칭

  • Brute force

    말그대로 모든 경우의 수를 탐색하면서 해당 패턴이 있는지 확인해보는 방법

    이 경우 모든 위치에서 패턴을 비교해야하므로 O(MN)의 복잡도가 나타난다.

  • KMP Algorithm

    불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으면 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 매칭을 할 수 있다.

    따라서, 패턴을 전처리하여 잘못된 시작을 최소화할 수 있다.(패턴의 각 위치에 대해 매칭 실패시 돌아갈 곳의 index를 저장)

    시간복잡도는 O(n) (검사하려는 문자열의 길이만큼)

    • 핵심 아이디어

      1. 접두사(prefix)와 접미사(suffix)

      2. 접두사와 접미사를 이용하여 중복을 피하도록 건너뛸 거리를 구한 pi 배열

    private int[] getPi(String pettern){
     String [] temp = pettern.split("");
     int len = pettern.length(), j = 0;
     int [] pi = new int[len];
     for (int i = 1; i < len; i++){
          while (j > 0 && !temp[i].equals(temp[j])) j = pi[j - 1];
          if (temp[i].equals(temp[j])) pi[i] = ++j;
     }
     return pi;
}

public List kmp(String str, String pettern){
     String [] s = str.split("");
     String [] p = pettern.split("");
     int [] pi = getPi(pettern);
     int n = s.length, m = p.length, j = 0;
     ArrayList<Integer> answer = new ArrayList<>();
     for (int i = 0; i < n; i++){
          while(j > 0 && !s[i].equals(p[j])) j = pi[j-1];
          if (s[i].equals(p[j])){
               if (j == m - 1) {
                    answer.add(i - m + 1);
                    j = pi[j];
               }
               else j++;
          }
     }
     return answer;
}

    KMP 참고

  • Boyer-Moore Algorithm

    오른쪽에서 왼쪽으로 비교

    대부분의 사용 소프트웨어에서 사용하는 알고리즘으로 패턴에 오른쪽 끝에 있는 문자가 불일치하고 해당 문자가 패턴에 존재하지 않으면 패턴의 길이만큼 이동하는 문자열 매칭 알고리즘

    시간복잡도는 O(mn)

  • Karp-Rabin Algorithm

    패턴을 해쉬화 하여 해쉬으로 만들고 찾고자하는 문자열에서 자리수 만큼 해쉬값을 계산한다. 이를 비교하여 문자열을 찾는 알고리즘

    이때 매번 index를 이동하면서 찾는 것이 아니라 이전에 구한 해쉬값을 이용하여 복잡도를 줄인 방식

3. 문자열 암호화

  • 시저 암호 (Caesar cipher)

    평문에서 사용되고 있는 알파벳을 일정한 문자 수만큼 평행이동하여 암호화를 한다.

  • 문자 변환표를 이용한 암호화 (단일 치환 암호)

    복호화를 위해서는 모든 키의 조합이 필요하다. 때문에 단순한 카이사르 암호화보다 훨씬 복잡하고 강력한 암호화 기법이다.

    위의 경우 알파벳을 암호화한다면 26!만큼의 키의 수가 나타난다.

  • bit 열 암호화

    • 배타적 논리합 (exclusive-or) 연산 사용

      key값을 설정하고 해당 key 와 암호화할 평문을 xor 연산으로 암호화하는 방식 같은 키로 복호화까지 가능!

4. 문자열 압축

  • Run-Length encoding Algorithm

    주로 bmp 파일의 압축 방법으로 사용되는 알고리즘

    같은 값이 몇 번 반복되는가를 나타냄으로써 압축하는 방식

  • Huffman coding Algorithm