동빈북 7장 내용정리 이진탐색(Binary Search)
이진탐색은 영어로는 Binary Search이다. 일반적으로 탐색할 때는 순서대로 탐색하는 순차 탐색 말그대로 순서대로 탐색하는 것이다. 그러나 이 방식은 찾는 데이터가 자료구조의 가장 끝부분에 들어가 있다면 이상황이 최악의 탐색상황이므로 O(N)의 시간 복잡도를 나타낸다. 이제 이거를 어떻게 효율적으로 탐색할 수 있는지에 대한 아이디어에서 나온것이 바로 이분탐색(이진탐색,Binary Search)이다. 만약 배열의 요소가 int[] list = {1,5,7,10,11,14,17,20,64,100}; 라고 가정해보자. 만약에 찾고자 하는 key값이 100이라면 순차탐색을 하게되면 접근하는 요소의 순서가 1,5,7,10,11,14,17,20,64,100 순서로 총 10번을 방문하게 된다.(key값이 없더라..
2020. 11. 13.
동빈북 6장 개념정리 정렬(Sort)
정렬의 사전적 의미는 말그대로 요소를 순서대로 놓는것이다. 예를들어 2,5,10,9,8 이라는 숫자들이 나열되어 있을때, 2, 5, 8, 9, 10 등으로 말이다. 정렬에는 굉장히 여러가지 종류가 있는데, 삽입정렬, 선택정렬, 버블정렬, 퀵정렬, 힙정렬, 합병정렬 등 여러가지가 있다. 이 정렬들이 어떻게 구현되어 있고(어떤 방법을 이용하여 정렬했는지) 시간복잡도가 얼마나 되며 왜 그런 복잡도를 가지는지를 아는 것은 매우 중요하다. (사실 나도 삽입 정렬이랑 선택 정렬은 아직도 햇갈린다.) 그래서 정리를 하려고 한다. 선택정렬 저장된 데이터의 요소 중 최소값을(또는 최대 값) 찾고 데이터의 요소 중 첫번째와 뒤집는 방식이다. 삽입정렬 저장된 데이터의 요소를 하나씩 찾아서 올바른 위치에 삽입 해준다. 즉, ..
2020. 11. 13.
