자료구조12 Collections와 Collection에 대하여 0. 개요 - Java를 공부하다 보면 Collections와 Collection을 반드시 만나게 된다. - 이 둘은 독립된 존재이면서 동시에 떨어질 수 없는 관계를 가지는데, 직접 파보기 전까지 이해하기가 힘들다. - 이번 포스팅에서는 Collections와 Collection의 차이점과 관계에 대해서 알아보자. 1. Collection이란? - Collection은 자료구조를 다루기 위한 기본 메서드와 반복자를 제공하는 인터페이스다. a) Collection은 Interface다. - 다음 사진은 Java 8 공식 문서의 collection에 대한 설명이다. - Collection은 Iterable을 상속받은 인터페이스다. - 보통 인터페이스는 공통된 메서드를 상속하기 위한 목적으로 작성된다. - 그.. 2022. 5. 9. 알고리즘 개념 총정리 - 정렬 a) 버블 정렬(Bubble Sort) - 인접한 요소끼리 크기 비교를 하며 swap과정을 통해 정렬한다. - 더이상 swap이 발생하지 않는 상태까지 정렬과정을 반복한다. - O(n^2)의 시간복잡도를 가진다. b) 삽입 정렬(Insertion Sort) - 가장 좌측의 요소를 기준으로 다른 요소와 비교하며 swap과정을 통해 정렬한다. - 기준 요소보다 작은 요소들은 기준요소의 좌측에, 큰 요소들은 기준요소의 우측에 정리하는 과정을 반복한다. - O(n^2)의 시간복잡도를 가진다. c) 선택 정렬(Selection Sort) - 가장 좌측 요소의 위치를 포인터로, 포인터가 가리키는 요소보다 작은 요소를 찾아 swap하며 정렬한다. - swap이 한번 일어날 때마다, 포인터의 위치는 오른쪽으로 한칸씩 .. 2021. 12. 23. 시간복잡도 완전정복(1) 0. 시작에 앞서 요즘 백준을 통해 알고리즘 문제를 열심히 풀고있다. 문제를 작성하면 내 코드가 다른 사람들의 코드보다 10ms 정도 더 걸리는 경우도 있고, 올바른 답은 나오지만 시간초과로 인해서 문제를 틀리는 경우가 있다. 이럴 때 내 코드가 어떤 시간복잡도를 갖고 있는지를 계산한다면, 개선점을 확인할 수 있을 거라고 생각했다. 그래서 이번 포스팅은 시간 복잡도를 계산하는 방법에 대해서 완전 정복을 해보려고 한다. 1. Big - O 표기법 a) 기본 개념 - 입력값에 따른 알고리즘의 사용량을 예측하는 방법이다. - 더 자세한 설명을 원한다면, 아래의 링크를 참고하기를 바란다. https://devraphy.tistory.com/40 Data Structure - 시간 복잡도(Time Complexi.. 2021. 8. 4. Algorithm - 자료구조 핵심정리 1. 정의 a) 자료구조란? 대량의 데이터를 효율적으로 관리하기 위해, 데이터를 저장 및 정렬하는 방식을 말한다. 데이터를 어떤 방식으로 저장하고 정렬하느냐에 따라 추출 방식 등 데이터를 처리 및 조작하는데 필요한 코드가 달라진다. 2. 자료구조 (Data Structure) a) 배열(Array) 한가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조 각 데이터마다 index를 부여하여 데이터 검색에 용이(장점) 배열은 크기가 고정적(단점) 데이터가 삭제되면 배열 전체의 데이터를 재정렬(단점) b) 큐(Queue) FIFO(First In, First Out)방식으로 데이터를 저장 및 정렬하는 자료구조 FIFO방식으로 인해 데이터 삭제시, 재정렬이 필요없다. 운영체제(OS)에서 프로세스 스.. 2020. 10. 6. Data Structure - 개념 정리(summary) - 이전 포스팅까지 기본적인 자료구조를 공부했습니다. 이를 기반으로, 알고리즘을 공부해 나갈 계획입니다. - 이번 포스팅은 복습 겸 앞선 포스팅에서 다뤘던 기본적인 자료구조에 대한 개념을 정리하는 포스팅입니다. 1. 자료구조와 알고리즘이란? - 자료구조(data structure): 대량의 데이터를 효율적으로 관리하기 위해 사용하는 데이터의 저장방식을 의미한다. 저장할 데이터의 특성과 데이터 사용의 목적에 따라 해당 데이터를 저장하는 방식이 달라진다. - 알고리즘(algorithm): 프로그래밍에서 어떠한 문제를 해결하거나 풀어내기 위한 방법 또는 과정을 의미한다. 수학처럼, 한가지 문제에도 다양한 알고리즘이 존재한다. 다만, 좋은 알고리즘이란 프로그래밍 상에서 가장 적은 자원(저장공간, 메모리)을 사용.. 2020. 9. 8. Data Structure - Heap(2) 1. Heap 구현 - 데이터 삭제(pop) - Heap은 최대값(max heap) 또는 최소값(min heap)만을 삭제한다. 그렇기에 root노드만을 삭제하면 된다. - root노드의 삭제는 root노드를 꺼내었을 때 발생하며, 이 동작을 pop이라고 명시한다. def pop(self): # heap에 데이터가 없는 경우 if len(self.heap_array) = len(self.heap_array): #배열의 길이보다 긴값 = 없는값 return False # 재정렬 2번 조건 - 좌측 자식노드만 존재(우측 자식노드는 없음) elif right_child >= len(self.heap_array): # 좌측 자식노드와 값을 비교하여 자식노드 값이 큰 경우 if self.heap_array[pop.. 2020. 9. 3. Data Structure - Heap(1) 1. Heap이란? - Heap은 트리구조를 기반으로한 자료구조로 데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전 이진트리(Complete Binary Tree)이다. * 완전이진트리란? → 트리에 데이터가 삽입될 때, 왼쪽에 위치한 자식노드를 먼저 채우는 규칙을 갖고 있는 이진트리이다. 이진트리이기 때문에 자식노드는 2개만 가질 수 있다. 1) Heap을 사용하는 이유 - 우선순위 큐와 같이 최대값과 최소값을 빠르게 찾기위해 사용한다. - 이를 배열로 구현하면 최대값과 최소값을 찾는데 O(n)만큼 걸린다. - 반면에, heap을 이용하여 최대값과 최소값을 찾으면 O(log n)만큼 걸린다. (더 빠르다) 2) Heap의 구조 - Heap은 최대/최소 값을 구하기 위한 구조인 최대 힙(Max H.. 2020. 8. 31. Data Structure - 트리(Tree) & 이진탐색트리(Binary Search Tree) 1. 트리(Tree) - 트리는 node와 branch를 이용하여 구성된 데이터구조로 사이클이 없다. - 트리는 이진트리(Binary Tree)형태의 구조를 이용하여 탐색(검색) 알고리즘 구현에 많이 사용된다. * 이진트리 - 하나의 node에서 뻗어나가는 branch의 수가 최대 2개인 트리구조 [알아야 할 용어] - Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 연결되어 있는 다른 노드에 대한 branch정보가 담겨있다.) - Root Node: 트리 맨 위의 노드 - Level: 최상위 노드인 root node를 level 0으로 하였을 때, branch로 연결된 하위 노드의 깊이를 나타낸다. - Parent Node: 부모 노드를 의미하며 어떤 node에 연결된 상위 node를 의미한다.. 2020. 8. 26. Data Structure - Hash Table (2) 1. Linear Probing 기법 - Close Hashing(폐쇄 해싱) 기법 중 하나로, 해싱충돌이 발생하면 Hash Table의 저장공간 안에서 충돌을 해결하는 기법이다. - 다시 말해, 충돌이 발생하면 Hash address를 이용하여 Hash Table의 빈공간을 찾아 저장하는 기법이다. - 이 기법을 사용하면 Hash Table의 저장공간 활용도를 높일 수 있다. 2. Linear Probing 기법 구현하기 [기본 구조] 시나리오1) 새로 추가하려는 데이터의 hash값에 이미 다른 데이터가 저장되어 있는 경우, hash table을 검색하여 가장 첫번째로 찾는 빈 공간에 데이터를 저장하는 방식이다. hash값 value 0 a 1 - 위의 표를 기반으로 설명합니다. 만약에 hash값이 0.. 2020. 8. 22. 이전 1 2 다음
