Algorithm/자료구조

해시(Hash)란? 데이터를 다루는 기법 중 하나이며, 키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing)이라고 한다. 해싱이 왜 필요할까? 선형 탐색 또는 이진 탐색은 찾는 키가 자료구조에 들어있는지 반복적 비교가 필요 -> 아무리 빨라도 O(logn) ->더 빠른 알고리즘 필요 ->O(1)을 보장하는 탐색 예로는 키를 그대로 1차원 배열의 인덱스로 사용 ->하지만 단순히 키를 배열의 인덱스로 그대로 사용하면 메모리 낭비가 심해질 수 있음. ∴ O(1) 시간 안에 탐색을 끝내면서 키를 변환하여 배열의 인덱스로 사용하는 방법인 "해싱" 키(key) 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 ..

Disjoint Set DisJoint Set이란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 - 즉, 공통 원소가 없는 "상호 배타적"인 부분집합들로 나눠진 원소들에 대한 자료구조 - Disjoint Set=서로소 집합 자료구조 Union-Find Union-Find란? Disjoint Set을 표현할 때 사용하는 알고리즘 -집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현 -아래의 세가지 연산을 이용하여 Disjoint Set을 표현 Union-Find의 연산 - make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. - union(x,y) x가 속한 집합과 y가..

탐색이란? 여러개의 가죠 중에서 원하는 자료를 찾는 작업 -탐색을 효율적으로 수행하는 것은 매우 중요 -탐색키(search key) 항목과 항목을 구별해주는 키(key) -탐색을 위하여 사용되는 자료구조 배열, 연결리스트, 트리, 그래프 등 순차탐색 -탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법 : 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사 -평균 비교 횟수 탐색 성공 : (n+1)/2번 비교 탐색 실패 : n번 비교 -구현 int sequentialSearch(int list[], int key, int low, int high) { for (int i = low; i 원소들을 모두 이동시켜야 함. 이진 탐색 트리는 매우 빠르게 삽입/삭제 수행 삽입,삭제가 빈번히 이루어진다면 이진탐색..

들어가기 전에 2021/02/24 - [Algorithm/자료구조] - [자료구조] 그래프 [자료구조] 그래프 그래프(Graph) : 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조 ex) 지하철 노선도, 지도, tree(선형자료구조들이나 트리를 그래프의 한 종류로 볼 수 있다.) 그래프 구성 그래프 hohodu.tistory.com 그래프 탐색 - 그래프의 가장 기본적인 연산 시작 정점부터 차례대로 모든 정점들을 한 번씩 방문 많은 문제들이 단순히 탐색만으로 해결됨 ex) 도로망(특정 도시에서 다른 도시로 갈 수 있는지 여부 , 전자회로(특정 단자와 다른 단자의 연결 여부 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) - 한 방향으로 갈 수 있을 때까지 가다가..

그래프(Graph) : 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조 ex) 지하철 노선도, 지도, tree(선형자료구조들이나 트리를 그래프의 한 종류로 볼 수 있다.) 그래프 구성 그래프는 G(V,E)로 표시 - 정점(vertices) 또는 노드(node) 여러가지 특성을 가질 수 있는 객체 의미 V(G) : 그래프 G의 정점들의 집합 - 간선(edge) 또는 링크(link) 정점들 간의 관계 의미 E(G) : 그래프 G간의 간선들의 집합 그래프의 종류 - 무방향 그래프 간선을 통해서 양방향으로 갈 수 있음 (A,B)로 표현 (A,B)=(B,A) - 방향 그래프 간선을 통해서 한쪽 방향으로만 갈 수 있음 일방통행 길 로 표현 ≠ - 가중치 그래프 네트워크(network)라고도 함 간선에..

들어가기 전에 분할 정복식 알고리즘 : 하향식 해결법으로서, 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다. ( ex)피보나치 알고리즘의 재귀) 동적계획 상향식 해결법을 사용하여 알고리즘을 설계하는 방법이다. 이 방법은 분할정복식 방법과 마찬가지로 문제를 나눈 후에 나누어진 부분들을 먼저 푼다. 그러나 이미 풀어서 답을 알고 있는 부분의 결고가 다시 필요한 경우에는 반복하여 계산하는 대신에 이미 계산된 결과를 그냥 사용한다. -> 작은 문제의 답을 저장했다가 사용 개발 절차 1. 문제의 사례에 대해서 해답을 주는 재귀 관계식(recursive property)을 정립한다. 2. 작은 사례를 먼저 해결하는 상향식 방법으로 문제의 사례를 해결한다. 예제1) 피보나치 수 구하기 -분할..

1. sort 헤더파일 : sort(start,end)를 이용하여 [start,end)의 범위에 있는 요소를 오름차순(default)으로 정렬해주는 함수이다. 퀵 정렬을 기반으로 합수가 구현되어 있고, 평균 시간 복잡도는 O(nlogn)이다. sort(arr, arr+n); //배열 sort(v.begin(), v.end()); //벡터 sort(v.begin(), v.end(), compare); //사용자 정의 함수 사용 sort(v.begin(), v.end(), greater()); //내림차순 (Descending order) sort(v.begin(), v.end(), less()); //오름차순 (default = Ascending order) 출처: https://blockdmask.tis..

정렬이란? 물건을 크기순으로 오름/내림차순으로 나열하는 것 정렬 알고리즘 종류 삽입 정렬(Insertion Sort) 선택정렬(Selection Sort) 버블 정렬 셀 정렬 합병 정렬(Merge Sort) 퀵 정렬(Qiuck Sort) 힙 정렬(Heap Sort) ->우선순위 큐 기수 정렬 계수 정렬 1. 삽입 정렬(Insertion Sort) 정렬되어 있는 부분에 새로운 레코드(정렬의 대상)를 올바른 위치에 삽입하는 과정 반복 구현 //오름차순으로 정렬 void insertionSort(int A[], int n) { for (int i = 1; i = 0 && A[j] > key; j--) A[j + 1..

1. 스택 스택의 개념 후입 선출(LIFO,Last In First Out)방식으로 가장 최근에 들어온 데이터가 가장 먼저 나간다. 스택의 연산 push(x) : 주어진 요소 x를 스택의 맨 위에 추가한다. pop() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다. isEmpty() peek() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다. isFull() size() 스택의 사용 사례 함수호출, Undo기능, 괄호검사, 계산기, 미로탐색 c++ STL stack 기본 사용법 헤더 : 선언 : stack 변수명 ex) stack st; 추가 및 삭제 -st.push(element) :top에 원소를 추가 -st.pop():top에 있는 원소를 삭제 조회 -s..