Java자료구조7 [Data Structure / Java] ✒️ HashMap HashMap이란 HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션이다. Map 인터페이스를 상속하고 있기 때문에 Map의 성질을 그대로 가지고 있다. Map은 key와 value로 구성된 Entry객체를 저장하는 구조를 가지고 있는 자료구조이다. 여기서 key와 value는 모두 객체이다. HashMap은 해싱(Hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보인다. HashMap은 Hash function을 통해 key와 value가 저장되는 위치를 결정하므로, 사용자는 그 위치를 알 수 없고, 삽입되는 순서와 들어 있는 위치 또한 관계가 없다. HashMap 사용법 선언 HashMap map1 = new HashMap();//HashMap생성 .. 2022. 8. 18. [Data Structure / Java] ✒️ Tree(트리) Tree란? 비선형(Non-Linear)자료 구조이다. 이러한 구조는 단일 방향으로 각각의 데이터들이 연결되거나 나열된 것이 아니라 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조로 설계될 수 있다. 선형 구조와 비-선형 구조의 차이 Point 선형 구조 비-선형 구조 데이터 저장 순차적으로 각 데이터를 순회할 수 있도록 저장 데이터들이 계층적으로 연결되어 저장 수준(Level) 단일 수준(Level)에서 모든 데이터를 저장 복수 수준(Level)에서 데이터를 저장 구현 복잡도 구현이 쉬움 구현이 어렵고 이해도 난해 순회 단일 동작으로 모든 데이터 순차적 순회 가능 데이터 순회에 복수의 동작 필요 메모리 활용 메모리 공간 활용 효율성 낮음 메모리 공간을 매우 효율적으로 활용 시간 복잡도 저장 공.. 2022. 8. 16. [Data Structure / Java] ✒️ Graph(그래프) 그래프란? 그래프는 정점과 간선으로 이루어진 자료구조이다. 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수도 있다. 그런 면에서 트리는 그래프의 일종인 셈이다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활에서 다양한 예를 그래프로 표현할 수 있다. 대표적으로 지하철 노선도, 도심의 도로 등이 있다. 이런 식으로 활용할 수 있는 방법이 많기에 문제도 다양하게 출제를 할 수 있다. 그래프는 알고리즘에서 굉장히 많이 사용된다. 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다. .. 2022. 8. 16. [Data Structure / Java] ✒️ Vector Vector란? Vector는 ArrayList와 동일한 내부구조를 가지고 있다. ArrayList와 마찬가지로 Vector내부에 값이 추가되면 자동으로 크기가 조절되며 그다음 객체들은 한 자리씩 뒤로 이동된다. 하지만 Vector와 ArrayList의 한 가지 다른 점이 있는데 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드들이 실행할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있다. Vector의 단점 (ArrayList와 비교) Vector는 항상 동기화된다는 장점이자 단점을 가지고 있다. 스레드가 1개일때도 동기화를 하기 때문에 ArrayList보다 성능이 떨어.. 2022. 8. 15. [Data Structure / Java] ✒️ Stack, Queue Stack이란? Stack이란 쌓아 올린다는 것을 의미. 따라서 Stack 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. Stack의 특징 Stack은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고,Top으로 정한 곳을 통해서만 접근할 수 있다.가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.Stack에서 자료를 삭제할 때에도 top을 통해서만 가능하다. 데이터 넣기(Stack에서 top을 통해 삽입): push() 데이터 최상위 값 빼기(top을 통한 삭제): pop() 비어있는지 확인: isEmpty() 꽉 차 있는지 확인: isFull() 따라서 Stack.. 2022. 8. 15. [Data Structure / Java] ✒️ Map Array는 index로 빠르게 읽기는 좋은데 유연하지 못하고 ... List는 유연하기는 한데 index로 빠르게 읽기는 못하고... 유연하면서도 빠르게 읽어내는 방법이 없을까? Map Key와 Value로 이루어진 자료구조. 순차적으로 메모리에 데이터를 저장하는 Array와 List와는 달리 Key와 Value로 구성되어 있다. hashing: Key를 범위(배열 크기)에 맞게 적절히 겹치지 않는 index로 변경한다. hash function: hashing의 기능을 수행함, key값을 넣으면 hash값으로 변환하여 bucket의 index로 사용된다. bucket: Map의 Array hash collision: 해쉬 충돌, 이미 존재하는 key값에 다른 key값으로 같은 hash의 index를 .. 2022. 8. 12. 이전 1 2 다음
