끄적끄적 코딩
article thumbnail
[자료구조] Shell Sort (셀 정렬)
자료구조 2021. 8. 6. 19:02

개념 간격을 기준으로 삽입정렬을 하는 방식 삽입정렬의 성질을 이용하고 보완한 방법 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 더 높음 과정 1. 간격을 구합니다. 1.1) 현재 간격이 없는 경우 (개수 / 2) 1.2) 현재 간격이 있는 경우 (간격 / 2) 2. 간격들에 존재하는 수들끼리 삽입정렬 3. 간격이 1이 아닌 경우 1, 2 반복 4. 간격이 1인 경우, 정렬 완료 시간복잡도 Best Case = n Average Case = n^1.5 Worst Case = n^2

article thumbnail
[자료구조] Counting Sort (계수 정렬)
자료구조 2021. 8. 6. 18:45

개념 배열내의 수의 개수를 저장해서 작은 수부터 개수만큼 값을 입력해서 정렬하는 방식 비교연산이 없음 배열내 최대 값 +1만 길이의 배열이 필요 max값 산출이 선행되어야 함 정수만 정렬 가능 누적합을 생성하여 누적합을 기준으로 정렬할 경우 안정정렬이 보장됨 과정 1. 카운팅 배열 생성 2. 카운팅 배열로 누적합 생성 3. 입력 배열과 동일한 크기의 출력 배열을 생성, 입력 배열의 역순으로 출력 배열에 요소들을 채움 시간 복잡도 (Best = Average = Worst) = O(N)

article thumbnail
[자료구조] Radix Sort (기수 정렬)
자료구조 2021. 8. 6. 17:37

개념 낮은 자릿수(혹은 높은 자릿수)부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘 정렬 속도가 빠름 문자열, 정수 정렬이 가능(자리수를 비교해서 정렬하는 방식) 안정 정렬 비교연산이 없음 자릿수가 없는 경우 정렬 불가 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 필요 LSD(Least-Significant-Digit) : 가장 작은 자리수부터 비교하는 방법 MSD(Most-Significant-Digit) : 가장 큰 자리수부터 비교하는 방법 1. 1의 자리를 비교하여 1의 자리를 기준으로 정렬 2. 10의 자리를 비교하여 10의 자리를 기준으로 정렬 3. 100의 자리를 비교하여 100의 자리를 기준으로 정렬 ... 시간복잡도 정렬하는 숫자의 자릿수에 따라 시간복잡도 O(d..

article thumbnail
허프만 코드 (Huffman code)
자료구조 2021. 5. 15. 20:58

허프만 코드 허프만 코딩은 문자의 빈도 또는 확률정보를 이용해 통계적 압축을 하는 방법 - 텍스트에서 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여 - 빈도가 높은 문자는 짧은 코드를 가지고, 빈도가 낮은 문자는 긴 문자가 됨 접두부(prefix code) 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진코드의 접두부가 되지 않은 코드 겹치지 않도록 이진코드를 만드든 것 허프만 코딩은 프리픽스 코드가 되어야만 디코딩 했을때 문제가 발생하지 않기 때문에 적용 되어야 함 *최적코드: 인코딩된 메시지의 길이가 가장 짧은 코드 인코딩 방법 1. 주어진 텍스트에서 각 문자의 출현 빈도수를 계산 2. 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진코드를 부여 3. 주어진 텍스트의 ..

article thumbnail
동적계획법 (Dynamic Programming)
자료구조 2021. 5. 15. 20:54

동적계획법(Dynamic Programming) 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말 - 복잡한 문제(complex problem)를 작은 문제(sub problems)로 나눔 - 작은 문제의 해는 복잡한 문제를 풀기위한 부분 해가 됨 - 복잡한 문제를 풀기위한 작은 문제들은 자주 등장하기 때문에 작은 문제가 나타날때 마다 계산할 필요 없이 해를 저장해놨다가 동일한 문제가 나오면 재 활용하여 시간을 절약 동적프로그래밍으로 풀어야하는 문제는 다음과 같은 2가지 특성을 가짐 - Overlapping Subproblems - Optimal Substructure Overlapping Subproblems(겹치는 부분문제) : 중복 하위 문제 - sub-sub problem 간에 중복되는 경우가 ..

article thumbnail
유니온 - 파인드 (Union - Find)
자료구조 2021. 5. 15. 20:33

유니온 - 파인드 알고리즘 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 - 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조 - 집합을 구현하는데 트리구조를 이용하여 구현 - 여러 노드가 존재할때 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 - find : x가 어떤 집합에 포함되어있는지 찾는 연산, 집합의 루트 노드경로를 짧게 압축 시킴 - Union : x와 y가 포함되어 있는 집합을 합치는 연산 동작 방법 1. union 연산 확인 : 서로 연결된 두 노드를 확인 1-1. A의 루트 노드 A'와 B루트노드 B'를 찾는다(find) 2-2. A'를 B'의 부모 노드로 설정 2. 모든 연산을 처리할때까지 1번 반..

article thumbnail
레드 블랙 트리 (RED-Black Tree)
자료구조 2021. 5. 15. 20:25

레드블랙트리 (RED-Black Tree) 자가균형 이진탐색트리로써, 대표적으로 연관배열 등을 구현하는데 쓰이는 자료구조 - 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고 최악의 경우에도 우수한 실행시간을 보장 - 이진트리의 구조를 그대로 채용하되, 딱 하나 색상(Color)라는 속성을 노드에 추가함으로서 자동으로 균형을 유지 - 이진 검색트리의 모든 노드에 성질에 따라 레드 또는 블랙의 색상 특성 - 노드는 레드 또는 블랙의 색을 가짐 - 루트노드는 빨간노드일 수 없음 (검정으로 변환) - 모든 리프노드는 블랙 (NIL 노드는 모두 블랙) - 빨간노드는 두 개의 검정 노드를 가짐 (자식이 없을 경우 블랙 NIL 노드를 가짐) - 루트에서 리프로 가는 경로의 검정 노드의 수는 모두 같음..

article thumbnail
브루트 포스 알고리즘 (brute force), 백트래킹 (Backtracing) 알고리즘
자료구조 2021. 5. 12. 22:21

브루트 포스 알고리즘 (brute force) 완전탐색 알고리즘 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과를 가져오는 알고리즘 - 구현이 쉬운 편 - 시간적으로 매우 비효율적 - 알고리즘은 항상 최적해를 구할 수 있음 활용 - 선형구조: 순차탐색 - 비선형구조: 백트래킹(backTracking), 맹목적 탐색(BFS, DFS) 백트래킹 (Backtracing) 알고리즘 되추적이라는 뜻으로 이전 단계로 거슬러 올라가 다른 가능성을 찾아보는 방법 모든 가능성을 찾아보는 것은 맞지만 그중에서도 가능성이 있는 것만 찾는 가지치기(Pruning) 기법을 사용 *가지치기 : 조건을 맞출 수 없는 경우, 해당 경우를 제외 시키는 방법 브루트포스, 백트래킹, DFS 차이 브루트 포스 알고리즘 =..

검색 태그