자료구조

[자료구조] 해시테이블

해시테이블 (HashTable) 이란? - 해시함수를 사용하여 변환한 값을 색인(index)로 삼아 키(KEY)와 값(VALUE)를 대응시켜 저장하는 데이터 구조 - 키를 통해 해당 데이터에 빠르게 접근이 가능하다. - 해시 값 : 해시 테이블의 Index 해싱이란? - 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 해시테이블의 연산 ● search() - 해시테이블 내 데이터를 탐색한다. ● insert() - 해시테이블에 (값, 데이터) 추가 ● delete() - 데이터 삭제 ** HashTable과 HashMap 차이 HashTable 해시테이블 HashMap 해시맵 공통점 둘 다 Map 인터페이스를 구현한 것 차이점1 : Thread-safe O (멀티 스레드 환경에서 우수)..

[자료구조] 데크

데크 (Dequeue) 란? - 양쪽에서 삽입과 삭제가 모두 가능한 구조 - Double-ended-queue의 줄임말 - 입력 제한 데크 : 한 쪽 입력을 제한한 데크 (Scroll) - 출력 제한 데크 : 한 쪽 출력을 제한한 데크 (Shelf) 데크의 연산 ● addFirst() : front 부분 입력 ● addLast() : last 부분 입력 ● removeFirst() / removeLast() : 출력 위 메서드 말고도 poll, offer, push, pop 모두 사용 가능하다. 1) 데크의 구현 아래와 같이 ArrayDeque를 통해 Deque를 구현할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import..

[자료구조] 큐

큐 (Queue) 란? - 입력 순서대로 데이터 처리가 필요할 때 사용하는 선입선출 구조 (FIFO) - BFS (그래프 넓이 우선 탐색), 프린터 출력 대기열과 같은 상황에서 사용 큐의 연산 ● enqueue() : 큐 맨 뒤에 데이터 추가 ● dequeue() : 큐 맨 앞쪽의 데이터 삭제 위 연산 뿐만 아니라, poll(), peek(), contains(), size(), isEmpty()도 사용가능하다. 큐의 특징 ● 한 쪽 끝은 front로 정하여 삭제 연산만 수행한다. ● 다른 한 쪽 끝은 rear로 설정하여 삽입 연산만 수행한다. ● ArrayList와 배열로 구현 가능하다. 1) 큐의 구현 아래 구현한 것과 같이, LinkedList로 생성하여 Queue의 다양한 메서드를 사용해보고 결과..

[자료구조] 스택

스택 (Stack) 이란? - 마지막에 들어온 데이터가 먼저나가는 후입선출 자료구조 (LIFO) - 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용 스택의 연산 ● push() : 스택의 가장 윗부분에 추가한다. ● pop() : 스택에서 가장 윗부분에 있는 항목을 제거한다. ● peek() : 스택의 가장 위에 있는 항목을 출력 및 반환한다. ● isEmpty() : 스택이 비어 있을 경우, true를 반환한다. 위 메서드 뿐만 아니라, contains(), size(), empty()도 사용 가능하다. 스택의 구현 아래와 같은 과정으로 직접 push, pop, peek, contains 등 사용해보며 결과를 확인해 볼 수 있다. 스택의 경우, 괄호 짝을 검사하거나 후위표기법 연산에서 주로 활용..

[자료구조] 연결리스트

연결리스트 (LinkedList)란? - 데이터를 링크로 연결해서 관리하는 자료구조 - 기본 구조 : 노드 ( 값 + 포인터 ) - 자료의 순서는 정해져 있지만, 메모리 상 연속성이 보장되지는 않음 1. 데이터 공간을 미리 할당할 필요 없다. 2. 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제가 용이하다. 1. 연결 구조를 위한 별도의 데이터 공간이 필요 -> 상대적 느림 2. 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요! [ 데이터 추가 ] 추가할 데이터를 담을 노드 생성 ↓ 링크 연결 작업 ↓ head 이전 작업 (제일 앞으로) [ 데이터 삭제 ] 삭제 대상 노드 지정 ↓ head 이전 작업 ↓ delete_node 삭제 ( 링크도 함께 삭제해주기 ) 유형1. 단순 연결 리스..

[자료구조] 조합

조합 (Combination)이란? - 순서 없고, 중복 허용하지 않음 - 서로 다른 n개 중에서 r개를 선택하는 경우의 수 - nCr // 조합 int n = 4; int r = 2; int pResult = 1; for (int i = n; i >= n - r + 1; i--) { pResult *= i; } int fResult = 1; for (int i = 1; i 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 X, 중복 x)의 각 결과를 출력하시오 순열과 마찬가지로, visited를 이용한 구현을 사용한다. (DFS) 해당 코드는 아래와 같다. public class Practice { void combination(int[] arr, boolean[] visited, i..