복습노트 복습노트

Priority Queue(우선순위 큐) 우선순위가 가장 높은 원소부터 pop되는 큐 ex)원소의 값이 클수록 우선순위가 높다 배열로 구현 1) 삽입 : O(N) / 삭제 : O(1) 2) 삽입 : O(1) / 삭제 : O(N) 결국 둘다 O(N^2)이 걸린다. 따라서 힙(Heap)으로 구현 Heap (힙) 완전 이진 트리로 이루어진 자료구조 최솟값 or 최댓값을 빠르게 구하기 위한 자료구조 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 힙 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 힙 느슨한 정렬상태(반 정렬 상태) 유지 ex) 최대 힙 (Max Heap) Heap 원소 삽입 (ex : max heap) 시간 복잡도 : ..

1) 정점 v가 속해 있는 그룹은 몇 번 그룹인가? (Find) 2) 정점 u가 속한 그룹과 정점 v가 속한 그룹을 합치면 어떻게 되는가? (Union) 정점 인덱스가 속한 그룹의 정보를 다음과 같은 배열에 저장할 수 있습니다. 만약 0번 그룹과 5번 그룹을 합치고 싶으면 어떻게 해야 할까? 다음과 같이 배열을 수정할 수 있습니다. 시간복잡도 Find : O(1) Union : O(N) 모든 정점을 순회하면서 바꿔야하기 때문 위의 그래프를 조직도 처럼 만들어 보자! 최고 리더는 -1로 해주고 각 노드마다 직속 상사를 배열로 저장하면 다음과 같은 배열이 됩니다. 여기서 0번 그룹이 5번그룹과 합치려면 어떻게 해야될까? 다음과 같이 합치면 됩니다. 시간 복잡도 Find : O(정점 v가 속한 트리의 높이) ..

그래프 탐색이란? 그래프의 한 정점으로 부터 출발해서 모든 정점을 1번씩 방문하여 그래프에 대한 정보를 얻는 것 정점 방문 순서에 따라 크게 두 방식으로 나뉨 깊이 우선 탐색(DFS) / 너비 우선 탐색 (BFS) DFS(깊이 우선 탐색) 다음 분기(brunch)로 넘어가기 전에 현재 분기를 완전히 탐색하는 방법 트리의 전위(preorder)탐색이 그래프로 확장된 개념 재귀 함수 or 스택으로 구현 1) 정점 1개를 선택한다. 2) 현재 정점과 이웃한 정점 중 아직 방문하지 않은 정점 중 하나를 방문한다. 3) 더 이상 방문할 수 있는 정점이 없는 경우, 현재 정점의 이전 정점으로 돌아간다. 4) 모든 정점을 방문할 때까지 2~3을 반복한다. 왼쪽의 그래프를 dfs를 통한 순서를 오른쪽 dfs tree로..

Graph? 이산수학에서 사용 특정 집합의 추상화된 원소들에 대하여, 원소들의 일부분이 어떤한 관계로 "연결되어있음"을 나타내는 수학적 구조의 일종 연결 관계가 있는 집합을 나타내는 데에 좋은 자료구조이다. 정점 v의 차수(degree) deg(v) 정점 v와 연결되어있는 정점의 수 ex) deg(1) = 2 경로(path) p 정점의 나열로써, 인접한 정점 사이에 간선이 있는 경우 p = {1, 3, 4, 5, 3} 단순 경로 (simple path) p 경로로써, 중복되는 정점이 없는 경우 p = {1, 3, 4, 5} 순환 (cycle) c 경로로써, 시작점과 끝점이 동일한 경우 c = {1, 3, 4, 5, 3, 1} 단순순환 (simple cycle) c 순환으로써, 시작점과 끝점을 제외한 중복..

분할정복이란? Divide and Conquer 주어진 문제를 둘 이상의 부분 문제로 나누어 푸는 방법 거의 같은 크기로 부분 문제를 나눔 재귀 호출 사용 1) Divide : 부분 문제로 나눌 수 있는 경우 2개 이상의 문제로 나눈다. 2) Conquer : 더 이상 나눌 수 없는 경우 현재 문제를 해결(정복) 한다. 3) Combine : 해결된 부분 문제들을 합쳐서 기본 문제를 해결한다. DP에는 중복이 발생하지만 분할정복에는 중복이 발생하지 않는다. 분할 정복의 전체 높이는 log n이다. 예시문제 백준 1992 (쿼드 트리) c++ 문제 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두..

예시 문제로 먼저 greedy라는 개념이 무엇인지 보겠습니다. 백준 1931 (회의실 배정) c++ 문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의의 시작시간과 끝시간이 주어지면 회의시간이 서로 겹치지 않게 최대 몇개의 회의가 진행될 수 있는지 알아 riveroilstone.tistory.com Greedy 알고리즘은 주어진 문제의 요소를 여러 개의 부분으로 나눈 뒤, 각 부분의 독립적인 평가를 시행하여 가장 평가치가 높은 것부터 고르는 방법입니다. 1) 한 번 선택하기로 한 (선택하지 않기로 한) 요소는 다시 고려하지 않는다. 2) 이렇게 얻은 해가 최적해라는 것을 보장할 때만 사용한다. 예시 문제 백준 2180..

동적 계획법(Dynamic Programming) 1) 큰 문제를 작은 부분 문제들로 나누어 푸는 방법 2) 점화식 세우기 3) 메모이제이션(Memoization) 기법 사용 ex) 피보나치 수열 [1, 1, 2, 3, 5, 8, 13, 21, 34, ....] F(n) = F(n-1) + F(n-2) HTML 삽입 미리보기할 수 없는 소스 다음과 같은 피보나치 수열을 수행하는데 재귀적으로 이루어지면서 중복되는 함수가 많습니다. 예를 들어 n이 6일때 피보나치 수행도를 보면 F(3)이 3번이나 수행되었습니다. F(3)의 값은 1번만 알면되는데 재귀적으로 탐색하는 과정에서 중복적으로 계산된 것입니다. 이를 방지하고자 메모이제이션 기법을 사용합니다. 메모이제이션(Memoization) 부분문제를 계산한 결과..

Brute Force 가능한 모든 해의 후보를 체계적으로 나열한 뒤, 각각의 후보가 진짜 답인지를 차례대로 확인하는 방법 예를 들어 어떤 수 N을 소인수분해 하는 과정을 모두 출력하는 프로그램을 구현한다고 가정하면 다음과 같은 코드를 짤 수 있습니다. int N; void chk(int i); int main() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); cin >> N; for (int i = 2; i