Study (47) 썸네일형 리스트형 [Algorithm] 정렬: 버킷 정렬, 기수 정렬 + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 비교에 기반한 정렬의 시간 복잡도 한계 => 두 원소의 비교에 기반한 정렬 알고리즘은 Θ(nlogn)보다 빠르게 동작할 수 없다. 버킷 정렬 (Bucket sort) 정렬될 데이터가 자릿수라는 개념이 있다면 이를 이용한다. ex) 정렬될 데이터가 택배 주소라면, 전체를 다 보지 않고 처음 위치를 보고 데이터를 분류할 수 있다. 분류한 데이터를 각각 정렬하고, 이를 이으면 정렬이 완성된다. - c개의 버킷으로 모든 원소가 균등하게 배분되어 각각 n / c개가 들어갔을 경우 => n / c개를 Θ((n/c) log (n/c)) 시간에 정렬할 수 있고, 이를 다시 합치면 => c(n/c) log(n/c).. [Algorithm] 정렬: 힙 정렬 + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 힙 정렬 (Heapsort) 버블 정렬과 비슷하게 1등을 뽑아내고, 나머지 원소에서 1등을 계속 뽑아내면서 정렬한다. 버블 정렬: 남은 원소에서 1등을 다시 비교를 통해서 찾는다. 힙 정렬: 힙을 이용하면, 1등을 뽑아낸 뒤 나머지 원소에서 1등을 뽑을 때, 다시 비교할 필요 없이 2등이 자동으로 1등이 된다. => 힙 생성 -> 루트 원소 제거 -> 힙을 유지 힙 (Heap) - 완전 이진 트리이다. + 원소가 n개인 힙의 모양은 1개이다. (높이는 logn) 최대 힙: 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진 트리 최소 힙: 부모 노드의 키 값이 자식 노드보다 작거나 같은.. [Kotlin] 함수형 프로그래밍 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. 고차 함수 - 함수를 파라미터로 받는 함수이다. fun initializeIntArray(n: Int, initializer: (Int) -> Int): IntArray { // initializer라는 (Int) -> Int 함수 타입의 변수를 파라미터로 받는다. // (Int) -> Int는 Int를 파라미터로 받아서 Int를 반환하는 함수 타입 val arr = IntArray(n) // 0으로 초기화 된 n개의 정수를 갖는 배열 for (i in 0 until n) { arr[i] = initializer(i) // initializer 함수에 i를 넣은 값을 arr[i]에 저장 } return arr } fun m.. [Kotlin] 객체 (Object) + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. 객체 (object) - 오직 하나의 인스턴스만 존재하는 클래스는 object라는 키워드로 정의하며 객체라 부른다. - 객체는 선언과 동시에 인스턴스가 생성된다. (객체 이름 = 타입 이름 = 인스턴스 이름) object Application { // 타입 이름이자 객체 이름 val name = "My Application" override fun toString() = name // 객체의 이름 반환 // toString 은 이미 상위 클래스에서 사용되고 있으므로 override 사용 (모든 객체는 toString 함수를 갖고 있다.) fun exit() {} // 빈 함수 } fun main() { println(App.. [Kotlin] 단순한 변수 이상인 프로퍼티 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. 최상위 프로퍼티 - 클래스에 소속되지 않은 프로퍼티는 전역 변수/상수의 역할을 한다. - public/internal/private 등의 가시성 지정이 가능하다. private val prefix = "Hello, " // 전역 변수 // private 선언이기 때문에 다른 파일에서는 호출이 불가능하다. fun main() { val name = readLine()?: return // null이면 return println("$prefix $name") } 늦은 초기화 (lateinit) - 생성자에서 초기화되지는 않지만, 프로그램 흐름 상 실사용 시 초기화되는 것이 명백한 변수에는 lateinit이라는 예약어로 표기하여.. [Algorithm] 정렬: 병합 정렬, 퀵 정렬 + 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 분할 정복 기법 (Divide-and-Conquer) 문제의 크기가 커지면 더 풀기가 어렵다. => Divide: 원래 문제를 독립적으로 풀 수 있는 작은 문제로 나눈다. => Delegate: 각각의 문제를 푼다. => Combine: 각각의 문제의 답을 이용하여 원래 문제의 답을 만든다. 정렬 문제에 대한 분할 정복 기법 1. 병합 정렬 (Mergesort) 2. 퀵 정렬 (Quicksort) 병합 정렬 Divide: 정렬할 리스트를 앞쪽 반, 뒤쪽 반으로 나눈다. Delegate: 앞쪽 반을 정렬한다. Delegate: 뒤쪽 반을 정렬한다. Combine: 이 둘을 합쳐서 하나의 정렬된 리스트를 만든다. - 앞쪽 반.. 이전 1 2 3 4 5 6 7 8 다음
