목록전체 글 (140)

justgo_developer

Dynamic Programming-knapsack problem

knapsack problem- n개의 아이템과 배낭- 각각의 아이템은 무게 Wi와 Vi를 가짐- 배낭의 용량 W- 목적 : 배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합예Greedy - 가격이 높은 것부터 선택- 무게가 가벼운 것부터 선택- 단위 무게당 가격이 높은것부터 선택->불가능 순환식bottom-up
IT/알고리즘 2018. 1. 18. 00:02
Dynamic Programming(LCS)

LCS(Longest Common Subsequence) 순환식 항상 순환식은 base케이스로 수렴하는지 확인해야한다. 동적계획법
IT/알고리즘 2018. 1. 17. 23:41
힙(Heap)

힙이란 최대값 및 최소값을 찾아내는 연산을 하기 위한 완전이진트리를 기본으로 한 자료구조- 완전이진트리- 부모노드의 키 값이 자식 노드의 키 값보다 크다(최대힙) or 작다(최소힙) 노드 삽입- 우선, 삽입하려는 노드를 완전이진트리의 맨 마지막 자리에 추가한 뒤,부모노드와 크기를 비교해가면서 대소관계아 따라 노드를 교환하여 힙으로 다시 만드는 과정을 거친다.노드 삭제- 힙에서 노드의 삭제는 루트노드를 삭제하면서 반환한다는 의미이다. 최대값이나 최소값을 찾아내는 연산을 하기 위한 트리이기 때문이다.노드에 노드가 하나도 남지 않을때까지 삭제연산을 반복해 반환된 노드들을 순서대로 늘어놓으면 오름차순 혹은 내리참순으로 정렬된 배열이 된다. 이를 힙정렬이라고한다. 루트노드와 맨마지막 노드의 자리를 바꾼다. 이렇게..
IT/자료구조 2018. 1. 17. 23:18
이전 Prev 1 ··· 28 29 30 31 32 33 34 ··· 47 Next 다음