컴퓨터 과학
-
[스크랩] hashmap컴퓨터 과학/자료구조와 알고리즘 2021. 8. 7. 17:36
정말 좋은 글이어서 스크랩해둡니다. 해시함수에 대한 간략한 정리는 정리를 할 수 있을 때 할 예정입니다. 원문 그대로 스크랩했습니다. >>출처 https://d2.naver.com/helloworld/831311 Java HashMap은 어떻게 동작하는가? 이 글은 Java 7과 Java 8을 기준으로 HashMap이 어떻게 구현되어 있는지 설명합니다. HashMap 자체의 소스 코드는 Oracle JDK나 OpenJDK나 같기 때문에, 이 글이 설명하는 HashMap 구현 방식은 Oracle JDK와 OpenJDK 둘 모두에 해당한다고 할 수 있습니다. Java가 아닌 다른 언어를 주로 사용하는 개발자라 하더라도, Java의 HashMap이 현재 어떻게 구현되어 있고, 어떻게 발전되었는지 알면 라이브러..
-
[간단 정리] 퀵 정렬컴퓨터 과학/자료구조와 알고리즘 2019. 11. 27. 01:16
*오름차순 기준입니다 정렬 알고리즘 중에 퀵 정렬이 가장 성능이 좋다. 다른 원소와 비교하여 정렬을 수행하는 비교 정렬에 속한다. 최악의 시간 복잡도는 O(N^2)이지만 최선과 평균이 O(NlogN)이다. 원소들 중에 같은 값이 있으면 순서가 달라질 수 있기 때문에 불안정 정렬이다. 기본적인 동작 1. 배열 중에 하나의 원소를 골라 피벗(기준)을 정한다. 2. 피벗을 기준으로 앞에는 피벗보다 작은 값, 뒤에는 큰 값이 오도록 나눈다. 이를 분할이라고 한다. 3. 분할된 배열에 대해 위 과정을 재귀적으로 반복한다. 최악의 경우는 피봇으로 가장 작은 수가 선택되거나 큰 수가 선택될 때인데, 이는 중위값을 선정해 해결할 수 있다. 0번째, 가운데, 마지막 요소 중에서 중간 값을 피벗으로 정하면 된다. 퀵 정렬..
-
[간단 정리] 정렬 알고리즘(버블, 선택, 삽입)컴퓨터 과학/자료구조와 알고리즘 2019. 11. 26. 19:44
*오름차순 기준입니다 1. 버블정렬 첫 번째 자료부터 마지막 자료까지 인접한 자료끼리 비교해가면서 교환한다. 정렬이 되어 있지 않은 자료를 기준으로(최악) 최초에 n-1번, 그다음에 n-2번, 그다음에 n-3번, 이렇게 해서 최대 횟수는 1 + 2 + .. + (n-1) = n(n-1)/2이므로 시간복잡도는 O(N^2)이다. 최고, 평균, 최악의 경우 모두 O(N^2). 구현은 매우 간단하고 성능이 안 좋다. 교환할 때마다 3번의 임시복사가 일어나기 때문이다. >>구현 #include #include void BubbleSort(int arr[], int size); void Swap(int& value1, int& value2); void PrintArr(int arr[], int size); int ..