dion

목차1. 기수 정렬2. 계수 정렬3. 셸 정렬  1. 기수 정렬 (Radix Sort)  - 낮은 자리 수부터 정렬하는 방식  * 123 > 3(일의 자리)  - 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리 필요  - 알고리즘 복잡도 : O(dn) *d : 최대 자릿수  2. 계수 정렬 (Counting Sort)  - 숫자 끼리 비교하지 않고 카운트를 세서 정렬하는 방식  - 카운팅을 위한 메모리 필요  - 알고리즘 복잡도 : O(n + k)  *k : 정렬 대상 데이터 중 최대값  3. 셸 정렬 (Shell Sort)  - 삽입 정렬의 약점을 보완한 정렬 방식  - 삽입 정렬의 약점 : 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비..

알고리즘 2024. 9. 24. 15:40

목차1. 합병 정렬2. 힙 정렬3. 퀵 정렬4. 트리 정렬  1. 합병 정렬 (Merge Sort)  - 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식  - 추가저장을 위한 메모리 필요 (인플레이스 정렬과 반대)  - 알고리즘 복잡도 : O(nlogn)  2. 힙 정렬 (Heap Sort)  - 힙 자료구조 형태의 정렬 방식  - 기존 배열을 최대 힙으로 구조 변경 후 정렬 진행  - 알고리즘 복잡도 : O(nlogn)   3. 퀵 정렬 (Quick Sort)  - 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식  - 한번 정렬 후 기준 값 왼쪽에는 기준값보다 작은 수만, 오른쪽에는 기준 값보다 큰 수만 존재  - 알고리즘 복잡도 : ..

알고리즘 2024. 9. 24. 15:27

목차1. 정렬2. 버블 정렬3. 삽입 정렬4. 선택 정렬  1. 정렬  - 특정 값을 기준으로 데이터를 순서대로 배치하는 방법  - 구현 난이도는 쉽지만, 속도는 느린 알고리즘      - 버블 정렬, 삽입 정렬, 선택 정렬  -  구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘      - 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬  - 하이브리드 정렬      - 팀 정렬, 블록 병합 정렬, 인트로 정렬  - 기타 정렬 알고리즘      - 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬  * 인플레이스 정렬 : 제자리 정렬, 추가적인 메모리 필요 없이 메모리 공간 내에서 해결 (버블, 삽입, 선택) 2. 버블 정렬 (Bubble Sort)  - 인접한 데이터를 비교하며 자리 바꾸는 방식  ..

알고리즘 2024. 9. 24. 15:07

목차1. 알고리즘2. 알고리즘의 조건3. 좋은 알고리즘4. 알고리즘 Part Summary  1. 알고리즘 (Algorithm)  - 어떤 문제 해결을 위한 절차나 방법  - 각각의 알고리즘에는 정형화된 플로우가 존재  2. 알고리즘의 조건  - 입력  - 출력  - 명확성  - 유한성 : 정해진 시간 내에 알고리즘이 동작해야함  - 효율성 : 시간 복잡도 혹은 공간 복잡도가 효율적으로 짜여진 것  3. 좋은 알고리즘  - 정확성  - 시간 복잡도  - 공간 복잡도  4. 알고리즘 Part Summary  - 정렬  - 이진 탐색 / 투 포인터  - 그리디 알고리즘  - 분할 정복 / 다이나믹 프로그래밍  - 백 트래킹  - 최단 경로  - 최소 신장 트리

알고리즘 2024. 9. 24. 13:54

목차1. 데크2. 데크 기본 구조3. 데크 주요 연산4. 입력제한 데크5. 출력제한 데크  1. 데크 (Deque)  - 양쪽에서 삽입과 삭제가 모두 가능한 자료구조    - Deque: Doubly-ended Queue    - Stack과 Queue를 합친 상태  2. 데크 기본 구조  - 데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조  - 일부 기능을 제한하여 용도에 맞게 변형 가능  3. 데크 주요 연산  - add(offer) : 데이터 추가 (front 쪽은 addFirst / Rear 쪽은 addLast)  - remove(poll) : 데이터 제거  * add와 remove 는 데이터가 없을 때 오류 발생 / offer와 poll은 데이터가 없을 때 null값 반환  4. 입력제한 ..

자료구조 2024. 9. 23. 10:45

목차1. 큐2. 큐 기본 구조3. 큐 기본 연산  1. 큐 (Queue)  - 선입선출 (First In First Out; FIFO) 자료구조  - 먼저 들어온 데이터가 먼저 나가는 구조  - 입력 순서대로 데이터 처리가 필요할 때 사용    ex) 프린터 출력 대기열, BFS (Breath-First Search/너비우산 ) 등  2. 큐 기본 구조  - 선입선출 구조를 따름  - 기본적으로 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어짐  3. 큐 기본 연산  - 데이터 추가 (Enqueue) : 큐에 데이터 추가  - 데이터 꺼내기 (Dequeue) : 큐에서 데이터 꺼내기   * Queue는 인터페이스이기 때문에 바로 객체 생성 불가 > 메소드를 오버라이딩 해서 구성을 해야함    > L..

자료구조 2024. 9. 23. 10:36

목차1. 스택2. 스택 기본 구조3. 스택 기본연산  1. 스택 (Stack)  - 후입선출 (Last In First Out; LIFO) 자료구조 : 마지막에 들어온 데이터가 먼저 나가는 구조  - 데이트가 입력된 순서의 역순으로 처리되어야 할 때 사용    ex) 함수 콜 스택, 수식 계산, 인터럽트 처리 등  2. 스택 기본 구조  - 후입 선출 구조  - 기본적으로 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이루어짐  3. 스택 기본 연산  - 데이터 추가 (push) : 스택의 가장 마지막 위치에 데이터 추가  - 데이터 꺼내기 (pop) : 스택의 가장 마지막 위치에서 데이터 꺼냄  - peek / top : 스택의 맨 위에 있는 데이터를 조회, 삭제하지 않고 데이터에 접근 가능  - i..

자료구조 2024. 9. 20. 11:23

목차1. 배열2. 배열의 장점3. 배열의 단점  1. 배열 (Array)  - 많은 수의 데이터를 다룰 때 사용하는 자료구조  - 각 데이터를 인덱스와 1:1 대응하도록 구성  - 데이터가 메모리 상에 연속적으로 저장됨데이터'a''b''c''d''e'인덱스01234  2. 배열의 장점  - 인덱스를 이용하여 데이터에 빠르게 접근 가능     ex) arr 배열'a''b''c'    arr[0] > 'a'   arr[1] > 'b'   arr[2] > 'c'  * 인덱스를 이용하여 데이터에 바로 접근 가능  3. 배열의 단점  - 데이터의 추가/삭제가 번거로운 편     - 미리 최대 길이를 정해서 생성해야 함     - 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성     - 데이터 ..

자료구조 2024. 9. 20. 10:59