힙 정렬 (Heap Sort) 힙 자료 구조를 이용하는 정렬 알고리즘 오름차순의 정렬을 위해 최대힙(maximum heap)을 구성 힙의 루트에는 가장 큰수가 저장됨 Pseudo code HeapSort Input: 입력이 A[1] .. A[n]까지 저장된 배열 A Output: 정렬된 배열 A 1. 배열 A의 숫자에 대해서 힙 자료 구조를 만든다. 2. heapSize = n // 힙의 크기를 조절하는 변수 3. for i = 1 to n - 1 4. A[1] ↔ A[heapSize] // 루트와 힙의 마지막 노드 교환 5. heapSize = heapSize - 1 // 힙의 크기를 1 감소 6. DownHeap() 7. return 배열 A Example Code private class HeapS..
kotlin
세그먼트 트리(Segment Tree) 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조 세그먼트 트리의 특징 이진 트리 기반 각 노드는 left, right 노드 두 개만의 자식을 가질 수 있음 구간 정보 저장 각 노드는 자신이 나타내는 구간의 정보를 저장 배열에서 특정 구간의 합을 구하는 방법 배열을 이용하여 선형적으로 구하기 트리 구조를 이용하여 구하기 배열을 이용하여 선형적으로 구하기 배열 A 배열 A에서 Index 2 .. 8 까지의 합 구하기 트리 구조를 이용하여 구하기 트리 A 이러한 세그먼트 트리가 존재할 경우 구간 합을 구하는 시간은 O(logn) 세그먼트 트리 구현 구간 합 저장..
Composable Function Jetpack Compose에서 가장 기본이 되는 요소 Composable Function의 의미 Composable 트리 구조 작성에 사용 Compose Runtime이 메모리에서 Composable 함수를 하나의 node로 이해 Composable Function 작성 방법 @Composable fun Greeting(name: String, modifier: Modifier = Modifier) { Text( text = "Hello $name!", modifier = modifier ) } @Composable 어노테이션을 이용하여 Composable 함수 작성 가능 어노테이션의 의미는 컴파일러에게 이 함수가 트리의 한 노드로 작동할 것이라는 의도 전달 함수에서..
Update 24.03.31 IR - Intermediate Representation Koltin 컴파일러가 소스파일을 해석하는 하나의 과정 Positional Memoization 위치 기억법 Compose에서 사용하는 런타임 최적화 방식을 지칭
Hilt 정의 및 기본 설정 프로젝트에서 종속 항목에 대해서 수동으로 삽입하는 코드를 줄이는 Android용 종속성 주입 라이브러리 모든 클래스와 종속 항목을 수동으로 구성 컨테이너를 사용하여 종속 항목을 재사용 및 관리 모든 Android 클래스에 컨테이너 제공 및 수명 주기 자동 관리 Hilt 목표 공식 문서 기반 표현 Android 앱을 위한 Dagger 관련 인프라 간소화 앱 간의 설정, 가독성 및 코드 공유를 용이하게 하기 위한 표준 구성요소 및 범위 세트 생성 테스트, 디버그 또는 출시와 같은 다양한 빌드 유형에 서로 다른 결합을 프로비저닝하는 쉬운 방법 제공 Hilt 설정 아래 환경은 Kotlin Domain Specific Language 기반으로 작성 Project Root build.g..
의존성 주입(Dependency Injection, DI) Hilt, Koin 등 다양한 Android DI를 돕는 라이브러리가 존재합니다. 그리고, Android 공식 사이트에서는 각종 편의성을 이유로 DI를 사용하길 권장합니다. 의존성(Dependency) 클래스 참조를 필요로 하는 다른 클래스 관계 A class를 만들기 위해서 B class가 필요한 것 class A(bClass: B = B()) { /* ... */ } class B { /* ... */ } 주입(Injection) 외부에서 객체를 생성하여 다른 객체에게 전달하는 것 Car class의 경우 Tire, Engine 등 다양한 부품을 외부에서 주입받아야함 private class Car( tire: Tire, engine: Eng..
쉘 정렬 (Shell sort) 삽입 정렬의 경우 맨 마지막 원소가 가장 작은 원소면 모든 숫자를 옮겨야함 이러한 단점을 보완 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동 동시에 앞부분의 큰 숫자는 뒷부분으로 이동 마지막에는 삽입 정렬 각 간격 별로 그룹을 설정하여 정렬 마지막에는 무조건 간격을 1로 설정하고 정렬 Pseudo code ShellSort Input: 크기가 n인 배열 A Output: 정렬된 배열 A 1. for gap h = [h0 > h1 >... > hk = 1] // 큰 gap부터 차례로 2. for i = h to n - 1 { 3. CurrentElement = A[i] 4. j = i 5. while (j >= h) and (A[j - h] > CurrentElement..
삽입 정렬 (Insertion Sort) 배열을 정렬된 부분 (앞부분)과 정렬 안 된 부분 (뒷부분)으로 나눔 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복 Pseudo code InsertionSort Input: 크기가 n인 배열 A Output: 정렬된 배열 A 1. for i = 1 to n - 1 { 2. CurrentElement = A[i] // 정렬 안된 부분의 가장 왼쪽원소 3. j = i – 1 // 정렬된 부분의 가장 오른쪽 원소로부터 왼쪽 방향으로 삽입할 곳을 탐색하기 위하여 4. while (j >= 0) and (A[j] > CurrentElement) { 5. A[j + 1] = A[j] // 자리 이동 6. j = j ..
선택 정렬 (Selection Sort) Input 배열의 원소 중 최솟값을 선택하여 0번 자리로, 0번 원소를 제외한 나머지 중 최솟값을 선택하여 배열의 1번 자리로 이동시키며 정렬 Pseudo code SelectionSort Input: 크기가 n인 배열 A Output: 정렬된 배열 A 1. for i = 0 to n - 2 { 2. min = i 3. for j = i + 1 to n - 1 { // A[i]~A[n-1]에서 최솟값을 찾기 4. if (A[j] < A[min]) 5. min = j 6. } 7. swap(A[i], A[min]) // min이 최솟값이 있는 원소의 인덱스 8. } 9. return 배열 A Example code private class SelectionSortE..
버블 정렬 (Bubble Sort) 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하여 정렬 Pseudo code BubbleSort Input: 크기 n 배열 A Output: 정렬된 배열 A 1. for pass = 1 to n - 1 2. for i = 1 to n - pass 3. if (A[i - 1] > A[i]) // 위의 원소가 아래의 원소보다 크면 4. swap(A[i - 1], A[i]) // 서로 자리를 스왑 5. return 배열 A Example code private class BubbleSortExample { fun solution(a: IntArray) { val sortedA = bubbleSort(a) println(sortedA.toList()) }..
