기억을 위한 기록들

배열이나 링크드리스트에서는 특정 데이터를 찾기위해 순차 탐색, 이진 탐색을 사용. 이진 탐색트리에서도 이진탐색을 사용한다. 근데 그래프에서는?? 이와같은 방법들이 쉽게 통하지 않는다. 대표적인 기법 2가지가 있다. 바로 깊이우선탐색과 너비우선탐색이다. 깊이 우선 탐색(DFS) (길 끝까지 깊이 들어간다.) 재귀활용 (or stack stl를 활용) 설명 : 최상단노드부터 말단 노드까지 빠르게 내려가면서 탐색하는 방법으로 보통 경우의 수를 확인 할 때 (사용 예: 바둑, 장기 등) 1. 시작정점을 방문표시 2. 해당 정점과 이웃하고 있는 정점중 아직 방문표시 없는곳을 선택하고 시작정점으로 삼고 dfs시작 다시 1번. 3. 정점에 더이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2번. 4. ..

정점 : 지점을 나타낸것 간선 : 2개 이상의 정점을 연결한 것 인접(Adjacent) : 나와 이웃하고 있는 정점 경로(Path) : 한 정점에서 다른 정점까지의 길 사이클(Cycle) : 단순 경로의 시작과 종료 정점이 동일한 경로 연결성 : 모든 정점이 서로 연결되어 있는것 방향성 그래프(Directed Graph) : 간선이 방향성을 가짐. 무방향성 그래프(Undirected Graph) : 간선에 방향성이 없음. 그래프는 정점의 집합? 간선의 집합? 정점의 집합 표현 방법 : 배열, 링크드 리스트 등 간선의 집합 표현 방법 : 간선은 그냥 선이 아니라 '인접관계'를 나타냄. 그래서 인접행렬(Adjacent Matrix) 또는 인접리스트(Adjacent List)로 표현 간선의 집한 표현방법 2가..

hyo-ue4study.tistory.com/127?category=907498 힙(Heap) 특징 힙은 완전 이진트리 자료구조의 일종. 힙에서는 항상 루트노드를 제거. 최소 힙 : 루트 노드가 가장 작은 값/ 값이 작은 데이터가 우선적으로 제거 최대 힙 : 루트 노드가 가장 큰값/ 값이 가장 큰 hyo-ue4study.tistory.com hyo-ue4study.tistory.com/189?category=862971 [C++]STL 우선순위 큐(priority_queue) 0. 기본 우선순위는 less (내림차순 높은값이 루트값) #include #include #include using namespace std; int main() { //priority_queue //아무것도 입력하지 않으면 기본..

- 힙은 힙 순서 속성(Heap Order Property)을 만족하는 완전 이진트리 자료구조의 일종. * 힙 순서 속성 : 트리 내의 모든 노드가 부모 노드보다 커야한다는 규칙 - 힙에서의 삭제는 항상 루트노드(최소값)를 제거. 왜냐! 가장 작은 데이터를 갖는 노드는 루트노드이기 때문. 삭제 후 에도 힙 순서속성 유지. - 최소 힙 : 루트 노드가 가장 작은 값/ 값이 작은 데이터가 우선적으로 제거 - 최대 힙 : 루트 노드가 가장 큰값/ 값이 가장 큰 데이터가 우선적으로 제거

순차탐색 - 데이터집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘. - 한쪽 방향으로만 탐색을 수행한다고해서 선형 탐색이라고 부르기도 함. - 효율이 좋진 않지만, 높은 성능을 필요로 하지 않거나, 데이터집합의 크기가 작을 때 유용 자기구성 순차탐색 - 자주 찾는, 자주 사용하는 항목들을 다른 항목들보다 우선하여 접근하게 가까운곳에 배치한다. - 자주 사용되는 항목을 어떻게 선별하는가에 대한 세가지 방법 1. 전진 이동법(Move To Front) : 한번 탐색되면 무조건 가장 앞에 위치 시킴. 2. 전위법(Transpose) : 한번 탐색되면 앞칸으로 한칸씩 이동. 자주 탐색되면 앞으로 몰림 3. 빈도 계수법(Frequency Count) : 각 요소들이 탐색되는 횟수..

#include using namespace std; template class Node { public: Node() : mdata(static_cast(0)) , mPre(nullptr) , mNext(nullptr) {}; Node(T _data) : mdata(_data) , mPre(nullptr) , mNext(nullptr) {} ~Node() { delete mPre; delete mNext; }; public: T mdata; Node * mPre; Node * mNext; }; template class DoubleLinked_List { public: DoubleLinked_List() : mHead(nullptr) , mTail(nullptr) {}; ~DoubleLinked_Lis..

이번엔 링크드 리스트다. 장점: - 새로운 노드의 추가/삽입/삭제 쉽고 빠름( 배열은 요소를 삽입하거나 제거하기 어렵) 단점 : - 다음 노드를 가리키려는 포인터 때문에 각 노드마다 4바이트의 메모리가 추가로 필요. - 특정 위치에 있는 노드를 얻는데 드는 비용이 크며, 속도도 느리다. 링크드리스트의 필요한 기본 연산은 5가지 - 노드생성/소멸 - 노드 추가 - 노드 탐색 - 노드 삭제 - 노드 삽입 코드 : #include using namespace std; template class Node { public: Node() {}; Node(T _data) :data(_data) {} ~Node() {}; T data; //현재 노드에 있는 데이터 Node * next; //현재 노드의 다음 노드를 가..

Least Recently Used 알고리즘이란? - 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법 - 컴퓨터의 자원은 한정적이며, 한도내에서 최고의 효율을 얻기 위해 여러 알고리즘이 존재, 그 중에 하나. (FIFO,OPT,LRU,LFU,MFU 등등..) 방법 첫번째 : 페이지에 저장 된 데이터가 언제 사용되었는지를 알 수 있게하는 부분을 구현해서 제일 오랫동안 참조되지 않는 데이터를 제거 하는 방법. 두번째 : 페이지에 데이터를 큐 형식으로 저장하는 방식. 페이지내에 데이터가 존재한다면 데이터를 페이지 내에서 제거하고 맨 위로 다시 올리고, 존재하지 않는다면, 바로 입력하여 맨 아래에 있는 데이터를 삭제하는 과정을 진행. 예제 그림 위 그림에서 7번, 9번같은 상황은 참조하는 값이 이미 페이지에..

이런 표가 머릿속에서 저절로 떠오르면 참 좋을텐데... 아래 사이트에서 직접 해볼 수 있다. www.toptal.com/developers/sorting-algorithms Sorting Algorithms Animations Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions. www.toptal.com

오름차순or 내림차순으로 정렬되어 배열이 있다고 하고, 정렬 되어 있는 배열에 특정값이 몇번 인덱스에 있는지 찾는 이진검색 알고리즘이 존재한다. 변수명 arr 배열(오름차순)을 넣고 15을 찾는다면 변수명 arr2배열에 주석부분을 서로 바꿔준 뒤 마찬가지로 15을 찾으면 사실 여기까지는 인터넷에 찾아보면 더 자세한 설명도 많이 나온다. 근데 내가 글을 쓴 이유는 순위 시스템에서 새로운 점수를 받았을때 해당 점수가 등수에 반영 가능한 여부를 판단하기 위해서 이다. 그러기 위해 이진검색을 조금 변경 해보았다. 내림차순인 변수명 arr2 배열에서 targetValue 새로운 점수인 70점이 순위에 드는지 여부를 확인하기 위함이다. 결과이다. 출력에 result+1은 실제 배열 인덱스와 우리가 인식하는 등수(1..

이전에 작성하였던 넓이우선탐색(BFS)은 말그대로 해당 그래프에 어떤 요소가 있는지 전체적으로 탐색한것이였다. 이제 여기서 좀 더 나아가 해당 그래프에서 시작점과 목표점를 정하여 해당 두 점이 이어져 있는지 확인하는 알고리즘을 확인해보자 . 이전에 작성했던 Graph 클래스에서 새롭게 추가 된 bool형을 반환하는 Search함수이다. 이제 이 함수를 이용해서 확인해보자. 이런 그래프가 있다고 하면 6과7이 나머지 노드들과 떨어져 있는 상태이다. 예를 들어 1에서 7까지 갈수 있는지 여부를 확인한다고 하면 결과가 0이 나온다(실패) 이제 이 노드들을 이어준다. 이렇게 5번과 6번 노드를 추가로 이어주고, AddEdget(5,6)을 추가해준 뒤 확인해보면 결과는 1로 출력된다.(성공) 여기까지는 이제 갈수..

이번엔 스택이다. 스택 쌓자 스택 클래스와 해당 스택에 쌓는 노드 클래스 2개의 클래스로 구성 되어 있다. template class Node { public: Node(T _data) : mData(_data) {}; ~Node() { delete mNextNode; }; T mData; //현재 노드에 있는 데이터 Node* mNextNode; //현재 노드의 다음 노드를 가리키는 포인터 }; template class Stack { public: Stack() {}; ~Stack() {}; void Push(T newItem); T Pop(); T GetTopData(); bool IsEmpty() const; int GetStackSize() const; private: Node * mTopNod..