알고리즘5 [알고리즘] - 쉘 정렬 (Shell-sort) 1. 쉘 정렬(Shell-Sort)이란? 리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다. 앞선 글에서 삽입 정렬 에 대해 설명하였다. 삽입 정렬의 경우, 기존 배열이 어느정도 정렬되어있냐에 따라 수행 시간이 크게 차이난다. 현재 선택한 원소의 적절한 삽입 위치가 멀다면, 비교 & 이동해야하는 횟수가 많아지면서 수행 시간이 늘어나는 것이다. 정렬된 상태와 가까운 배열일수록 수행 시간은 단축된다. 즉, 삽입 정렬은 초기 리스트가 정렬이 된 상태일 경우 더 효율적이다. → 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다. → 쉘 정렬은 삽입 정렬을 보완한 방법! 쉘 정렬의 시간 복잡도는 아직까지도 정확하게.. 2024. 4. 14. [알고리즘] - 삽입 정렬 (Insertion-sort) 1. 삽입 정렬(Insertion Sort)이란? 선택한 원소를 현재 정렬된 배열 범위 내의 적절한 위치에 삽입하는 방법이다. 구현하기 쉬운 알고리즘이지만, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 삽입 정렬의 수행 방식 삽입 정렬 과정 ① 현재 index의 원소를 선택한다. ② 정렬된 부분 내에서, 현재 선택한 원소가 들어갈 적절한 삽입 위치를 찾는다. ③ 삽입 위치부터 끝까지 데이터를 한 칸씩 뒤로 민다. ④ 삽입 위치에 현재 선택한 원소를 삽입한다. ⑤ index를 1 증가시키고, 다시 ①부터 반복한다. (index가 배열의 크기만큼 커질때까지 반복) 다시 말해, 인덱스를 증가시켜 가면서 배열의 원소를 선택하고, 선택한 원소를 정렬된 범위 내의 적절한 위.. 2024. 4. 9. [알고리즘] - 버블 정렬 (bubble sort) 1. 버블 정렬(bubble sort)이란? 인접한 데이터끼리 비교, swap 연산을 수행하여 정렬하는 방법 버블 정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 알고리즘은 간단하나, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 버블 정렬의 수행 방식 버블 정렬의 수행 과정 ① 정렬할 범위의 앞부분부터 인접한 두 원소의 값을 비교한다. ② 앞 원소가 더 크다면 swap한다. / 뒤 원소가 더 크다면 continue ③ 정렬할 범위의 끝부분까지 반복한다. => 반복이 끝나면 정렬할 범위는 1 감소, 정렬된 범위는 1 증가한다. ④ 새로운 정렬할 범위를 얻었다. 다시 ①부터 반복한다. 3. 버블 정렬 구현 (C++) #include using name.. 2024. 2. 13. [알고리즘] - 투 포인터 (Two-Pointers) 1. 투 포인터 알고리즘 (Two - Pointers Algorithm) 투 포인터 알고리즘은 1차원 배열에서 활용할 수 있는 알고리즘이다. 배열에서 특정 원소를 가리키는 2개의 포인터를 사용하여 목표값을 찾는다. 이중 반복문을 이용하면 시간 복잡도가 O(n^2)이지만, 투 포인터 알고리즘을 이용하면 O(n)으로 해결이 가능하다. 코딩테스트에서 자주 나오는 편은 아니지만 종종 사용되므로 알아두고 넘어가자. 2. 투 포인터 알고리즘 활용하기 N개의 자연수가 저장되어 있는 수열이 있다고 했을 때, 이 수열에서 연속된 특정 구간의 합이 K이 되는 부분을 찾고자 한다. 예를 들어, 7개의 자연수가 들어있는 배열 arr에서 구간 합이 6인 경우의 수를 세어 보자. N = 7 / K = 6 초기 설정 기본 알고리즘.. 2024. 1. 19. [알고리즘] - 구간 합 (Prefix sum) 1. 구간 합(Prefix sum)이란? 수열에서 특정 구간의 합을 구할 때 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 코딩 테스트에서 유용하게 활용 가능하니 꼭 알고 넘어가야 하는 알고리즘 중 하나이다. 부분 합과 혼동할 수 있어 정리해보자면, 일차원 배열 A가 있다고 하자. - 부분 합(Partial sum) : 처음부터 k번 인덱스까지의 합 ( = A[0] + A[1] + ... A[k] ) - 구간 합(Prefix sum) : i번부터 j번 인덱스까지의 합 ( = A[i] + A[i+1] ... + A[j-1] + A[j] ) 반복문으로 i번부터 j번 인덱스까지 더한다면? #include using namespace std; int main() { int i, j; cin.. 2024. 1. 9. 이전 1 다음
