꾸준함의 기록

[자료구조] 링크드 리스트 정리 및 구현 목차 1. 정리 2. 구현 정리 개념 1) 링크드리스트 기본 리스트가 물리적으로 연속된 메모리에 연결되어있는 것과 달리, 각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해 연결되는 리스트이다. 2) 노드 링크드 리스트에서의 원소는 다음 원소에 대한 주소를 저장해야하기 때문에 단위로 저장되는데 이를 노드라고 한다. 노드는 원소의 값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드로 구성된다. 종류 1. 단순 링크드 리스트 노드가 다음 노드와 연결되는 기본적인 링크드 리스트이다. 첫번째 노드를 HEAD, 마지막 노드를 TAIL이라고 한다. 2. 원형 링크드 리스트 마지막 노드가 첫번쨰 노드를 가리키게 하여 리스트 구조를 원형으로 만든 것이..

[자료구조] 배열 구현하기 c++ 배열 구현 코드 #include using namespace std; class Array { private: int* arr; // 배열 size = size; arr = new int[size]; // size를 동적으로 for (int i = 0; i = size) { cout = size) { cout

[자료구조] 힙(Heap)과 완전 이진 트리(Complete binary tree) 개념 및 구현 목차 1. 힙 2. 완전 이진 트리 3. 힙 구현 힙(Heap) 특징 1. 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. (*우선순위 큐: 데이터들이 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 나감.) 2. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다 -큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 3. 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다 힙 트리에서는 중복된 값을 허용한다 ( 이진 탐색 트리에서는 중복된..

[자료구조] 해시맵(Hash Map) 해시 목차 1. 해시맵 2. 해시와 해시 함수 3. capacity & load factor 4. 구현 해시맵(Hash Map) 개념 맵이란 것은 키(Key) 와 값(Value) 두 쌍으로 데이터를 보관하는 자료구조. (키는 맵에 오직 유일하게 있어야함 ,값은 중복 상관 X). 키와 값을 매핑하기 위해 해시라는 것을 사용한다. 한편,HashMap은 HashTable과 달리 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다. (해시 테이블과의 비교는 사실 의미 없음) 특징 java 8 Has..