Monday, March 28, 2011

binary 데이터 핸들링

요즘 binary 데이터를 처리할 일이 많이 생긴다. sff 파일도 그렇고 ab1파일도 그렇고. 단 한번도  binary 파일을 처리해보지 못한 나에겐 공포의 영역. 해서 함 해보기로 한다. 까짓거 사람이 만든건데 뭐 별거 있겠어.


우선은 누가 짜놓은 ab1 파일 파싱하는 프로그램을 봤는데 struct 모듈을 사용한다.

http://www.thegreatgoodplace.com/tt/study/316 (길원이형 블로그를 보게 될 줄이야...)


헌데 잘 이해가 안된다. 우선 쉬운 블로그를 찾아보자.

http://seorenn.blogspot.com/2011/02/python-struct-padding.html


음.. 때려 맞추자면 pack이 binary로 만들어 주는거고 unpack이 binary로 된걸 python 형식의 string으로 바꿔주는듯.. padding이란 말이 나오는데 뭐 % operator에 숫자 붙인 것처럼 데이터가 특정 사이즈만큼 안될 때 0 bit로 넣어주는거 같고.. 음.. 생각해보니 binary 라는게 그냥 데이터가 틈(?) 없이 계속 나열되어 있는 것이겠군. 그렇다면 파일 format 그러니까 몇바이트까지가 하나의 데이터고 또 몇바이트까지가 하나의 데이터고 이런 정해진 포멧만 알고 특정 바이트까지로 구분해서 읽으면 그게 데이터가 되겠다는 생각이 든다. 아닐수 있지만.. 여튼


이제 struct 모듈의 full 설명을 볼 차례다.
http://docs.python.org/library/struct.html
pack이랑 unpack은 위에서 말한거랑 같고 pack_into랑 unpack_from 이 있는데 이는 특정 buffer에서 offset 값서 부터 읽거나 쓰는거 같은거..  
byte order, size, and alignment 아.. 요것이 중요한거 같은데. format 의 첫 character가 @,=,<,>,!(!는 poor souls을 위한 거란다. 나인가 보다 네트워크는 big인걸 까먹는 나) 중에 하나 선택하는건데 이게 byte order, size, alignment를 뭘로 할거냐. 그러니까 native 라 함은 하드웨어 특유의 방식 byte order 같은 경우에는 intel cpu의 경우 little endian 이다 뭐 이런거 뜻하는 걸거고(확인하려면 sys.byteorder를 사용하란다).. size는 링크 안에 표가 있다. 아.. 근데 alignment가 뭔지 모르겠다.. 뭐지 이거.. 아. 예제를 보아하니 format이 다른 연속의 데이터가 있을때 이를 맞춰주는거를 alignment라고 하는거 같은데 정확하지 않다.




첫 url 링크의 프로그램을 보면 ab1 파일의 binary format과 프로그램이 있는데 struct를 알고보면 굉장히 프로그램이 단순다하는 걸 알게 된다. 다만 전부 unpack의 format이 big-endian 인데 이는 ab1 파일 자체가 그렇게 되어 있기 때문에.


아 그리고 전에 포스팅 했던 bit 연산자도 다시 볼 필요가 있겠다.
http://graphy21.blogspot.com/2010/10/bit.html

Saturday, March 26, 2011

iphone 개발 수업 3주차-2

3/26
<UITable view>
같은 형태의 데이터를 list 형태로 반복해서 출력. MVC로 구성
섹션: 리스트에서 그룹
섹션 헤더 : 섹션의 이름
섹션 푸터 : 섹션 마지막의 메뉴같은것(?)
셀 : 그룹을 이루는 하나 하나의 항목; contentView


UITableView : MVC 에서 view의 역할


UITableViewDataSource : MVC 에서 model의 역할, 데이터 관리
-(NSInteger)numberOfSectionInTableView:(UITableView *)TableView ; 섹션(group)의 수를 return(섹션이 없을때 return 값은 1)
-(NSInteger)tableView:(UITableView *)TableView numberOfRowsInSection:(NSInteger*)section;
-(UITableViewCell *)tableView:(UITableView *)TableView cellForRowAtIndexPath:(NSIndexPath*)indexPath
UITableViewDataSource 에서는 위의 3 메소드를 반드시 정의해줘야 한다.


UITableViewDelegate : controller의 역할, 이벤트 관리


MainWindow 객체 안에 UITableView가 있고 MainWindow화면을 관리하는 UIViewController 객체가 UITableView 의 내용을 알기 위해 UITableViewDataSource의 메소드들을 호출하는데 먼저 numberOfSectionInTableView를 호출해서 섹션의 갯수를 알아냄, 그 다음에 tableView를 호출해서 섹션하나에 몇개의 셀이 있는지 알아냄(섹션 갯수만큼 호출). 그 뒤 UITableViewDataSource 를 호출해서 셀의 내용을 받는다(한 화면에 보여줄 셀 갯수만큼 호출).  
---------------------------------------------------------------------------------------------------


< Navigation based application in SimpleHumanResource Architecture (SimpleHumanResource 라는 프로젝트로 Navigation based application 의 architecture를 알아보자) >
1.SimpleHumanResourceAppDelegate 안에 시스템 이벤트 처리 메소드와 아래의 것들이 있다.
UIwindow *window;  MainWindow관리(title, frame등)
UINavigationController *navigationController; MainWindow내용 전환(UIViewController들을 전환)


2.RootViewController ; 첫화면으로 이는 UIViewController, UITableViewDataSource(내용관리를 위한 프로토콜), UITableViewDelegate(이벤트를 위한 프로토콜)를 상속받은 UITableViewController을 상속받음. 즉 화면 내용, UITableView의 내용, 이벤트를 다 관리(이것은 첫화면을 UITableView를 나타내기 위해서 UITableView와 관련된 것들을 상속 받았는데, 그게 싫다면 그냥 UIViewController만 상속 받으면 된다).


3.만약 또 다른 화면을 만들고 싶다면 2번에서처럼  UIViewController를 상속받은 클래스를 만들면 된다.


2번 3번에서 만든 여러개의 화면이 공유하는 데이터나 내용은 1번의 SimpleHumanResourceAppDelegate에 넣으면 된다. [[UIApplication SharedApplication] delegate]를 사용하면 공유 정보리스트 중 SimpleHumanResourceAppDelegate를 리턴하게 된다.


UIViewController에는 IBOutlet UIView * view를 속성을 가지고 있다. UITableViewController는 IBOulet UITableView* tableView 를 가지고 있다. 그렇기 때문에 RootViewController는 이 속성을 자동으로 가지게 된다.




Outlet과 ReferenceOutlet의 차이는? Referencing Outlet 이 주소값을 받을 속성들.
----------------------------------------------------------------------------------------------------


<JSON>
서버나 클라이언트가 각각 구성된 언어가 다르기 때문에 특정 객체를 넘겨줄때 사용하는 것으로 원래는 xml을 사용했는데 xml 이 복잡하기에 JSON을 웹에서 많이 사용한다.
예를 들어 서버는 python으로 개발이 됐는데 client 는 objective-c로 된 어플을 사용중이라면 데이터 교환을 위한 통일된 형태가 필요하다. 이럴 때 사용되는 데이터 교환의 표준이 xml. 
그러면 xml을 개발자들이 잘 안쓰는 이유? xml 파싱하기가 쉽지 않아서
그래서 표준은 아직 아니지만 형식을 가진 문자열인 JSON 을 많이 사용한다. 이렇게 JSON 문자열로 서버에서 클라이언트로 데이터를 보낸다.
http://www.json.org/

Friday, March 25, 2011

iphone 개발 수업 3주차

3/25
< Collection >
-객체들의 주소 저장
-크기가 가변
-검색, 삭제, 수정이 쉽다 (삭제, 수정, 추가 가능한 것들은 mutable이 들어간 클래스들).
NSSet <- NSMutableSet 이 상속 : 삽입한 순서와 저장 순서가 다름, 객체의 중복 저장이 안된다.
NSArray <- NSMutableArray 이 상속 : 포인터 배열, 삽입순서와 저장한 순서가 같다. 중복 저장 가능. 배열대신 사용하면 편리하다.
NSDictionary <- NSMutableDictionary 상속 :  key 값으로 value의 검색이 가능.
아래 그림은 12시 부터 시계 방향으로 NSSet, NSArray, NSDictionary 의 클래스 설명.


그 위의 객체에 이름이 objects로 끝나는 메소드를 사용하려면 마지막 인자로 반드시 nil 을 넣어줘야 한다.
NSDictionary의 key 는 중복이 안되는데 이는 사실 NSSet 으로 관리한다. 그렇기 때문에 key를 꺼낼때 NSSet 이 ordering 한 순서로 나온다.


클래스의 메소드가 - 이면 반드시 alloc을 해서 객체를 생성해서 사용해야 하는것이고, + 로 된 메소드는 클래스 메소드로서 객체 생성 없이 클래스 이름으로 사용할 수 있다. 그리고 + 으로 되어 있으면 autorelease 되어 진다. 그럼 뭘 사용해야 하느냐? 그건 선택 나름.


다시 한번 1주차의 마지막에 언급된 architecture와 life cycle 그리고 2주차의 view-based application 을 읽고 이해하길 바란다.
-------------------------------------------------------------------------------------------------


<Notification>
노티피케이션이 필요할 때 :
1.  2주차에서 마지막에 나온 예 MyPickerViewDelegate예제를 보면 InstaTwitViewController는 그 안의 객체인 MyPickerViewDelegate의 메모리 주소를 알고 있지만 반대로 MyPickerViewDelegate는 InstaTwitViewController 의 메모리 위치를 알지 못한다. 그렇기 때문에 InstaTwitViewController의 메소드를 사용할수가 없다. 이럴 때 노티피케이션을 사용하면 해결, 곧 사용하고자 하는 객체의 메모리 주소를 모를 때 사용
2. 이벤트 발생시 동시에 여러개 메소드를 호출할때
3. 호출되는 객체가 무엇이지 모를 때
예를 들어 MainWindow에 버튼이 있을때 그 버튼을 누를 때 객체 A,B,C 의 메소드가 동시에 실행되어져야 할때, 혹은 어떤 객체의 메소드가 호출되는지 모를때 노티피케이션을 사용한다.


이는 InstaTwitViewController객체가 NSNotificationCenter 객체에게 NSPickerView 선택시 알려달라고 요청함. 그러면 NSNotification이 백그라운드로 감시하다가 이벤트가 발생하면 InstaTwitViewContoller에게 알려준다.
그러면 통보하고자 하는 MyPickerViewDelegate에서 NSNotificationCenter에 통보하는 실행문을 넣는다. 그러면 MyPickerViewDelegate에서 특정 메소드가 호출될때 NSNotificationCenter에 통보를 하고 이 객체가 다시 InstaTwitViewController 객체에 NSNotification 객체(이 안에 정보가 다 있다)통보가 된다.


이 순서는 NSNotificationCenter 를 InstaTwitViewController객체 안에 생성하고 등록한다. 그러면 이벤트가 발생하였을 때 NSNotificationCenter가 InstaTwitViewController객체에게 통보를 하게 된다. 
생성 : NSNotification 은 어플 실행시 생성, 딱 하나만 생성, 리눅스의 데몬처럼 백그라운드로 실행, [NSNotificationCenter defaultCenter] 하면 NSNotification이 리턴된다.
등록 : [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(UiUpdate) name:@"name" object:nil userInfo:nil] ; self, 즉 자신 객체를 등록하고 이벤트 발생시 호출될 메소드는 UiUpdate라는 메소드이고(@selector는 메소드의 주소를 return)  이름은 name으로 하고 object는 nil 이다(object에는 주소를 넣을 수 있다, 이러면 NSNotificationCenter 객체가 이벤트 발생을 통보시, 즉 메소드 호출 시 그 주소를 인자로 넘긴다) 라는 의미.
통보 : [[NSNotificationCenter defaultCenter] postNotificationName:@"PickerViewDidChanged" object:self userInfo:nil] ; 통보하는 곳의 이름은 PickerViewDidChaged이고 self, 나 자신을 넘기고 더 넘기고자 하는 더 필요한 데이터는 없다라는 의미


원래 특정 이벤트의 발생을 감시하는 것은 UIApplication이 하는 일이였으나 UIApplication이 감시하는 이벤트는 시스템적인 이벤트, 그러니까 버튼이 눌리는 것 같은 이벤트, 그러나 나머지 이벤트 즉 시스템적인 이벤트를 제외한 이벤트는 NSNotificationCenter가 모니터링한다. 
-----------------------------------------------------------------------------------------------


속성을 다른 객체에서 사용하려면 1. set,get 메소드를 정의하거나 2. @property로 선언하거나 3. keyofvalue dictionary를 이용한다.


<Key Value Dictionary>
일반적으로 객체는 NSObject를 상속하는데 NSObject 클래스에는 NSMutableDictionary가 있어서 key 값으로 NSObject를 상속받은 클래스의 속성을, value로는 그 속성의 속성값(그러니까 속성안에 들어가 있는 값)을 가지고 있다. 이를 이용하면 코딩이 짧아짐.


그런데 이 key value observing이 꼭 대입이 되는 것은 아니다. 예를 들어 IBOulet으로 선언된 속성(즉 interface builder로 만든 view(xml에 정의된)의 주소를 넣을 속성)는 반드시 set,get 메소드를 만들거나 property로 선언해서 사용해야 한다.


사용방법 : NSObject 를 상속받은 클래스 MyCandle이라는 것이 있을때 keyofvalue Dictionary 를 사용하려면 [MyCandle valueForKey:@"candleState"];는 property로 사용할때의 MyCandle.candleState와 동일한 의미, [MyCandle setValue:NO forKey:@"candleState"];  는 MyCandle.candleState = NO; 과 동일.


<Key Value Observing>
NSObject를 상속받은 클래스 MyCandle의 속성과 keyofvalue dictionary는 MyCandle 이 감시하면서 그 두값을 같게 맞추는데 둘중 하나가 변했을때 알려달라, 곧 메소드를 호출해 달라. 그런데 Notification과는 달리 호출되는 메소드 이름(observeValueForKeyPath)이 정해져 있다. 그래서 메소드를 @selector로 해서 인자로 넘길일은 없다.


설정 : [MyCandle addObserver:self forKeyPath:@"candleState" option:NSKeyValueObservingOptionNew|NSKeyValueObservingOld context:nil]; candleState속성이 수정시 self, 즉 나 자신에게 수정된 값이 뭔지(NSKeyValueObservingOptionNew), 그리고 예전값이 뭐였는지(NSKeyValueObservingOld) 그리고 통보할때 nil(지금은 nil이기 때문에 아무것도 없다)을 전달하면서 알려달라라는 의미.
호출되는 메소드 : -(void)observeValueForKeyPath:(NSString*)keyPath ofObject:(id)object change:(NSDictionary*)change context:(void*)context ; keyPath는 값이 수정된 속성이름, object는 통보자의 주소, change에는 바꾸기 전의 값과 바뀐후의 값이 dictionary(NSKeyValueChangeNewValue와 NSKeyValueChangeOldKey를 key로 갖는다)로, context 는 addObserver호출시 전달했던 인자.


등록시 option의 인자를 NSKeyValueObservingOptionInitial 은 원래 등록을 하면 감시가 시작되는 것이 아니라 등록하는 메소드(그러니까 등록 statement가 있는 메소드)가 끝나야 호출이 되는데(왜냐면 single thread이기 때문에) 이 option 을 사용하면 등록하는 순간 바로 monitoring 을 시작한다. 


notification과 key value observing 이랑 유사한데 그럼 언제 key value observing  를 사용하느냐? 값이 바뀌었을 때 통보할 때


이벤트가 발생했을때 호출되는 메소드는  return 값이 없다.

sqlite3

sql이 필요하게 됐다. sqlite3를 쓰기로 한다. 그닥 큰 db가 아니라서. 

sqlite3 설치
다운받고 그냥 install (configure=>make=>make check=>make install), 끝

sqlite3 사용법
내가 사용하는 건 굉장히 단순한 select문만 필요한거라.. 근데 첨에 하면 어떻게 실행시키고 어떻게 db를 만드는지 조차 생소한다. 알고나면 아.. 쉽네.. 
주의할건 special command. cvs file을 table로 load 할려면 special command의 .import 를 사용할 것. 다만 먼저 .separator를 할것.

python으로 연동하기

Thursday, March 24, 2011

make report file using open office, python module Appy

논문을 읽다가 이틀을 읽다보니 루즈하고 지겹고 재미도 없고 정체되고.. 해서 당장은 필요가 없지만 아마도 나중에 필요하게 될 것을 한 번 프로그래밍 해보자는 생각에..


당면해 있는.. 아니지 급한건 아닌데 언제가는 풀어야 할 문제들.. 생각해보니 2가지.
1. 하나는 read에서 trim이 안된 primer등을 제거하는것. global alignment 알고리즘으로 가야 하는건지.. 아니면 그냥 string search로 가야 하는건지. 지금 생각은 최장 공통 문자열 탐색(LCS)으로 찾아서 그게 cutoff(지금 생각하자면 하나의 base pair mismatch까지 허용) 를 통과하면 그 영역은 trim하는 식으로다가 할생각이긴한데.. 이건 좀 찾아봐야 할거 같다. 지금 내가 뭔소리 하는지도 파악이 안되니.
2. report form을 template로 정해놓고 특정부분 영역의 값만 바꾸는 그러니까 파이프 라인 돌리고 나면 샘플마다 다른 그림과 결과가 생길건데 기존의 template에다가 요 데이터만 넣는 것을 어찌 할까 했는데.. 


오늘 해결해보고자 하는건 2번. report file format은 pdf로다가 하는걸로(html로 하려는 의도도 있었지만 왠지 html은 가벼워 보인다는 여론이.. 근데 요즘 html5를 보기 시작했는데.. 허이구 이거 그냥 태그의 모임이 다가 아닌듯한 느낌이랄까. 여튼). 그래서 이것저것 알아보기 시작함. 우선은 text2pdf 같은 module이 있나 봤는데. 음.. 모르겠다. 어쩌다 어쩌다 찾게된 방법. open office와 appy라는 python module을 사용하는것

<open office>
http://download.openoffice.org/
예전에 원철이 형이 쓰는거 본거 같은데.. 그 때 pdf 변환이 바로 된다고 좋다고 하셨던거 같은데.. 여튼 보니까 pdf 버튼이 있다. 와. 좋다. 근데 영문판으로 깔길 권장한다. 어짜피 사용법이 naver에서는 잘 안나오고 구글링해야 하는데. 이게 옵션이 영어로 되다보니 한글판 깔면 매치가 안된다. 뭔 옵션을 이야기 하는건지..

<appy module>
http://appyframework.org/pod.html
appy가 happy의 h를 제거한 단어란거(확실한건 아니다). 어떻게 해야하는지 위 url을 살펴보면 나온다. 하지만 나같은 완전 초보를 위해서 내가 한 삽질을 반복하지 않기 위해 내 삽질을 소개하자면(내 삽질은 사실 url의 text만 잘 읽으면 다 나온다). 
기본 컨셉은 이거다. open office로 template를 만든다. 그리고 그 template 안에 바뀌어야할 문자열 내지는 테이블 안의 특정 cell을 tracking change로 표시해둔다. 아니면 insert의 note로 표시. 아 근데 사실 이게 문제였다. 도대체 tracking change가 뭐냐고? 아 다음 url을 참고한다. http://www.tutorialsforopenoffice.org/tutorial/Change_A_Document_Red_Lining_Or_Tracking_Changes.html 여기 보면 나오는데.. 아무것도 아니다. 그냥 왜 office에서 에디팅하고 그 흔적을 남겨 놓는것, 그걸 지칭한다. 한글판으로 설명하자면 편집=>변경사항=>기록. 이 모드에서 기록된 부분은 python script로 변환 가능하다. 그리고 insert 메뉴의 note는 뭐냐. 삽입=> 설명 옵션을 뜻하며 여기에다가 python script를 써주면 프로그래밍이 된다. 나머지는 위 url를 좀더 자세히 들여다 볼것.
아.. 그리고 한가지.. template에서 특정값을 바꿔서 결과 내는건 template가 있다면 open office가 필요 없다. 다만 그 결과를 odt 형식이 아닌pdf 형식으로 바꾸려 한다면 그 때 appy 모듈이 open office를 사용하기 때문에 서버에 open office 가 깔려 있어야 한다.

Monday, March 21, 2011

suffix tree (1)

whole genome alignment, Silva에서의 alignment 과정 그리고 금선생 추천 책 등등에서 많이 만나온 용어 suffix tree. 정리해야 겠다. 일단. 참고 문헌은 http://www.cs.ucf.edu/~shzhang/Combio10/lec3.pdf 과 algorithms on Strings, Trees, and Sequence의 5장부터로 한다. 과연 볼수 있을려나..


네이버링으로 대략적으로 알아본 결과 reference가 m길이의 T 문자열일때 query가 n 길이의 S 문자열이면 KMP나 보이어-무어의 방법(이 두가지 방법 다 뇌를 자극하는 알고리즘에 나온다. 기억이 가물하지만)이 O(m)의 시간이 걸리는데 비해 suffix tree는 reference를 한번 preprocessing (O(m)) 하면 O(n)의 시간만에 T에서 S를 찾아낸다(hashing 인건가). 또한 i번째 leaf 노드에서 루트까지 node의 값을 연결하면 T[i:m]의 문자열이 나온다. 그리고 suffix tree를 구하는 방식은 여러가지인데 특정 문자열에 대한 suffix tree는 unique하다. 또한 문자열 안에 substring이 몇번 나오나 혹은 어디에 있나 하는 정보를 root에서 부터 원하는 substring까지의 노드를 찾고 거기서 부터 연결된 leaf 갯수를 새면 그 정보가 나온다. 요정도..


<from UFC >
: ucf 자료를 보면 순서가 suffix의 대한 intro, definition, exact string matching problem, building suffix tree 순으로 되어 있다.  그림은 위 링크의 pdf를 참조하길. 


-hash table 보다 suffix tree가 났냐? hash가 더 이해하기 쉽고 뭐.. 시간도 비슷하지만 문젠 hash table은 query의 문자열의 길이가 고정이라는거. 그리고 다른 string match trick이 안먹힌다는데.. 이건 계속 봐야 알겠음.


-suffix tree의 정의 : 
1. rooted directed tree로 문자열 길이만큼의 leaves를 갖는다.
2. root 노드를 제외한 internal 노드는 최소한 2개의 자식 노드를 갖으며 각 edge(연결선)은 문자열의 substring으로 labeling되어 있다.
3. 한 노드에서 나가는 edge들의 시작 character는 동일할 수 없다.
4. suffix tree의 key feature는 i 번째 leaf에서 edge의 label들을 연결하면 문자열의 i번째에서 시작하는 substring이 된다.
5. 문자열의 마지막 character는 unique charater여야 한다.


-exact string matching problem
reference 문자열 ST를 O(m) 시간 만큼 걸려서 suffix tree를 만들고 query 문자열 P를 ST에서의 unique path로 찾는다. root 에서부터 query의 문자열이 되는 path를 찾는다. path의 마지막 노드 아래의 leaf가 query를 포함하고 있는 suffix가 되겠다.


-building the suffix tree
1.Naive method : O(m**2)의 시간이 걸린단다. 이해는 잘된다. root에서 부터 제일 긴 suffix 부터 node를 붙인다. 예를 들어 papua 라는 문자열을 suffix tree로 만들려면 우선은 papua에서 제일 긴 suffix 인 papua를 root 노드에서 부터 연결한다. 그 다음의 젤 긴 suffix인 apua를 또 root에서 새로운 노드로 붙인다. 그다음 suffix는 pua인데 suffix tree의 정의에 따라 자식 노드들의 첫 character는 같으면 안되기때문에 아까의 papua와 pua가 첫 글자가 겹치기 때문에 이를 root에서 공통으로 edge를 만들고  apua와 ua로 노드를 분리 시킨다. 이런식으로 마무리.
2. 원래 suffix tree의 reference의 preprocessing 시간이 O(m)이라고 했는데 이는 1973년 Weiner에 의해 소개됐고 이후 space efficient 한 방법을 McCreight가 1976년 소개, 그 뒤 1995년 더 단순한 on-line algorithm이 Ukkonen에 의해 소개
3. Ukkonen's algorithm : 1에서부터 m 까지의 prefix를 하나씩 따서 그것의 suffix들을 tree에 extension하는 방식(이 말이 이해는 안갈건데 pdf 그림보면 안다). 이때 extension은 3가지 rule( 1.s[j:i+1] 을 extend 할때 s[j:i]까지의 label이 있는 edge를 찾으면 그 edge에 i+1번째 character를 extend한다. 2. 만약 root에서 시작되는 edge중 s[j:i]까지 매치되는 edge가 없으면 맞는데까지에서 새로운 edge와 노드를 만든다. 3.이미 s[j:i+1]까지의 문자열이 정확히 매치되면 nothing to do)에 따른다. 여기까지는 기본 방법이고, 여기다가 speed up 방법이 있는데 요건 이해가 안됨.


여전히 알고리즘 시간에 대한 계산이 이해가 잘 안된다. 음.. 그리고 예전 알고리즘 책 볼때도 느낀건데 어떻게 진행하는지는 이해는 하는데 왜는 깊게 이해 안되는 느낌이랄까.. 명화를 감상하는데 아 저기에 뭐가 있고 저기에 뭐가 그려져 있구나. 근데 이게 무슨 느낌으로 그린거지?하고 이해하지 못하는 느낌. 내가 볼때 반복만이 이 느낌을 채울수 있다고 본다.