2019-08-20
병합 정렬(merge sort)? 병합 정렬(merge sort)의 핵심은 분할과 정복이다. 정렬할 배열을 원소가 하나뿐인 배열 단위로 나뉠 때까지 분할하고, 반대로 이렇게 분할된 배열을 점점 더 큰 배열로 병합하면서 정렬을 완성한다. 분할/정복이라는 접근 방식은 재귀 호출을 통해 구현된다. 이 링크를 통해 병합 정렬이 어떻게 작동하는지 참고할 수 있다.…
2019-08-20
퀵 정렬(quick sort)? 퀵 정렬(quick sort)은 가장 애용되는 정렬 알고리즘이다. 복잡도는 O(n long n)이고, 복잡도가 동일한 여타 정렬 알고리즘보다 성능이 낮다. 병합 정렬과 마찬가지로 분할/정복 방식으로 접근한다(그러나 병합 정렬 과는 달리, 원소를 하나 가진 배열까지 잘게 쪼개지 않는다.) 이 링크를 통해 퀵 정렬이 어떻게 작…
2019-08-19
삽입정렬? 삽입 정렬(insertion sort)은 한 번에 한 원소씩 정렬된 배열을 만들어가는 알고리즘이다. 첫 번째 원소는 정렬이 끝났다고 가정하고, 두 번째 원소와 비교해 첫 번째 원소보다 더 작다면 첫 번째 원소 앞으로 옮긴다. 그래서 처음 두 원소의 정렬이 끝나면 다음엔 세 번째 원소와의 비교를 계속한다.(첫 번째, 두 번째, 세 번째 위치 중 …
2019-08-19
선택정렬? 선택정렬(selection sort)은 제자리(in-place) 정렬 알고리즘의 하나로, 최솟값을 찾아 맨 앞으로 보내고, 그 다음으로 작은 값을 찾아 2번째 위치로 보내는 식으로 정렬한다. 이 링크를 통해 선택 정렬이 어떻게 작동하는지 참고할 수 있다. 시간복잡도 시간 복잡도가 O(n^2) 이기 때문에 거의 사용되지 않는 알고리즘이다. 다만 …
2019-08-18
버블정렬(Bubble Sort)? 버블 정렬은 인접한 두 원소를 모두 다 비교하고 그 결과에 따라 두 원소의 위치를 서로 바꾼다. 원소가 정렬돼가는 모습이 마치 수면 위로 떠오르는 거품(버블) 같다고 하여 버블 정렬이란 이름이 붙었다. 이 링크를 통해 버블 소트가 어떻게 정렬되는지 참고할 수 있다. 시간복잡도 시간 복잡도가 O(n^2) 이기 때문에 거의 …
2019-06-22
Hash Table? 은 자료 구조에서 특정 값을 가장 신속하게 찾는 방법이다. 링크드 리스트에의 경우 특정 원소를 찾기 위해 자료구조가 가진 모든 원소를 루프를 통해 탐색해야 한다. 배열의 경우에는 원소 추가 시에 각 원소를 하나씩 뒤로 밀어야 해서 비용이 크다. Hash 함수 는 어떤 에 해당하는 값의 주소를 테이블에서 찾아주는 함수이므로 조회속도…
2019-06-20
SET(집합)? 정렬되지 않은(unordered) 컬렉션(collection) 으로 원소는 반복되지 않는다.(중복된 원소가 없다) SET 자료구조는 수학책에 나오는 유한 집합(finite set) 개념을 컴퓨터 과학에 적용한 것이다. SET은 정렬 개념이 없으며 원소가 중복되지 않는 배열이라고 볼 수 있다. 집합은 합집합(union), 교집합(inters…
2019-06-19
들어가며 Dictionary 와 Hash 자료구조는 유일한 값(반복되지 않는 값)을 저장하기 위한 자료 구조다. Dictionary(or Map)은 값을 형태로 저장한다. Dictionary(Map) Dictionary(or Map)은 값을 형태로 저장하는 자료구조로 는 원소를 찾기 위한 식별자(identifier) 이 , 가 형태의 원소를 모아…