전체 글49 [알고리즘] - 쉘 정렬 (Shell-sort) 1. 쉘 정렬(Shell-Sort)이란? 리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다. 앞선 글에서 삽입 정렬 에 대해 설명하였다. 삽입 정렬의 경우, 기존 배열이 어느정도 정렬되어있냐에 따라 수행 시간이 크게 차이난다. 현재 선택한 원소의 적절한 삽입 위치가 멀다면, 비교 & 이동해야하는 횟수가 많아지면서 수행 시간이 늘어나는 것이다. 정렬된 상태와 가까운 배열일수록 수행 시간은 단축된다. 즉, 삽입 정렬은 초기 리스트가 정렬이 된 상태일 경우 더 효율적이다. → 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다. → 쉘 정렬은 삽입 정렬을 보완한 방법! 쉘 정렬의 시간 복잡도는 아직까지도 정확하게.. 2024. 4. 14. [알고리즘] - 삽입 정렬 (Insertion-sort) 1. 삽입 정렬(Insertion Sort)이란? 선택한 원소를 현재 정렬된 배열 범위 내의 적절한 위치에 삽입하는 방법이다. 구현하기 쉬운 알고리즘이지만, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 삽입 정렬의 수행 방식 삽입 정렬 과정 ① 현재 index의 원소를 선택한다. ② 정렬된 부분 내에서, 현재 선택한 원소가 들어갈 적절한 삽입 위치를 찾는다. ③ 삽입 위치부터 끝까지 데이터를 한 칸씩 뒤로 민다. ④ 삽입 위치에 현재 선택한 원소를 삽입한다. ⑤ index를 1 증가시키고, 다시 ①부터 반복한다. (index가 배열의 크기만큼 커질때까지 반복) 다시 말해, 인덱스를 증가시켜 가면서 배열의 원소를 선택하고, 선택한 원소를 정렬된 범위 내의 적절한 위.. 2024. 4. 9. [알고리즘] - 선택 정렬 (Selection Sort) 1. 선택 정렬(Selection Sort)이란? 정렬되지 않은 데이터 중에서 최솟값을 찾아 맨 앞 원소와 위치를 교환시키는 방법 제자리 알고리즘 (in-place algorithm) 에 해당한다. 제자리 알고리즘 (in-place algorithm)이란? 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법을 말한다. 알고리즘은 간단하나, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 선택 정렬의 수행 방식 선택 정렬 과정 ① 정렬할 범위 안에서 최솟값을 찾는다. (내림차순인 경우 최댓값을 찾으면 된다.) ② 정렬할 부분 중 가장 앞에 있는 데이터와, ①에서 구한 데이터를 swap한다. ③ 정렬할 범위는 1 감소한다. → (맨 앞 데.. 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. [C++] - 덱(deque) 사용법 정리 (STL) 덱(deque)이란? 덱(deque)이란, double-ended-queue의 줄임말로, 큐의 양쪽에서 원소를 삽입하거나 삭제할 수 있는 자료구조이다. 덱은 C++에서 많이 쓰이는 STL 자료구조 중 하나이다. 1. 헤더파일 #include using namespace std; deque를 사용하기 위해서는 헤더파일을 include 시켜주어야 한다. STL deque는 std namespace에 있기 때문에 cin이나 cout을 사용할 때와 같이 using namespace std;를 써주면 std::를 일일이 써주지 않아도 되어 편리하다. 2. deque 선언하기 deque 이름; #include #include using namespace std; int main(){ deque dq;//D라는 이름.. 2024. 1. 16. 이전 1 2 3 4 5 6 7 8 9 다음
