자료구조 알고리즘 (30) 썸네일형 리스트형 동적계획법 메모리를 더 사용하여 이미 접근했던 배열을 추가 접근하지 않는 방식. 하향식 접근법 재귀에서 많이 사용 됨.dp 를 사용하는 알고리즘 이항 계수 ( 5 개 중 2 개 뽑는 경우의 수는?) 보통 이항 계수를 재귀로 푸는데 그러면 재귀 호출이 너무 많아진다.이를 방지하기 위해 메모이제이션이라는 방식을 이용한다.배열에 호출된 특정 방식에 대한 결과 값을 저장하여, 해당 특정 방식이 반복되어 호출 될 경우에 배열에 저장한 값을 가져오는 방식이 동적 계획법이다. int cache[50][50];int Combination(int n, int r){ // 기저 사례 if (r == 0 || n == r) { return 1; } // 이미 답을 구한 적 있으면 바로 반환 int& ret = cache[n][r].. 최소 신장 트리 최소 스패닝 트리 - 그래프/트리의 응용최소 스패닝 트리를 알아보기 위한 자료구조가 있다.상호 배타적 집합(Disjoint Set) -> 유니온-파인드 라고도 함.(합치기-찾기) 상호 배타적 집합 코드예로 알아본다. 리니지 배틀그라운드 라는 혼종을 만든다!혈맹전 + 서바이벌을 합치는 게임을 만든다면?1인 팀 1000명 (팀id 0 ~ 999 ) 고유 id 부여 동맹 시스템 있음 ( 1번팀 + 2번팀 = 하나의 팀 ) 이렇게 됨 일반적으로 팀 병합을 한다면 시간복잡도 O(n) 으로 안좋음void NewGame(){ struct User { // 내가 속해 있는 팀을 Id 로 구분 int teamId; // TODO }; // TODO : UserManager vector users; for (int .. 해쉬 테이블과 맵의 차이 해쉬 테이블 알아보기 해시 테이블에 관하여많이 나오는 질문 map vs hash_map(C++11 표준 unordered_map)map : 레드블랙트리.균형 이진 트리로 만들어져 트리 구조로 관리가 된다.그리고 균형을 맞추기 위해 트리의 한 계층으로 쏠리는 것을 방지하기 위한 조건과 알고리즘이 적용되어 있다.삽입/삭제/탐색 의 시간복잡도가 O(logN) 이다. 그런데 시간복잡도 상의 더 빠른 자료구조는 hash_map 이다.해쉬 맵은 메모리를 더 많이 사용하여 속도를 취하는 방식이다.다만, 충돌이 너무 많이 일어나지 않는다는 가정하에 해쉬 맵이 더 빠르다.충돌이 일어나면 다른 자리를 찾거나 체이닝 등에 의해 시간이 할애되기 때문이다. 충돌이 적다는 가정하에 hash_map 의 삽입/삭제/탐색의 시간복잡도는 O(1) 로 가장 .. 퀵 정렬 시간복잡도 : 최악의 경우 O(N^2) 평균적으로 O(NlogN) 이다. 데이터 복사가 없기 때문에 병합보다 일반적인 경우 더 빠름 시간복잡도 같아도pivot >= v[low] 이면 low 를 오른쪽 이동 반복pivot 1,2 의 반복문을 빠져나왔을때 low 1,2,3 반복low > high 가 되면 반복문 빠져나와서 v[pivot] 과 v[high] 스왑그 후 pivot 기준으로 나뉘어진 왼,오 를 다시 퀵 소트로 각각 pivot 다시 설정해서 정렬 반복void QuickSort(vector& v, int left, int right){ if (left > right) return; int pivot = v[left]; int low = left + 1; int hig.. 병합 정렬 분할 정복이라는 개념이 들어간다. 분할 문제를 더 단순하게 분할정복 분할된 문제 해결결합 결과 취합 마무리3 단계로 이루어짐 만약 8개의 원소가 있다면 반으로 나눠서 각각 정렬한다.분할을 최대한 많이 함 그 다음 정렬된 각각의 문제들을 결합하여 다시 정렬.당연히 재귀적인 방식을 이용한다.시간 복잡도 : MergeResult 함수는 N 근데 MergeResult 를 반반씩 쪼개 질 때마다 사용하므로 logN 만큼 사용한다 즉, O(NlogN)이다. void MergeResult(vector& v, int left, int mid, int right){ int leftI = left; int rightI = mid + 1; vector temp; while (leftI mid) .. 힙 정렬 힙 자료구조를 이용하는 정렬.O(nlogn)의 시간복잡도를 가진다. 맨 마지막 인덱스부터 정렬한다.void HeapSort(vector& v){ priority_queue, greater> pq; // O(NlogN) // pq 에 데이터를 push 할 때는 시간 복잡도 logN이다. // 그러나 여기서는 v의 모든 요소 N 개를 집어넣으니 NlogN이다. for (int num : v) pq.push(num); v.clear(); // O(NlogN) // 위와 같음 while (!pq.empty()) { v.push_back(pq.top()); pq.pop(); }} 삽입 정렬 삽입 정렬정렬할 배열의 원소를 하나씩 빼서 정렬한다.보통 배열을 하나 더 만들어서 값을 복사해오면서 정렬할거라 생각할수 있지만 실제로는 그렇게 구현하지 않고, 정렬할 배열의 왼쪽, 오른쪽 등의 기준으로 나누어 정렬한다.결국 시간복잡도 O(N^2) 이다.. 일반적으로 효율 안좋다. 배열을 안쪽 for 문을 돌 때 마다 인덱스 i 까지의 배열 요소들이 정렬된다.예) i == 3 이면 v[0]~v[3] 까지의 요소들이 정렬된다. 즉, 안쪽 for 문 돌 때마다 정렬이 특정 범위까지 계속 일어난다. void InsertionSort(vector& v){ const int n = (int)v.size(); for (int i = 1; i =0; --j) { if (v[.. 선택 정렬 선택 정렬배열을 전체 스캔을 통해서 가장 우선순위가 되는 원소를 맨 앞으로 이동시킨다. 즉, 버블 처럼 순간순간 비교하여 바꾸는 것이 아니라 배열 전체 스캔 후 1번. 이것을 정렬이 끝날 때 까지 반복한다. 버블 정렬보다는 성능이 좋지만 O(N^2) 이다. 좋지 않음 void SelectionSort(vector& v){ const int n = (int)v.size(); for (int i = 0; i 이전 1 2 3 4 다음
