대엉코딩

0. string

- character의 sequence 이다.

- string의 예시로서는

  -> HTML문서

  -> DNA sequence

  -> 등등....매우 많다.

- 아스키코드, binary alphabets, DNA alphabets( {A,C,G,T} )

- 보통 TEXT에서 PATTERN과 일치하는 SubString(그 위치)를 찾는 문제가 많다.

- 검색엔진, 텍스트 에디터, 생물학적 조사 등 을 할 때 주요하게 사용된다. 

1. 개요

- 가장 간단하고 naive한 방식의 알고리즘 이다.

- 텍스트의 위치 가능한 모든 자리에 PATTERN을 매치시켜 비교과정을 거친다.

- 비교과정 중 완벽하게 매치하거나 남은 텍스트의 길이보다 패턴의 길이가 더 길어질 경우 비교를 멈춘다.

2. 시간복잡도

- 워낙 간단해서 의사코드를 기재하진 않았지만 복잡도 분석을 해보면

- 텍스트의 길이 (m) 패턴의 길이 (n)  이라 하면 시간 복잡도는 O(n*m)

- m의 위치 가능한 모든 자리에서 n을 비교하기 때문에 최악의 경우 O(n*m) 이다.

- 최악의 경우 중 간단한 예시를 들어보면

 -> TEXT: AAAA........B

 -> PATTERN: AAAB

-이경우 불일치가 패턴의 맨 끝에 존재하므로 패턴을 매번 비교할 때 마다 끝문자가 나타날 때 까지 비교를 해야한다.

3. 장점 및 단점

- 장점은 알고리즘 자체가 매우 간단하다.

- 패턴이나 텍스트를 Preprocessing하는 과정이 없다.

- 알파벳의 범위가 좁을 경우 (위의 경우 처럼 a,b) 성능이 떨어진다.

- 영어나 한국어처럼 글자의 종류가 매우 많을경우는 나름 brute-force도 성능이 괜찮을 수 있다.

https://www.acmicpc.net/problem/1316

- 문자열을 탐색 하는 문제입니다.

- 딱히 어려운 문제는 아니고

- 단어를 차례대로 문자 하나씩 탐색 하던중 같은 문자를 받다가 다른 문자가 처음 나타날 경우

- 그 단어가 이전에 들어온적이 있는 단어 인지 처음 들어온 단어 인지만 체크 하면 되는 문제입니다.

- 들어왔던 단어들을 벡터에 저장해 두었다가 새로운 문자가 들어올 때 그 벡터들을 탐색하여 들어온적이 있었는지를

-확인 하였습니다.

<코드>

https://www.acmicpc.net/problem/1120

- 문제 파악은 어렵지 않고

- 입력 출력 조건을 읽어보면

- 처음 든 생각은 a(더 짧은 문자열) 을 b(긴 문자열) 의 어느 위치에 위치를 시켜야 같은 문자를 가지는 값이

- max가 되는지를 파악한 후 그 값을 a문자열의 길이에서 빼주면 최소로 다른 글자가 나옵니다.

(어차피 위치 시킨이후 다른 문자들은 b와 완벽하게 같은 글자들을 넣어주면 되므로 신경 쓸 필요가 없습니다.)

<코드>

https://www.acmicpc.net/problem/10757

- 아무 생각 없이 long long (int)로 제출 했다가 당연히 안됨!.

- 하나의 자료형에 담을 수 없는 큰 수 들의 입력, 출력은 더더욱 더!

- 문자열을 이용하자!

- 이런 생각 후의 단계는 단순 했습니다.

- 1단계 : 자릿수 맞추기

      3200 + 10 을 그냥 문자열에 넣고 계산하면

      3 2 0 0

  +  1 0   

      이 되므로 원하는 결과가 안나온다.

      자릿수를 맞춰 앞쪽에 0을 넣어 0 0 1 0 을 만들어주자.

- 2단계 : 더한후 carry값을 계산하자!

- 두 단계만 생각하면 간단했습니다.

/수정/ 

생각해 봤는데 오류가 있는데 이게 결과를 int배열로 잡아서

출력에는 이상이 없지만 result[0]은 carry 처리가 제대로 되지 않습니다.

즉 이 문제에서는 상관없이 결과는 잘 나오지만 다른 i번째의 출력과 일관성이 없는거 같습니다.

잘 못 짠듯...... 뒤집어서 다 계산하고 캐리까지 계산하고 마지막에 뒤집을까....