꿈꾸며 개발하기

해시 테이블(Hash Table) = 해시맵, 해시표 해시함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 색인(index)삼아 데이터의 값(Value)를 키(key)와 함께 저장하는 자료구조를 해시 테이블 이라고 함 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot) 이라고 함 해시테이블(= 해시맵, 해시표)은 키를 통해 해당 데이터에 빠르게 접근이 가능함. 해시 충돌 해시 테이블에 같은 공간에 서로 다른 값을 저장하려는 경우 -> 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우 해시 충돌이 일어나 원하는 결과를 얻을 수 없음 해시 충돌을 해결하는 방법에는 선형탐사법, 제곱탐사법, 이중해싱, 분리연결법 등 방법으로 해결할 수 있음 이와 관련된 내용은 추후에 정리할 ..

Deque. Double-ended queue 양쪽에서 삽입과 삭제가 모두 가능한 자료구조 Java에서 Deque는 Java.util 패키지에 있는 Queue 인터페스의 하위 유형으로 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있음 양 쪽 끝에 요소를 삽입하고 삭제할 수 있는 데이터구조를 지원 FIFO, LIFO 모두 사용 가능함(스택과 큐를 합친 것) Deque는 Palindrome Checker , Song Playlist 등에서 사용 Deque 주요 메서드. HTML 삽입 미리보기할 수 없는 소스 Deque 관련 코딩테스트 문제. 프로그래머스 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 ..

Queue. 큐는 대기열이라고도 하며 선입선출(First In First Out) 자료구조 입니다. 먼저 들어온 데이터가 먼저 나가는 구조로 쉽게 말해 선착순을 떠올리면 됩니다. 먼저 온 사람은 먼저 집에가세요.!!!!!!! 입력 순서대로 데이터 처리가 필요할 때 사용하며 프린터 출력 대기열 등과 비교 됩니다. 자바에서는 Queue는 인터페이스로 정의되어 있고 Priority Queue 등 구현되어 있으나 ArryList나 LinkedList 클래스를 활용하여 구현하는 경우가 있음 큐 데이터 추가 큐 데이처 삭제 Queue 주요 메서드. HTML 삽입 미리보기할 수 없는 소스 ArrayList로 Queue 구현하기. HTML 삽입 미리보기할 수 없는 소스

시작하며. 선형 / 비선형 자료구조 공부하면서 이해 안되는 부분도 많고 머리속에서 두둥실 떠다니는 개념들을 자리잡기 위해 자료구조란 무엇이고 어떻게 분류되는지 어떤 것들이 있는지 간단하게라도 정리하고 넘어가려 한다. 비선형 자료구조는 아직 모르는게 많아서 제대로 정리가 안된거 같다. 자료구조란. 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨. 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 해 자료구조에 대한 이해가 중요 자료구조 형태에 따른 분류. 선형 자료구조 데이터 요소가 순차적 또는 선형으로 배열되고 일대일 관계에 있으며 각 요소..

Stack. 자료 구조 중 하나인 Stack은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조 후입선출 자료 구조 Last In First Out : LIFO 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용 ex) 함수 콜 스택, 수식 계산, 인터럽트 처리, 웹브라우저 앞으로 / 뒤로 자바에서 스택을 사용하기 위해서 java.util 패키지에서 제공하는 Stack을 사용하면 된다. 기본 Stack 클래스 외에도 ArrayList로도 구현해보자. Stack 한장으로 정리해보기. Stack 주요 메서드. import java.util.Stack; public class Main { public static void main(String[] args) { // Stack 선언 Stack st..

LinkedList. 선형으로 자료를 관리, 자료가 추가 될 때마다 메모리를 할당받고, 자료는 링크로 연결되어 물리적 위치와 논리적 위치가 다를 수 있음. 연결리스트의 각 요소는 다음 주소값을 가리키는 주소값을 가짐 물리적인 메모리가 떨어져 있어도 논리적으로는 앞뒤 순서가 있음. 같은 List 인터페이스를 구현한 ArrayList에 비해 중간에 자료를 삽입하고 제거하는데 시간이 적게 걸림 크기를 동적으로 증가할 수 있음 연결리스트의 각 요소는 요소의 자료와 다음 주소를 저장하는 부분으로 구현 또한 스택이나 큐에서 다양하게 활용할 수 있음 배열과 연결리스트의 차이점. 자료의 변동(수정, 삭제) 등이 많다면 연결리스트 사용 거의 없다면 배열을 사용하는게 좋다. 연결리트스 데이터 추가. 연결 리스트 가장 앞에..