본문 바로가기

분류 전체보기114

자바의 자료구조 - 덱 : DEque deque는 양쪽 끝에서 삽입과 삭제가 모두 가능하다. Double Ended Queue라는 뜻을 갖고 있다. Stack과 Queue를 Deque의 특수한 예시라고 생각해도 좋다. : 시간복잡도 원소의 추가가 O(1) 원소의 제고가 O(1) 제일 앞/뒤의 원소확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. : C에서는 직접 구현하는 내용이 있었지만, 자바에서는 기본 타입중에 있기때문에 직접사용할 수 있다. 2021. 11. 20.
자바의 자료구조 - 연결리스트 : 연결리스트는 순차적으로 연결된 자료구조이다. A, B, C가 있다면 A는 B의 위치를 기억하고, B는 C의 위치를 기억하는 구조이다. A만 알고있으면, 순서대로 나아가기만 하면 전체를 알 수 있다. 다만 이 방식으로만 다른 원소들에 접근할 수 있고, B나 C에 바로 접근할 수는 없다. : 연결리스트 성질 1. k번째 원소를 확인 / 변경하기위해 O(k)가 필요 2. 임의의 위치에 원소를 추가 / 임의의 위치의 원소를 제거 O(1) 3. 원소들이 메모리상에 연속해 있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결리스트에서는 임의의 위치에 원소를 추가하거나 임의 위치 원소 제거가 O(1)이다. 배열과 비교시 가장 큰 차이가 있는 성질이고, 연결 리스트의 장점이다. 이는 밑에서 좀 더 .. 2021. 11. 20.
자바의 자료구조 - Heep 역시나 순서는 이상한 기분이지만 크게 지장은 없을 듯 하다. 곱셈을 배우고 덧셈을 배우면 아 이렇게 곱셈에 쓰였구나 할 수도 있으니 앞으로도 나오는 자료구조 포스팅을 참고하면 좋을 듯 하다. : Heep은 우선순위 개념을 Queue에 이용하여 만들어진 자료구조이다. 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터를 먼저 배출한다. 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다. 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내기 위한 자료구조이며, 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하.. 2021. 11. 19.
자바의 자료구조 - Stack 순서가 좀 이상해진 기분이 들지만 이번 자료구조는 Stack이다. 스택은 총의 탄창을 생각해보면 구조가 매우 흡사하다. 탄창을 입구로 총알을 넣고, 가장 먼저 넣은 총알이 가장 마지막에 발사되게 된다. 이러한 선입후출의 자료구조가 Stack이다. ( First In Last Out ) 단순한 구조이기 때문에 Stack이 갖는 특징이 있는데, 1. 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다. 2. 하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다. 3. 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다. : 스택의 사용 : 재귀 알고리즘 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다. 재귀함수를 빠져 나와 퇴각 검색(backtrack)을.. 2021. 11. 19.
자바의 자료구조 - Map : Map은 Collection 인터페이스와 별개이지만, json형식과 유사한 key-value 자료구조로 자주 사용되는 구현체이다. 사전과 같은 형태의 자료구조로, ( 사전과 달리 순서는 없다. ) 중복된 key를 가질 수 없고 각 key는 오직 하나의 value에만 mapping될 수 있다. Map 인터페이스를 구현한 클래스는 HashMap, TreeMap, LinkedHashMap, Hashtable 이 있다. Hashtable은 null을 허용하지않고, HashMap은 null을 허용한다. 심지어 HashMap은 Key, Value에 모두 null이 허용되고, HashTable은 Key, Value에 모두 null이 불가하다. ( 타 ide는 모르겠지만, 이클립스의 경우 코딩에 오류는 발생하지 않.. 2021. 11. 19.
자바의 자료구조 - 이진 탐색 트리, 레드 블랙 트리 : 이진탐색트리(Binary Search Tree) 이진 탐색 트리에는 자신의 왼쪽 서브 트리에는 현재 노드보다 key값이 작은 것, 오른쪽 서브 트리에는 현재 노드보다 key값이 큰 것, 을 배치해 탐색이 가능. 이진 탐색 트리에서 중위순회를 하게되면, 오름차순으로 정렬된 순서로 key값을 얻을 수 있다. 이렇게 되어 있을때, 중위순회란 7->3->8->1->9->4->10->0->11->5->2->6 이런 순서로 참조하는 것을 말하고, 왼쪽에는 현재보다 key값이 작은 원소, 오른쪽에는 현재보다 key값이 큰 원소가 위치하기에 오름차순으로 정렬되게 된다. 그래서 탐색의 시간 복잡도는 O(h) ( h = 트리의 높이 ) 가 된다. : 레드 블랙 트리 이 역시도 이진 탐색 트리의 일종이다. 그런고로 동일.. 2021. 11. 19.
자바의 자료구조 - Set 원소 간 순서가 없고, 데이터 유일성을 가지는 자료구조. ( 데이터 유일성으로 인해 null 값도 하나만 가질 수 있다. ) 주머니 형태의 저장공간이라고 상상하면 좋다. 인덱스역시 존재하지 않으며, 값을 추가하거나 삭제할 때에는 추가 혹은 삭제하고자 하는 값이 Set 내부에 있는지 검색 한 뒤 추가나 삭제를 해야 하므로 속도가 List구조에 비해 느리다. Set은 List와 공간을 증가시키는 방식이 다르다. List는 한칸씩 index를 증가시키며 공간을 증가시키지만, Set은 저장용량을 약 2배씩 증가시키게 된다. 그렇기 때문에 과부하를 일으킬 수 있어서 저장할 크기을 알고있다면 미리 크기를 지정해주는 것이 좋다. 구현체로는 HashSet, TreeSet, LinkedHashSet 3가지가 있다. : .. 2021. 11. 18.
자바의 자료구조 - Queue Queue : 데이터를 처리하기 전에 잠시 저장하고 있는 선입선출 ( First In First Out : FIFO ) 의 자료구조이며 tail에서 원소를 추가하고, head에서 원소를 삭제 ( 배출 ) 한다. 자바에서 Deque 인터페이스는 ArrayDeque와 LinkedLIst 클래스들로 구현된다. : 선언 Queue queue = new LinkedList(); : 메소드 .add(n) : n을 큐에 삽입 int element = queue.remove() : 큐의 값을 배출 ( 큐에서는 삭제됨 ) .peek() : 가장 밖의 값을 표현 .poll() : remove와 동일 이렇게 확인해 볼 수 있다. 이전 글들을 보면 직관적으로 알 수 있게 그려놓은 것이 있는데 휴지심 같은 원통형을 생각해보면 .. 2021. 11. 18.
자바의 자료구조 - List 참고하던 블로그에서는 C언어 기반으로 자료구조를 설명해서 자바의 자료구조는 따로 찾아보았다. 우선 자료구조란? - 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 형태. - 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨 - 자료의 효율적인 관리는 프로그램의 수행 속도와 밀접한 관련이 있음. - 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로, 자료구조에 대한 이해가 중요함. ( 출처 : https://soliloquiess.github.io/study/2021/03/20/java_%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0.html ) 1) Type[] (변수명) 기본적인 타입을 가지고 만드는 배열이다. 선언시 null 혹은 크기를 .. 2021. 11. 18.
공간복잡도 참고자료 : https://blog.encrypted.gg/922 공간복잡도 - 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 이 크기는 메모리의 크기를 의미한다. 참고 : 512mb = 1.2억개의 int ( int 1개가 4바이트 ) 참고 : char 자료형은 1byte = 8bit ( c언어 기준, 자바는 2byte ) N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1) 예상한 코드가 제한이상의 메모리를 요한다면 다른 방법을 고민해보도록 하자. 이러한 1byte는 0,1 즉 이진수가 하나 들어가는 공간이다. int는 byte의 공간을 갖는데 2^31-1개의 숫자를 표현할 수 있다. 2147483647로 21억 정도의 숫자이다. 즉, 이를 벗어난 숫자를 int로 .. 2021. 11. 17.

티스토리툴바