studlog

퀵소트는 피봇을 정하는 파티션 과정과 2번의 분할 과정으로 이루어져 있다. $n$개의 원소를 퀵소트로 정렬하는 데 걸리는 시간을 $T(n)$이라 할 때 $T(n)$은 $m$개와 $n-m$개로 분할된 원소를 정렬하는 시간과 $n$개의 원소 중 피봇을 정하는 파티션 과정으로 나눌 수 있다. 아래 식을 활용해서 퀵소트의 시간복잡도를 구할 수 있다.$$T(n)=T(m)+T(n-m)+C(n)$$ Best case time complexity퀵소트는 피봇이 항상 배열을 균등하게 분할하여 분할의 횟수가 $\log n$번 실행되는 경우에 $O(n\log n)$에 동작한다. 최선의 방법으로 퀵소트를 할 때 걸리는 시간을  $T(n)$이라고 하면 $T(n)$은 아래와 같다...

Run Loop란런 루프(Run loop)는 스레드에 전달된 소켓, 파일, 키보드, 마우스 등의 입력과 타이머 객체를 처리하는 객체이다. 런 루프를 사용해 스레드의 활동 상태를 조정할 수 있으며 이것이 런 루프가 고안된 이유이다. 모든 스레드는 생성될 때 자신만의 런 루프를 갖는다. 메인 스레드에 생성된 메인 런 루프는 생성과 동시에 자동으로 실행(Start)되지만 그 외 스레드의 런 루프는 자동으로 실행되지 않는다. 따라서 개발자는 적절한 타이밍에 직접 런 루프를 실행시켜 이벤트를 처리해야 한다. 입력 이벤트의 종류런 루프는 2가지 입력 이벤트를 받는다. Input source는 다른 스레드나 애플리케이션에서 비동기적으로 전달된 이벤트이다. Timer source는 예정된 시간 또는 반복된 Interv..

초기화(Initialization) 인스턴스의 저장 프로퍼티는 사용하기 전에 반드시 특정 값 또는 nil로 초기화되어야 한다. 초기화(Initialization)는 클래스, 구조체, 열거형의 프로퍼티 초기 값을 설정하는 단계이다. 초기화 과정은 초기자(Initializer)를 정의해 구현할 수 있다. Struct Initializer 구조체의 초기자를 만드는 간단한 방법은 초기자 내부에서 저장 프로퍼티의 초기값을 지정해주는 방법으로 매개변수(parameter)가 없는 init 키워드를 사용하는 것이다. 저장 프로퍼티의 초기 값을 항상 미리 지정된 값으로 초기화한다. 만약 모든 저장 프로퍼티의 초기값이 설정되어 있고, 어떤 초기자도 정의하지 않았다면 스위프트는 모든 저장 프로퍼티를 초기값으로 초기화하는 기..

단조 스택(Monotonic Stack) 이란단조 스택(Monotonic Stack)은 스택(Stack) 자료 구조의 변형 중 한 개로 스택의 원소들이 단조 증가 혹은 단조 감소 상태인 스택을 말한다. 겉보기에는 힙(Heap) 자료구조와 비슷하게 보이지만 다르다. 정확하게 말하자면 단조 스택이란 스택에 원소를 삽입할 때 스택의 상태가 단조 증가 혹은 감소를 유지되는 것을 말한다. 사실 단조 스택은 자주 쓰이지는 않는다. 하지만 특정 문제에서는 단조 스택이 힘을 발휘할 때가 있다. 그중 한 개는 자신보다 처음으로 크거나 작은 원소의 값을 찾는 문제(Next Greater or Smaller Element)이다. 예를 들어 배열 [2, 1, 2, 4, 3]가 주어졌을 때 자신보다 처음으로 큰 원소를 저장하는..

Key-Value-Observing Key-Value-Observing (KVO)는 코코아 프로그래밍 패턴 중 한 개로 프로퍼티의 변화를 다른 객체에 알릴 때 사용할 수 있다. 애플리케이션의 뷰(View) 또는 모델(Model)의 프로퍼티 변화를 컨트롤러(Controller)에 알릴 때 유용하다. KVO는 프로퍼티가 변경될 때마다 알림을 보내기 위한 체계를 구현할 필요가 없다. 프로퍼티의 변경 사항이 생기면 관찰 객체에 직접 알림을 전달하기 때문에 NSNotificationCenter와 다르게 관찰자에게 변경 사항을 알리는 중앙 개체가 필요 없다는 것이 장점이다. NSObject를 상속할 때 KVO를 위한 기본적인 메서드가 NSObject에 이미 구현되어 있기 때문에 이러한 메서드를 오버라이드 할 필요도..

Key-Value-Coding 많은 프로그래밍 언어에서 캡슐화된 객체의 프로퍼티 값을 얻거나 수정하기 위해서는 객체에 정의한 getter, setter 메서드를 통해 접근할 것이다. 아마 스위프트도 getter, setter 메서드 혹은 연산 프로퍼티 등 비슷한 방식으로 접근할 것이다. 이러한 객체의 프로퍼티에 직접적으로 접근과는 다르게 Objective-C와 스위프트는 Key-Value-Coding(KVC)를 통해 객체의 프로퍼티에 간접적으로 접근할 수 있다. Objective-C에서 KVC 방식을 사용하기 위해서는 객체가 NSKeyValueCoding 프로포콜을 채택해야 한다. 다행히도 프로토콜 메서드의 기본적인 구현이 되어 있기 때문에 따로 구현해야 하는 것은 없다. Identifying an Ob..

정적 디스패치(Static Dispatch)와 동적 디스패치(Dynamic Dispatch) 스위프트는 C++, 자바 등 많은 언어들처럼 클래스 상속을 지원하고, 슈퍼 클래스를 상속한 서브 클래스에서 프로퍼티와 메서드 오버라이딩을 할 수 있다. 따라서 프로그램은 런타임 단계에서 동일한 이름의 메서드들 중 어떤 메서드를 실행시켜야 할지 결정해야 한다. 이 과정을 동적 디스패치(Dynamic Dispatch)라고 한다. 스위프트의 동적 디스패치는 기본적으로 vtable를 참조하는 간접 호출(Indirect Call)이다. 따라서 컴파일 단계에서 호출될 함수를 결정하여 직접 호출(Direct Call)하는 정적 디스패치(Static Dispatch) 보다 느리다. class A { var aProperty: ..

스위프트는 인덱스로 문자열(String)의 요소에 접근하려고 하면 'subscript(_:)' is unavailable: cannot subscript String with an Int, use a String.Index instead. 에러 메시지를 보여준다. 스위프트의 문자열은 왜 인덱스로 요소에 접근하지 못할까? let array: [Int] = [0, 1, 2, 3, 4, 5] print(array[3]) let string: String = "Hello world" // error print(string[3]) 스위프트의 문자열은 서브스크립트(subscript)를 지원하지 않기 때문에 인덱스를 이용해 요소에 접근할 수 없다. 서브스크립트를 지원하지 않은 이유를 알기 위해선 스위프트가 어떻게 문..

다섯 개의 사진이 순서대로 돌아가는 캐러셀을 만들어보자. 컬렉션 뷰 사용하기 컬렉션 뷰의 페이징 기능을 사용해 캐러셀을 만들 수 있다. 수평 스크롤인 컬렉션 뷰를 추가하고 레이아웃을 잡은 후 컬렉션 뷰의 Paging Enabled 속성을 True로 바꾼다. 그리고 셀에 이미지 뷰를 넣으면 된다. 자연스러운 페이징을 위해 컬렉션 뷰의 Min Spacing을 0으로 한다. Min Spacing을 0으로 하지 않으면 이미지가 넘쳐서 보인다. 이제 셀 사이즈를 조절하여 한 개의 이미지씩 보이게 바꾸자. UICollectionViewDelegateFlowLayout 프로토콜을 사용해서 셀 아이템의 크기를 정하자. extension RxViewController: UICollectionViewDelegateFlow..

AnyObject AnyObject는 모든 클래스가 암묵적으로 준수할 수 있는 프로토콜이다. AnyObject는 타입이 정해지지 않은 객체에 사용할 수 있다. 모든 클래스, 클래스 타입 또는 클래스 전용 프로토콜의 인스턴스는 AnyObject를 타입으로 사용할 수 있다. let label: UILabel = UILabel() let button: UIButton = UIButton() let imageView: UIImageView = UIImageView() let a: AnyObject = label let b: AnyObject = a.self let c = button.self let array: [AnyObject] = [ label, button, imageView.self ] protocol..