DEVLOG DEVLOG

힙이란? 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 완전 이진 트리로 구현된 자료구조입니다. 부모 노드가 가진 값이 자식 노드의 값보다 작은 힙을 Min Heap, 부모 노드가 가진 값이 자식 노드보다 큰 힙을 Max Heap 이라고 합니다. 이때 부모노드의 값은 자식 노드보다 무조건 작거나 커야합니다. 위 이미지는 Max Heap의 예시입니다. 루트 노드의 값이 가장 크고 리프 노드를 제외한 자식 노드들 또한 본인의 자식 노드 보다 큰 값을 가지고 있습니다. 이러한 특성을 활용하여 가장 크거나 가장 작은 값을 찾아내기에 적합한 자료구조라고 볼 수 있습니다. 힙의 동작 방식 데이터 삽입 힙은 완전 이진 트리이기 때문에 최하단 노드부터 데이터가 채워집니다. 추가된 노드와 부모 노드의 값을 비교 후 자식..

리스트란? 리스트는 데이터를 나란히 저장하고 중복된 데이터의 저장을 허용하는 자료구조입니다. 순서의 개념이 없는 집합과는 달리 순서, 위치를 갖고 있습니다. 스택, 큐 또한 리스트를 활용하여 구현된 자료구조입니다. 리스트의 구현 방법으로는 배열을 사용하는 순차 리스트, 메모리의 동적 할당을 기반으로하는 연결 리스트가 있습니다. 순차 리스트 순차 리스트는 배열을 기반으로 리스트를 구현한 방법입니다. 장점 데이터의 참조가 쉽다(인덱스 값으로 한번에 참조 가능) 단점 연속된 메모리 주소를 할당해야 하기 때문에 배열의 길이가 초기에 결정되어야함 삭제의 과정에서 데이터의 이동이 빈번하게 발생 시간 복잡도 데이터 탐색 인덱스를 활용하여 임의 접근이 가능하기 때문에 탐색 과정에 시간 복잡도는 O(1)입니다. 데이터 ..

해시 테이블(Hash Table) 해시 테이블은 key, value로 데이터를 저장하는 자료 구조입니다. 해시 테이블은 내부적으로 버킷(배열)을 사용하여 데이터를 저장하는데 각 key에 해시 함수를 적용하여 버킷의 고유한 index를 생성하고 이 index를 활용하여 값을 저장, 검색할 수 있습니다. value가 저장되는 장소를 버킷 혹은 슬롯이라고 명칭합니다. key에 해시 함수를 적용해 바로 버킷에 도달할 수 있어 시간복잡도는 O(1)입니다. 해시 충돌 해시 함수에는 문제점이 하나 존재하는데 해시 함수는 입력 값의 길이에 상관없이 고정된 길이의 값을 출력하기 때문에 입력 값이 다르더라도 같은 결과 값이 나오는 케이스가 발생합니다. 이를 해시 충돌(Hash collision)이라고 명칭합니다. 이를 해..

Graph란? Node와 Node를 연결하는 Edge를 하나로 모아 놓은 비선형 자료구조 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 네트워크 모델 방향성에 따라 Undirected Graph와 Directed Graph로 나누어짐 Undirected Graph 간선을 통해 양방향으로 진행 노드A와 노드B를 연결하는 간선이 존재하면 (A, B)로 표현 Directed Graph Edge에 방향성이 존재 A -> B이면 로 표현 와 는 다름 가중치 그래프(Weighted Graph) Edge에 비용이나 가중치가 할당된 그래프로 네트워크라고도함 Graph의 특징 그래프는 네트워크 모델 2개 이상의 경로가 존재 할 수 있음 root node가 존재하지 않음 부모-자식 관계가 존재하지 않음 순회는..

스택(Stack)이란? 한 쪽 끝에서 데이터를 넣고 뺄 수 있는 LIFO(Last In Fisrt Out) 형식의 자료구조 스택은 가장 최근에 스택에 추가한 데이터가 가장 먼저 제거됨 push() : 스택에 데이터를 저장 pop() : 스택에서 데이터를 꺼냄 peek() : 스택에서 가장 최근에 추가한 데이터를 반환 isEmpty() : 스택이 비어 있을 때 true 반환 활용 방안 재귀 알고리즘 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어줌 재귀함수를 빠져 나와 backtracking을 할 때는 스택에 넣어 두었던 임시 데이터를 가져옴 웹 브라우저 방문 기록 실행 취소 역순 문자열 만들기 수식의 괄호 검사 후위 표기법 계산 큐(Queue)란? 먼저 넣은 데이터가 먼저 나오는 FIF..