Computer Science/자료구조6 자료구조 hash 해시 테이블(Hash Table) 해시 테이블은 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조이다. 연관배열 구조(associative array)란, 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다. 연관배열 구조는 다음의 명령을 지원한다. 키(key)와 값(value)이 주어졌을 때, 연관 배열에 그 두 값(key & value)을 저장하는 명령 키(key)가 주어졌을 때, 연관되는 값(value)을 얻는 명령 키(key)와 새로운 값(value)이 주어졌을 때, 원래 키에 연관된 값(value)을 새로운 값(value)으로 교체하는 명령 키(key)가 주어졌을 때, 그 .. 2022. 4. 22. [CS 면접] 자료구조 정렬의 종류, 정렬의 차이 정렬(Sort) 정렬이란 : 데이터들을 일정한 순서대로 열거하는 알고리즘을 말한다. 정렬의 종류 : 대표적으로 거품정렬(Bubble Sort) , 선택정렬(Selection Sort) , 삽입정렬(Insertion Sort), 퀵정렬(Quick Sort), 합병정렬(Merge Sort) , 힙정렬(Heap Sort) 등이있다. 거품정렬 (Bubble Sort) 인접하는 두 항을 축차교환한다 원리는 간단하지만 교환 횟수가 많다. 최악일때 O(n^2)으로 swap 발생한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; void bubbleSort(vector &arr) { for (int i = arr.size()-1; i >.. 2022. 3. 24. [CS 자료구조] 그래프와 트리의 차이 그래프(Graph) 다양한 종류의 물리적 구조를 나타낼 수있는 수학적 비선형 데이터 구조 그래프의 정점(vertex,node)은 점 또는 원으로 표시되고 모서리는 호 또는 선 세그먼트로 표시 정점의 집합이 V, 변의 집합이 E인 그래를 G=(V,E)라고 표현 두점 u,v를 연결한 변 Edge는 E (u, v)로 표시 종류 무향 그래프와 ,유향그래프로 나뉘어 짐 변 에는 다양한 속성이 있음 대표적으로 비용(cost)가 존재 특징 인접한 정점 - 정점 a는 정점 b에 인접합니다 (a, b) 또는 (b, a). 경로 - 임의의 정점 w의 경로는 인접한 정점 시퀀스입니다. 사이클 - 첫 번째와 마지막 버텍스가 동일한 경로입니다. Degree - 정점에 입사하는 다수의 가장자리입니다. 연결된 그래프 - 임의의 정.. 2022. 3. 7. [자료구조] CS 공부 스택 vs 큐 (스택으로 큐구현 , 큐로 스택구현) 스택(Stack) 스택stack은 push 와 pop이라고 하는 두 종류의 조작이 가능 한 데이터 구조 LIFO(Last in First Out) : 마지막에 넣은 요소가 가장 먼저 나온다 push : 스택의 가장 윗부분에 데이터를 쌓는 조작 기능 pop : 스택의 가장 윗부분 데이터를 빼내는 조작 기능 스택을 조작하는 STL 라이브러리를 사용하는 언어는 상당히 많지만 c++ 라이브러리를 이용하여 알려주고자한다 stack::pop : 가장 위에서 요소를 빼는 조작 stack::push : 가장위에서 요소를 넣는 조작 stack::top : 가장위에있는 요소를 확인하는 조작 stack::empty : 데이터가 존재하는지 stack::size : 데이터의 사이즈를 확인 1 2 3 4 5 6 7 8 9 10 .. 2022. 2. 24. 이전 1 2 다음
