컴퓨터 과학/자료구조와 알고리즘
-
그래프 간선의 분류 간단 정리컴퓨터 과학/자료구조와 알고리즘 2021. 9. 14. 22:41
참고 https://rebro.kr/71 https://hy38.github.io/about-edges-in-graph https://bowbowbow.tistory.com/1 https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm 설명 아래와 같은 그래프가 있습니다. 1번 정점부터 깊이 우선으로 탐색을 시작하면 다음과 같은 스패닝 트리가 나옵니다. 스패닝 트리를 연결하고 있는 간선을 스패닝 트리 간선이라고 합니다. 스패닝 트리에는 순환이 없습니다. 스패닝 트리는 이미 방문한 노드는 방문하지 않기 때문에 (5, 1), (6, 4), (6, 3), (1, 7) 간선은 스패닝 트리에 포함되지 않습니다. 여기에서 순방향 간선, 역..
-
hash map컴퓨터 과학/자료구조와 알고리즘 2021. 8. 7. 21:51
언어 차원에서 제공하는 알고리즘은 성능, 안정성 등에서 검증이 된 것입니다. 그렇지 않으면 해당 언어의 신뢰도에 치명적인 손상을 입힐 수 있기 때문입니다. 때문에 검증된 이론, 수학적으로 증명된 공식 등을 통해서 구현됩니다. 자료구조는 직접 개발하기 위해 공부한다기 보다는 간단한 기능을 직접 구현해보면서 개념과 기본적인 흐름을 파악하는 데 의의가 있는 것 같습니다. 해시맵은 데이터를 배열에 넣습니다. 그러므로 O(1)의 시간복잡도를 가지지만 데이터가 많아질수록 중복된 해시 코드를 얻게 될 확률이 올라갑니다. 그래서 C++ 표준 라이브러리인 std::unordered_map은 일정 수준 이상에서 std::map보다 성능이 안 나올 수 있습니다. 해시맵은 최악의 경우에는 O(n)까지 성능이 저하될 수 있습니..
-
[스크랩] 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 ..