최적부분구조 : 부분문제 정답을 이용해 기존문제의 답을 구할 수 있는가?중복되는 부분문제:부분문제에 중복 계산이 있는가?해결법: 1\. memorization : 재귀/ 상위하향 접근 2\. tabulation : 반복문/ 하위상향 접근1.최적부분구조2.탐욕적 선
divideconquercombine 보통 2.conquer 단계가 쉽지 않다합병정렬: 하나의 리스트를 반으로 나눈뒤 문제풀기 1\. divide 2\. conquer 3\. combine : 요놈이 어렵다 (보통 함수를 이용!)퀵정렬 : 1\. divid
패턴매칭 알고리즘 1. 보이어무어 시간복잡도: 최악 O(m*n) but 빠를때는, 매우 빠르다. 일반적인 상용 시스템에서 사용중 패턴의 마지막 요소, 즉 오른쪽 인덱스를 기준점으로! 해당 문자열이 패턴에 있다면, 그 인덱스까지 skip 없다면, 완전히 뒤로
스택과 재귀: 재귀는 어렵다. 또한 recurison error 위험이 있다. 따라서 가급적 스택을 이용! 큐와 비슷하게 가능. stack == queue, pop() == popleft <동일구조>!!while stack :stack.pop()갈 수 있는 방향