Computer Science/Algorithm (3) 썸네일형 리스트형 병합 정렬 전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법인 병합 정렬(합병 정렬)이 있음 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과입니다. 4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과입니다. 2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과입니다. 1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과입니다. 병합 정렬 실행 시간의 상한은 O(n log n) 숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을.. 버블 정렬 vs. 선택 정렬 버블 정렬이란? 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다. 마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식 중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로 (n-1)*(n-2) = n^2-3n+2(n−1)∗(n−2)=n2−3n+2 번의 비교 및 교환이 필요 여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2) 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 됩니다. 선택 정렬이란? 배열 안의 자료 .. 알고리즘 기본 개념 (선형 검색, 이진 검색, Big O 표기법) 선형 검색 (Linear search)란? 일렬로 검색을 하는 방법 7개의 박스가 1번부터 7번까지 있으면 내가 찾는 물건이 어느 박스에 있는지 발견할 때까지 1번부터 하나하나 one by one 찾는거임 이진 검색 (Binary search)란? 이진 검색 알고리즘은 오름차순(ascending order)으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택 Big O 표기법? 여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있습니다. O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)도 .. 이전 1 다음
