justgo_developer

배열의 경우, 인덱스나 주소값을 통해서 한번에 해당값에 접근할수있다.대신에 길이가 가변적이지 못하다. 링크드리스트의 경우, 길이가 고정되지 않는 대신 원하는 값을 찾기 위해 각 노드를 일일이 순회해야 한다. 최악의 경우 O(n) 해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 구조: 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁금의 탐색 알고리즘-> 탐색 성능이 향상됐지만 공간은 희생함 해싱(hashing): 해시테이블을 이용한 탐색: 자료를 검색할 때, 탐색이나 첨자가 아닌 내용에 의해 필요한 자료에 도달하는 기법 자료를 찾아주는 함수를 해싱함수라고 한다.서로 다른 자료가 해싱 함수에 의해 같은 값을 생성하는 경우 충돌(Collision)이라고 한다.탐색시간이 O(1)..

knapsack problem- n개의 아이템과 배낭- 각각의 아이템은 무게 Wi와 Vi를 가짐- 배낭의 용량 W- 목적 : 배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합예Greedy - 가격이 높은 것부터 선택- 무게가 가벼운 것부터 선택- 단위 무게당 가격이 높은것부터 선택->불가능 순환식bottom-up

LCS(Longest Common Subsequence) 순환식 항상 순환식은 base케이스로 수렴하는지 확인해야한다. 동적계획법