Noooodle's Footprints

배열(Array): 동일한 타입의 여러 원소를 선형 집합으로 관리하는 정적 데이터 구조생성과 동시에 크기가 고정되어 늘릴 수 없다.메모리상에 일렬로 저장되어 Random Access가 가능하다.원소에 접근과 변경은 빠름, 중간에 원소 추가&삭제시 원소를 옮겨야 하므로 오래걸림.. get, add : O(1)insert, remove : O(N) 리스트(List): 동일한 타입의 여러 원소를 선형 집합으로 관리하는 동적 데이터 구조원소가 추가&삭제됨에 따라 크기가 변경될 수 있다.List Interface 구현체에 따라 특성이 다르다.ArrayList, LinkedList, Vector 가 있음 ArrayList: 동적 배열을 사용한 List 구현체원소가 추가될 때 배열에 남은 공간이 없다면, 크기를 일정..

4. Merge sort 5. Quick sort 6. Heap sort Divide-And-Conquer, 분할정복법분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복: 각각의 작은 문제를 순환적(재귀)으로 해결합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 Merge sort, Quick sort, Heap sort 모두 분할정복법을 사용한다. 세 가지 방법 모두 시간복잡도는 O(nlogn)으로 동일하다. *예시는 오름차순 정렬*노란색은 정렬된 부분*파란색은 정렬할 부분4. Merge sort, 합병정렬1) 배열을 절반으로 나눔 2) 나뉜 배열 각각을 정렬함 3) 나뉜 배열을 합치면서 정렬순환적(재귀) 코드이다. 재귀는 자기 자신을 호출하는 것을 말한다. 처음..

정렬은 말 그대로 순서대로 정리하는 것을 의미한다. 뒤죽박죽인 숫자를 오름차순, 내림차순으로 정렬할 수 있다. 뭐 그런 것들.. 데이터들을 정리할때 필요하다. 정렬 알고리즘은 여러가지가 있지만 내가 배운 몇 개만 다뤄볼 것이다.1. Insertion sort2. Bubble sort3. Selection sort4. Quick sort5. Merge sort6. Heap sort7. Radix sort -> 특정한 경우에 사용오름차순 정렬로 예시를 들었다. 1. Insertion sort(삽입 정렬)앞 원소가 정렬되었다고 가정하고 정렬되지 않은 뒤의 원소를 정렬된 원소들 사이에 삽입한다. 이때 크기를 비교하고 적절한 위치에 넣는다.그림으로 예시를 들자.노란색은 정렬 된 부분, 흰 색은 정렬되지 않은 부분..