푸으름

Algorithm 공부 #24 - dp 동적 계획법(Dynamic Programming) ● 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결하여 최동적으로 복잡한 문제의 답을 구함 ● 동적 계획법의 원리와 구현 방식 1. 큰 문제를 작은 문제로 나누기 2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값이 항상 같아야 함 3. 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하여 추후 재사용, 이 방식을 메모이제이션이라 함 4. 동적 계획법은 톱 - 다운 방식과 바텀 - 업 방식으로 구현 가능 ● 톱-다운 구현 방식 : 위에서부터 문제를 파악해 내려오는 방식 / 주로 재귀 함수 형태로 구현 코드의 가독성이 좋고 이해하기가 편함 ● 바텀-업 구현 방식 : 가장 작은..

Algorithm 공부 #23 - 조합 조합(Combination) ● n개의 숫자에서 r개를 뽑는 경우의 수 ● 코딩 테스트에서는 순열보다는 조합이 빈도수가 높음 ● 조합은 동적 계획법의 시작이라고 할 수 있음 ● 조합의 접근법 : 이미 그 전단계의 데이터의 선택여부가 결정되었다고 생각하기 D[i][j] = D[i-1][j] + D[i-1][j-1] 백준 11050번 이항 계수 1 https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net #include using namespace std; int D[11][11]; int m..

Algorithm 공부 #22 - 최소 공통 조상(Lowest Common Ancestor) 최소 공통 조상(lowest common ancestor) ● 최소 공통 조상 : 임의의 두 노드를 선택 후, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드 ● 선택된 누 노드의 깊이가 다른 경우: 더 깊은 노드를 부모 노드로 1개씩 올려 주면서 깊이를 맞춰줌 이때, 두 노드가 같다면 해당 노드가 최소 공통 조상이므로 탐색 종료 최소 공통 조상 빠르게 구하기 ● 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에는 한 단계씩 올려 주는 방식이었다면 이 방식은 2^k씩 올라가면서 맞춰주는 방식 ● 기존에 자신의 부모 노드만 저장해 놓던 방식에서 ..

Algorithm 공부 #21 - 세그먼트 트리 세그먼트 트리(Segmant Tree) ● 주어진 제이터의 구간 합과 데이트 업데이트를 빠르게 수행하기 위한 알고리즘 ● 트리 초기화 / 질의값 구하기(구간 합 구하기, 최대, 최소) / 데이터 업데이트하기의 과정으로 나뉨 ● 트리 초기화하기 1. 데이터의 개수가 2^k일때 start_index=2^k 2. 2^k+1 인덱스부터 리프노드를 제외한 나머지 노드의 값을 채우기 3. 구간 합일 때 : A[N] = A[2N] + A[2N+1] / 최대 : A[N] = max(A[2N], A[2N+1) 최소 : A[N] =min(A[2N],A[2N+1]) ● 질의값 구하기 1. 질의 인덱스를 세그먼트 트리 인덱스로 변환 => 세그먼트 트리 index = 주어진 질의..