자료구조

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

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

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

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..