본문 바로가기

Study

(47)
[Algorithm] Segment Tree 문제Prefix Sum 배열을 이용하면 누적합을 O(n) 시간에 구할 수 있다.=> O(logn)에 누적합을 구할 수 있는 방법은 없을까?=> 배열을 수정할 수 있는 방법은 없을까? Segment Tree - 완전 이진 트리이다. (배열로 표현할 수 있다.)- 리프노드는 배열의 각 원소 값을 갖는다.- 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 값의 합을 갖는다.- 노드의 개수는 배열의 요소 개수의 4배가 된다.합 구하기각 노드가 나타내는 구간이 [start, end]일 때, [left, right] 합을 구하는 방법은? 루트부터 차례대로 다음을 점검한다. (4가지 경우의가 존재한다.) 1. [start, end]와 [left, right]가 겹치지 않는다.=> 아무것도 하지 않는다. 2. [star..
BIT (Binary Indexed Tree) 문제 Prefix Sum 배열을 이용하면 누적합을 O(n) 시간에 구할 수 있다. => O(logn)에 누적합을 구할 수 있는 방법은 없을까 ? 용어 정의 A[i] : 배열 A의 i번째 요소 L[i] : i를 2진수로 나타냈을 때 마지막 1에 해당하는 값 ex) 12 = 1100 => L[12] = 4 Tree[i] : A[i]부터 앞으로 L[i] 개의 값의 합 (이전 수) L[i]를 구하는 방법 L[i] = i & -i -i = ~i + 1 i = 1001101011101011000000000000 ~i = 0110010100010100111111111111 -i = 0110010100010101000000000000 i & -i = 000000000000000100000000000 PrefixSum[..
[Kotlin] 제네릭스 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. 제네릭과 파라미터 제네릭이란? => 클래스 내부에서 사용하는 특정 대상의 타입을 파라미터화 한 것 ex) ArrayList : T 타입을 가지는 원소의 ArrayList ex) HashMap : K타입의 키와 V타입의 값을 가지는 Entry의 HashMap + T, K V 를 타입 파라미터라고 한다. 제네릭을 사용하여 참조 변수 및 객체를 정의할 수 있다. - 타입 파라미터에 대한 실제 타입을 지정해야한다. - 타입 추론이 가능할 경우 타입 인자를 생략할 수 있다. fun main() { val list = ArrayList() list.add(5) list.add(6) // list.ad..
[Kotlin] 파일과 I/O 스트림 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. I/O 관련 클래스 InputStream: Byte 단위로 입력을 읽어 온다. - FileInputStream: 파일을 Byte 단위로 읽기 위한 클래스 OutputStream: Byte 단위로 출력한다. - FileOutputStream: 파일을 Byte 단위로 쓰기 위한 클래스 Reader: 문자 단위로 입력을 읽어 온다. - FileReader: 파일을 문자 단위로 읽기 위한 클래스 Writer: 문자 단위로 출력한다. - FileWriter: 파일을 문자 단위로 쓰기 위한 클래스 import java.io.FileWriter fun main() { val writer = File..
[Kotlin] 컬렉션 유틸리티 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. ++ 직접 코딩하라는 문제는 나오지 않고, 코드를 주고 어떤 의미인지 적는 문제가 출제됩니다. Collection의 생성 fun main() { val a1 = listOf(1, 2, 3) // unmutable list 생성 println(a1) // [1, 2, 3] // a1.add(4) 불가능 val a2 = mutableListOf(1, 2, 3) // mutable list 생성 a2.add(4) // 가능 println(a2) // [1, 2, 3, 4] val m1 = mapOf(1 to "I", 5 to "V", 10 to "X", Pair(50, "L")) // pair 객체를 통해 map 생성 print..
[Kotlin] 컬렉션 타입 + 항공대학교 김철기 교수님의 객체 지향 프로그래밍 과목 내용를 정리한 글입니다. 배열 Array C언어의 배열과 비슷한 특성을 갖는다. - 크기가 정해져 있다. - 원소의 삽입, 삭제가 불가능하다. - 원소의 대치는 가능하다. (원소 변경) Java의 기본 자료형이다. - Java와의 호환을 위해 Kotlin의 collection 관련 class를 상속 받지 않는다. iterator()를 제공한다. - for문을 통해 원소를 차례로 방문할 수 있게 한다. fun main() { val arr = arrayOf("Hello", "World", "Kotlin") for (elem in arr) { println(elem) } } Java와의 호환 및 성능을 위해 기본 자료형 별 Array 클래스가 있다. ..