본문 바로가기

전체 글

 (178)
[자료구조] 트리(Tree)란? 배열, 리스트, 스택과 큐, 해시테이블과 같은 자료구조는 데이터의 이전 데이터나 다음 데이터의 순서가 존재하는 선형 자료구조에 해당한다.이러한 구조는 특정 데이터를 검색할때 순서대로 데이터를 찾아야하는 문제점과,데이터를 저장하기위해 일정한 공간을 미리 할당해야하는 등의 제한적인 구조를 가지고있어 복잡한 문제를 해결하는데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. 계층적 문제란 계층적 속성을 갖는 자료는 선형구조로 표현하기가 어렵다는 것을 뜻한다순환 종속성 문제란 두개 이상의 요소가 서로 순환적으로 의존하여 발생하는 문제를 뜻하는데, 이또한 선형구조로 표현하기에는 어려움이 있다. 따라서 이러한 단점들을 개선하기위해 비선형 자료구조가 나오게되었다비선형 자료구조는 크게 트리와 ..
정렬 알고리즘[Quick Sort] Quick sort 란? Quick sort는 최선,평균 시간복잡도가 O(n log n)이고, 최악의 경우에는 O(n^2)인것을 확인할 수 있다.그리고 메모리는 O(n log n)인것을 확인할 수 있다 Quick sort는 이름에서도 나타나듯이 평균적으로 매우 빠른 수행속도를 자랑하는 정렬방법이다. Quick sort도 Merge sort와 같이 분할정복법을 사용한다. 그러나 Merge sort와 달리 리스트를 균등하게 분할할 필요는 없다.Quick sort도 Merge sort와 같이 시간복잡도가 O(n log n)인데, Quick sort가 훨씬 짧은 시간이 걸린다는것을 알 수 있다. 왜그럴까??이는 "참조지역성의 원리"로 설명할 수 있다!Quick sort는 알고리즘 특성상 동일한 배열 내에서 자리..
정렬 알고리즘[Merge Sort] 정렬알고리즘을 살펴보기전에 먼저 시간복잡도에 대해서 알아볼 필요가 있다시간복잡도에 대한 내용을 정리했었어서 링크만 첨부하도록 하겠다시간복잡도란?간단하게 한줄로 요약해보면시간복잡도란 "입력값과 연산수행시간의 상관관계를 나타내는 척도" 를 말한다즉, "문제를 해결하는데 걸리는 시간과 입력의 합수관계"이다. 시간복잡도는 최악을 기준으로 "빅오 표기법"으로 표시하여 성능을 예측하는데,시간복잡도가 빠른순으로 보면 아래와 같이 나타낼 수 있다O(1) O(log n) O(n) O(n log n) O(n^2)O(1)이 시간복잡도가 가장 좋고(가장 빠르고), O(n^2)이 가장 안좋은것(가장 느림)을 알 수 있다   Merge sort 란?이제 5개의 정렬알고리즘이 있는 표를 보면서 Merge Sort에 대해서 알아..

티스토리툴바