본문 바로가기

전체 글

 (27)
DP: knapsack problem (1) n개의 물건이 각각 다른 가치, 무게를 가지고 있다고 하자.나의 배낭에는 무게 w만큼의 물건을 담을 수 있다. 제한된 용량을 가진 배낭(Knapsack)에 최대한의 가치를 넣어보자.  물건을 하나씩 넣으면서, 넣는 경우와 안 넣는 경우를 비교하며 최대값을 선택하면 된다. dp[i][w]: i번째 물건까지 고려했을 때, 배낭용량이 w인 경우 얻을 수 있는 최대 가치 이 경우 시간 복잡도는 O(n*w)이다.  역시 문제를 풀어봐야 제 맛knapsack 문제집: https://www.acmicpc.net/workbook/view/19494 OR https://www.acmicpc.net/problemset?sort=ac_desc&algo=148 ✘ 백준 1535 안녕 classic knapsack proble..
stack (1) Stack은 LIFO (List In, First Out) 자료구조입니다.가장 최근에 삽입된 데이터가 가장 먼저 제거됩니다. python에서 Stack은 주로 List로 구현됩니다.   python에서 Queue은 주로 Deque로 구현됩니다.Deque는 양 끝에서 O(1) 시간복잡도의 자료구조입니다.    ✘ python List 특성Dynamic array: 메모리 관리 측면에서 효율적Over allocation: 리스트 크기를 초과하여 여유 메모리 할당python list는 새로운 요소가 추가될 때마다 매번 메모리 할당 XReference counting: 참조 카운팅 방식으로 메모리 관리Garbage collector로 참조 카운트가 0이 된 객체를 자동 메모리 해제+ deque는 이중 연결 리..
은닉 마르코프 모델 HMM (Hidden Markov Model) * 패턴인식(오일석) 7장 순차 데이터의 인식의 내용을 학습하고 정리한 글입니다. 모든 그림은 해당 책으로부터 가져왔습니다. 순차 데이터 (Sequential data): 시간성(temporary property)를 갖는 데이터  시간성을 갖지 않는 데이터와 대비 시켜보면서 특징을 알아보겠습니다.   ① 특징의 순서를 바꾸면 패턴의 물리적 특성이 왜곡된다.  [그림 7.1]은 두 축 x1, x2를 바꾼 공간입니다. 바꾸어도 베이지안 분류기, 신경망, SVM, k-NN 등 문제되지 않습니다.  [그림 7.2]는 x4, x5를 바꾼 모습입니다. 이 경우 시간성을 갖는 경우 패턴의 물리적 특성이 왜곡됩니다.    ② 특징 벡터가 가변 길이를 갖는다.  ③ 관측 벡터로 표현한다.  : 시간 t에서의 관측   :..

티스토리툴바