분류 전체보기 (79) 썸네일형 리스트형 삽입정렬(Insertion Sort) 삽입 정렬( insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘인데 버블정렬(Bubble Sort)와 선택정렬(Selection Sort)와 마찬가지로 단순하고 이해하기 쉽지만 성능상으로는 느린 정렬 알고리즘 중 하나이다. 어떤 식으로 동작하는지 살펴보자. 위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다. 삽입정렬은 처음 2개의 원소들을 비교한다. 14와 33 2개의 원소를 비교하면 이미 오른차순으로 정렬되어 있고 정렬 서브리스트(sorted sub-list) 14를 가지게 된다. 이제 앞으로 이동하여 33과 27을 비교한다. 33.. 버블(거품)정렬(Bubble Sort) 버블정렬은 데이터의 모든 원소를 하나씩 무식하게 비교해가면서 정렬하는 기법(부르트포스(Brute Force) 의 한 종류) 으로 정렬시 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블(거품)정렬이라고 부른다. 알고리즘을 살펴보기 전에 VisuAlgo 에서 어떤 방식으로 정렬되는지 시뮬레이션 해보자. 버블정렬은 모든 원소를 하나씩 비교해서 원하는 정렬 규칙에 맞게 두 원소를 서로 swap 하는 과정을 거친다. 쉽게 설명하기위해 정렬되지 않은 배열 numbers 가 아래처럼 있다고 할때 오름차순으로 버블정렬 하때 순서는 아래와 같다. (아래 이미지들의 출처는 튜토리얼 포인트 입니다.) 버블소트는 처음 2개의 원소(numbers[0], numbers[1])를 비교한다. 비교해서 만약 첫.. 보간탐색(Interpolation Search) 선형탐색(Linear Search)는 데이터의 원소를 처음부터 끝까지 순차적으로 탐색하면서 검색하는 부르트포트(Brute Force)의 종류이고 이진탐색(Binary Search)은 정렬된 데이터 원소들을 절반씩 나누면서 분할 정복(Divide Conquer)하는 방식이라고 설명했었다. 그럼 보간탐색(Interpolation Search)은 무엇인가? 보간탐색은 이진탐색을 개선한 것인데 이진탐색처럼 비교 대상을 무조건 mid = (high-low)/2 로 하지 않고 우리가 찾는 원소는 전체 데이터 값을 보니 대충 이정도에 있겠구나 추측하여 탐색하는 방식이다. 예를들어 data = [2, 4, 6, 8, 10, 12, 14] 가 있고 이중 12를 찾는다면 이진탐색은 mid = (6 - 0)/2 = 3이 되.. 이진탐색-상/하한선((lower bound,upper bound) 주어진 자료에서 중복되지 않은 값이 주어질 때 그 데이터내에 특정 값이 존재하는지 검색하는 방법 중 이진탐색(Binary Search)은 자료를 정렬한후 분할정복방식으로 데이터를 2/1씩 나누면서 값이 존재하는지 확인하는 알고리즘을 사용했었다. 이진탐색이 데이터내 특정 값을 정확히 찾는 것이라면 lower bound와 upper bound 는 이진탐색 알고리즘에서 약간 변형된 것으로 중복된 자료가 있을때 유용하게 탐색할 수 있는 알고리즘으로 lower bound는 데이터내 특정 K값보다 같거나 큰값이 처음 나오는 위치를 리턴해주고 upper bound 는 K값보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘이다. △ [출처] http://bajamircea.github.io/coding/cpp/2.. 이진탐색(Binary Search) 선형(순차) 탐색(Linear Search) 은 부르트포스(brute force)의 일종으로 무식하게 처음부터 끝가지 모든 자료를 비교해가면서 원하는 값을 찾는 무식한 방법이라고 하였다. 그래서 찾는것이 앞부분에 있으면 다행히 빨리 찾을수 있지만 뒤에 있다면 worst case 로 탐색하는데 O(N)이 걸린다. 이진탐색(Binary Search) 알고리즘은 선형탐색이 가지고 있는 단점을 보완할 수 있는 알고리즘인데 아무리 자료가 많아도 탐색하는데 O(log N) 이 걸린다. 선형탐색에 비해 성능면에서 엄청 좋은것이다. 그래서 실무에서는 선형탐색보다 이진탐색을 더 많이 사용한다. 대신 조건이 있는데 선형탐색은 자료가 정렬될 필요가 없지만 이진탐색은 내부 알고리즘 로직에 의해 반드시 자료가 정렬되어 있어야만.. 선형(순차) 탐색(Linear Search) 선형(순차) 탐색(Linear Search)은 자료를 탐색하는데 가장 무식하면서 이해하기 쉬운 알고리즘(algoritm) 이다. 선형(순차)탐색은 일종의 부르트포스(Brute Force)의 한 예이기도 한데 왜 무식하냐 하면 특정 자료를 찾기위해서 모든 자료를 뒤져봐야 알기 때문이다. 찾는 것이 일찍나오면 그나마 다행인데 모든 자료 끝까지 뒤질때까지 안나오는 worst case 인경우 성능이 O(N)이다. 위 그림을 보면 더 이해하기 쉬운데 리스트 = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 } 에서 33을 찾기위해 처음부터 마지막 까지 같은 값이 있는지 하나씩 비교해가면서 찾는 것이다. 코드 구현도 매우 간단한데 함수의 확장성을 고려해서 점진적으로 발전시켜 나가겠다. 1.. 선택정렬(Selection Sort) 선택정렬(Selection Sort)은 심플한 정렬 알고리즘이다. 알고리즘이 어떤 식으로 동작하는지 살펴보자. 위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다. 모든 데이터들을 순차적으로 비교하여 가장 최소값을 찾는다. (여기는 10이 가장 작은 값이다.) 위에서 찾은 가장 작은 값은 10이다. 10을 첫번째 위치에 있는 (index = 0) 인 14와 교체한다. 맨 왼쪽의 10은 이미 데이터의 모든 원소들 중 가장 작은값이 선택(selection)되어 이동하였으므로 그 다음에는 10을 뺀 나머지 원소들 중 가장 작은 값을 찾는다. 10을 뺀 나머지 원소들 중에서 가장 작은 값은 14이므로 14를 두번째 위치에 있는(index = 1) 인 33과.. 순열(Permutation) 목차 경우의 수 - 합의 법칙경우의 수 - 합의 법칙 순열(Permutation) 이전 1 ··· 5 6 7 8 9 10 다음
