algorithm3 [알고리즘] - 쉘 정렬 (Shell-sort) 1. 쉘 정렬(Shell-Sort)이란? 리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다. 앞선 글에서 삽입 정렬 에 대해 설명하였다. 삽입 정렬의 경우, 기존 배열이 어느정도 정렬되어있냐에 따라 수행 시간이 크게 차이난다. 현재 선택한 원소의 적절한 삽입 위치가 멀다면, 비교 & 이동해야하는 횟수가 많아지면서 수행 시간이 늘어나는 것이다. 정렬된 상태와 가까운 배열일수록 수행 시간은 단축된다. 즉, 삽입 정렬은 초기 리스트가 정렬이 된 상태일 경우 더 효율적이다. → 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다. → 쉘 정렬은 삽입 정렬을 보완한 방법! 쉘 정렬의 시간 복잡도는 아직까지도 정확하게.. 2024. 4. 14. [알고리즘] - 투 포인터 (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 다음
