반응형 분류 전체보기166 허프만 코딩 허프만 코딩문자의 빈도를 이용해 압축하는 방법으로 빈도가 높은 문자는 적은 비트로, 빈도가 낮은 문자는 높은 비트로 표현하여 필요한 비트 수를 줄여 압축하는 방식(-> 높은 압축률)문자열 압축을 위해 허프만 트리를 사용함각 문자에 대한 출현 빈도수를 구하여 내림차순으로 정렬한 뒤 빈도수가 가장 낮은 두 값을 자식 노드로, 빈도수의 합을 부모노드로 하는 연산을 반복적으로 수행하여 트리를 구성함허프만 트리를 구성하면 모든 문자열은 리프노드에 위치함왼쪽가지를 1, 오른쪽 가지를 0으로 표현하여 리프노드(문자열)에 노드에 도달하는데 거쳐가는 비트로 문자열 표기-> 문자열이 모두 리프노드에 위치하므로 문자열 간에 접두부가 겹치지 않음-> 문자열을 표현하는데 겹치는 비트가 없으므로 압축 이후 데이터 손실이 발생하지.. 2025. 6. 12. [정렬 알고리즘] 합병 정렬, 퀵정렬, 계수 정렬 합병정렬(머지소트)주어진 배열을 크기가 1인 배열이 될때까지 두개씩 쪼개나가는 분할 과정을 진행한 후 하나씩 합쳐나가며 정렬을 수행함(분할정복 알고리즘)합병정렬을 위해 추가적인 메모리 공간을 필요로함(제자리 정렬X)중복된 데이터에 대해 입력순서를 유지하는 안정정렬시간복잡도 : O(NlogN)2개씩 분할하는 과정을 보면 마치 이진트리가 생성되는 절차와 같다. -> logN크기가 1인 배열이 되면 다시 2개씩 합병하며 정렬을 수행함 -> N따라서, 정렬에 O(NlogN)의 시간복잡도를 보임분할정복 알고리즘분할 정복알고리즘은 큰 하나의 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음 결과를 모아 해결하는 기법이다.일반적으로 쪼갠 문제를 또다시 쪼개어 나가는 방식으로 순환호출 방식을 이용하여 구현한다. N.. 2025. 6. 12. [정렬 알고리즘] 버블, 삽입, 선택, 힙 정렬 정렬데이터를 특정한 기준에 따라 순서대로 나열하는 것안정정렬(Stable Sort) vs 불안정정렬(Un-stable Sort)안정 정렬은 중복된 값이 존재하는 경우 정렬 이후에도 입력순서와 동일한 순서를 유지하는 정렬이다.불안정 정렬은 중복된 값이 존재하는 경우 정렬 이후 입력순서와 상관없이 임의로 정렬된 경우이다.정렬 결과가 늘 동일하게 유지되어야하는 경우 또는 중복시에 입력 순서를 유지해야하는 경우에는 안정 정렬을 사용하는 것이 유리하고,그에 대한 기준 없이 성능이 더욱 중요하다면 불안정 정렬을 사용하는 것이 유리할 수 있다.(불안정 정렬의 경우, 중복시 어떻게 처리할지에 대한 기준을 정하지 않기에 추가적인 연산을 수행하지 않는다.)안전정렬의 종류 : 삽입, 버블, 병합불안정 정렬의 종류 : 선택,.. 2025. 6. 12. Map과 Set이란(Hash, Tree 기반 자료형 비교) Map맵은 비선형 자료구조로 key-value 쌍으로 데이터를 저장하는 특징을 갖고 있다.맵의 key는 중복이 허용되지 않으나, value는 중복이 허용된다.자바의 맵 자료형에는 대표적으로 HashMap과 TreeMap이 존재한다.HashMap은 해시테이블 기반으로 자료를 관리하기에 조회, 삽입, 삭제 연산에 O(1)의 시간복잡도를 갖는다.TreeMap은 균형 이진탐색트리의 한 종류인 레드블랙 트리를 통해 데이터를 관리하기에 조회, 삽입, 삭제 연산에 O(logN)의 시간복잡도를 갖는다. Set셋은 비선형 자료구조로 중복이 허용되지 않는다.중복을 허용하지 않는 집합과 같은 개념이다.자바의 셋에는 HashSet, TreeSet이 존재한다.HashSet은 해시테이블 기반으로 자료를 관리하기에 조회, 삽입, .. 2025. 6. 12. 이전 1 ··· 3 4 5 6 7 8 9 ··· 42 다음 반응형
