justgo_developer

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

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

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

트리: 부모-자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조부모는 여러 자식을 가질 수 있지만 자식은 하나의 부모를 갖는다.이진트리는 각 노드가 최대 2개의 자식을 가지는 트리위의 그림은 포화이진트리 구조이다. 모든 노드가 2개의 자식을 가지고 있다.트리의 최상단 노드를 루트(root)라고 한다.루트로부터 어떤 노드까지의 거리를 그 노드의 깊이(Depth)라 한다.깊이가 같은 노드끼리의 집합을 레벨(level)이라 한다.같은 부모를 가진 노드들을 형제(Sibling)노드라 한다. 트리의 표현배열표현법 : 각 노드에 인덱스를 부여하여 배열에 저장하는 방법링크표현법 : 다음 노드를 가리키는 포인터 변수를 이용하여 부모노드가 자식노드를 가리키는 방법트리의 순서가 배열의 인덱스가 되어 1번부터..

행렬의 곱셈 pxq행렬 A와 qxr행렬 B곱하기 void product(int A[][], int B[][], int C[][]){for(int i=0 ; i

동적계획법1. 일반적으로 최적화문제(최소값,최대값) 혹은 카운팅 문제에 적용됨2. 주어진 문제에 대한 순환식을 정의한다.3. 순환힉을 memoization 혹은 bottom-up 방식으로 푼다. - subproblem들을 풀어서 원래 문제를 푸는 방식, 그런 의미에서 분할정복법과 공통성이 있음- 분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않음- 즉 서로 overlapping하는 subproblem들을 해결함으로써 원래 문제를 해결 분할정복법동적계획법 Optimal Substructure- 어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말한다.- 분할정복법/탐욕..

행렬 경로 문제 - 정수들이 저장된 n x n 행렬의 좌상단에서 우하단까지 이동한다.단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다.- 방문한 칸에 있는 정수들의 합이 최소화되도록 하라. Recursive algo. int mat(int i, int j){if (i==1 && j==1)return m[i][j];else if(i==1)return mat(1,j-1) + m[i][j];else if(j==1)return mat(i-1,1) + m[i][j];elsereturn Math.min(mat(i-1,j) , mat(i,j-1) ) + m[i][j]; } => 비효율적 Memoization:계산된 결과값을 캐시에 저장int mat(int i, int j){if(L[i][j] != -1)return L..

큐(Queue) 큐는 데이터의 제거는 가장 앞에서 수행되며, 데이터의 삽입은 가장 뒤에서 수행되는 제한된 리스트 구조가장 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO- first in first out)형태의 자료구조이다. 가장 오래전에 입력된 데이터를 front라고 하며가장 최근에 입력된 데이터를 rear라고 한다. 삭제는 front에서 이루어지고삽입은 rear에서 이루어 진다. 삽입 - insert: 리스트 끝 부분을 가리키는 rear에서 발생하며데이터가 삽입 될때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.삭제(추출) - remove: front가 가리키고 있는 데이터를 꺼낸 후 front값을 하나 증가 시키도록 구현한다.front값이 rear를 추월하게 되면 더 이상 제거..

스택(Stack)-배열 이용: 가장 최근에 들어간 데이터가 먼저 나오는 구조후입선출(Last In First Out)이라고 한다. 배열은 사이즈가 정해져 있다.현재 데이터의 위치를 알기 위해 top이라는 변수를 사용(스택포인터) Push : 스택에 데이터를 넣는 작업Pop : 스택에 들어 있는 데이터를 빼내는 작업 실제로 배열을 이용한 스택 구조에서는 top의 위치를 변경함으로써데이터를 빼낸 것처럼 처리한다. Push: 스택에 데이터가 가득 찼는지 확인 후 가득차있지 않다면 데이터를 넣어주는 작업Pop : 스택에 데이터가 있는지 확인 후 데이터 배내는 작업 연결리스트를 이용한 스택: 연결리스트를 이용한 스택 구현은 스택의 크기가 정해져있지 않고 동적으로 늘어날 수 있다. 첫 노드를 head, 마지막 노드..

동적계획법(DP) Fibonacci Numbers->recursion으로 하니 많은 계산이 중복됨Memoization: 중간 계산 결과를 cahing함으로써 중복 계산을 피함bottom-up 방식배열을 이용해 순환식을 bottom-up방식으로 계산하는 것은 동적계획법이라ㅗㄱ 한다. 이항계수(Binomial Coefficient)->많은 계산이 중복됨 Memoization Dynamic Programming Memoization vs Dynamic Programming- 순환식의 값을 계산하는 기법들이다.- 둘 다 동적계획법의 일종으로 보기도 한다.- Memoization 은 top-down방식이며, 실제로 필요한 subproblem만을 푼다.- 동적계획법은 bottom-up 방식이며, recursion에..