Hash Table 자료 구조 해시 테이블이란 무엇인가? 알아보자 Hash 먼저, 해시(Hash) 다. 해시(해시 함수)는 임이의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 의미한다. 아무리 큰 숫자, 작은 숫자를 넣더라도 정해진 크기의 숫자가 나온다. 은행 금고 (은행에 어떤 것을 보관하더라도 동일한 모양의 열쇠를 받는것처럼) 이러한 해시 함수를 적용해 나온 고정 길이의 값을 해시값, 해시 코드, 해시섬 등으로 부른다. 해시 함수는 입력값의 범위가 출력값의 범위보다 넓기에 서로 다른 입력값에도 동일한 값이 출력되는 경우가 존재한다. 이러한 경우 충돌되었다고 하며 연결 리스트로 연결하는 방식으로 해결한다. Hash Table 해시 테이블이란 해시 함수의 특징을 이용해 변환값을 색인으로 삼아 KEY-VALUE를 저장하는 자료구조를 의미한다. KEY를 알고 있다면 빠르게 VALUE를 저장/삭제/조회할 수 있다. 하지만 KEY는 순서가 없다. 매우 빠른 속도…

트리 Tree 특징 트리는 노드와 간선으로 이루어진 데이터 구조를 의미한다. 그림과 같이 하나의 뿌리(루트)부터 시작해 간선으로 연결된 여러 갈래의 노드 가지가 뻗어있는 구조이다. 두 노드가 상하 관계를 갖고 있을때, 서로 부모-자식 관계라 하며, 루트에서 가까운 노드를 부모 노드, 먼 쪽을 자식 노드라고 한다. 이진 탐색 트리 Binary Search Tree 특징 이진 탐색 트리는 부모 노드가 특정 기준에 의해 최대 2개의 자식 노드를 갖는 특징을 보이는 트리다. 노드의 정렬이 특정 순서로 되어있어 탐색하기 쉽다. 그림은 왼쪽 자식 노드가 부모보다 작고 오른쪽 자식 노드가 부모보다 큰 기준에 의해 분류되어있다. 부모 노드를 확인하고 조건에 맞는 한쪽 노드를 확인하기에 탐색을 절반으로 줄일 수 있다. 한쪽으로 쏠려있는 트리가 될 수 있기에 기준점이 되는 루트를 잘 정하는게 중요하다. 트리 순회 트리를 순회하는 여러가지 방법이 있지만, BFS와 DFS가 가장 유명하고 널리 쓰인다.…

스택 Stack 특징 스택은 LIFO (Last In First Out / 후입선출) 의 특징을 가진 자료 구조다. 위 그림과 같이 순서대로 쌓아 올려진 형태이다. 데이터 입력은 push, 데이터 출력은 pop 이라 한다. 예시 최근 추가된 데이터부터 순차적으로 사용되기에 ctrl Z 나 브라우저 방문 기록과 같이 최근 동작을 기억하고, 사용하는 경우에 주로 사용한다. 큐 Queue 특징 큐은 FIFO (Fist In First Out / 선입선출) 의 특징을 가진 자료 구조다. 데이터 입력은 Enqueue, 데이터 출력은 Dequeue 라 한다. 예시 어떤 작업을 순서대로 실행하기 위해 대기시킬 때 (like 프린트 대기열) 사용한다. 스택 Stack 특징 예시 큐 Queue 특징 예시

이중 연결 리스트 특징 이중 연결 리스트는 단일 연결 리스트에 반대 방향으로 연결이 하나 추가된 개념이다. 단일 연결 리스트는 다음 노드만 연결했다면, 이중 연결 리스트는 이전 노드까지 연결한다. 그렇기에 양방향에서 탐색이 가능하다. [ 20 ➡ 10 ➡ 1 ➡ 5 ➡ 9 ] [ 20 ⬅ 10 ⬅ 1 ⬅ 5 ⬅ 9 ] 양방향 탐색은 특정 인덱스의 데이터를 가져오거나 노드를 탐색할 때 큰 장점이 된다. 단점 하지만 연결을 한 번 더 해야하기에 단일 연결 리스트보다 메모리 소모가 크다. 그리고 구현이 조금 더 복잡해진다. 그렇다해도 장점이 더 크기에 단일 연결 리스트보다는 이중 연결 리스트를 사용한다. 추가 단일 연결 리스트와 비슷하다. 이전 노드와의 연결만 추가하면 된다. 삭제 단일 연결 리스트와 비슷하다. 이전 노드와의 연결만 해제하면 된다. 구현 이중 연결 리스트 특징 단점 추가 삭제 구현

연결 리스트 Linked List 배열 연결 리스트 장점 인덱스를 통한 빠른 접근 삽입과 삭제가 용이 단점 삽입과 삭제 중간 데이터 삭제시 공간 낭비 발생 임의 접근이 불가능해 느린 탐색 용도 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 삽입과 삭제 연산이 요구되고, 검색이 적을 때 단일 연결 리스트 단일 연결 리스트는 각 노드가 다음 노드를 가리키며 한 방향으로 연결되어 있는 자료 구조이다. 연결 관계를 지속하는 것에 주의하면 데이터 추가와 삭제가 어렵지 않다. 추가 새로운 노드를 생성하고, 새 노드가 그 다음 노드를 가리키게 한다. 새 노드의 이전 노드가 새 노드를 가리키게 한다. 삭제 삭제할 타겟 노드를 찾는다. 타겟 노드의 이전 노드가 타겟 노드가 가리키던 노드를 가리키게 한다. 타겟 노드의 포인터가 아무것도 가리키지 않게 한다. 구현 연결 리스트 Linked List 단일 연결 리스트 추가 삭제 구현