파이썬으로 이진 탐색 구현하기

이진 탐색(binary search)은 정렬된 데이터에서 특정한 값을 아주 빠르게 찾는 방법이다. N개의 데이터 중에서 특정한 값 x를 찾을 때, 최악의 경우 N번의 비교가 필요한데, 이진 탐색의 경우 최대 log_{2}N만큼의 비교를 하게 된다. 즉 자료의 크기가 클수록 선형 탐색에 비해 성능이 매우 우수해진다. 다만 이진 탐색은 자료가 정렬되어 있다는 전제가 필요하다. (이 때문에 컴퓨터 과학에서는 정렬이 매우 중요하고, 성능이 좋은 정렬 알고리듬을 만들기 위해 많은 노력이 있어왔다.)

파이썬으로 이진 탐색 구현하기 더보기

생일 문제

30명의 사람이 있을 때, 이 중 생일 같은 사람이 최소 2명 있을 확률을 구하고 싶다. 어떻게 계산할 수 있을까? 이러한 문제를 생일 문제라 한다. 흥미로운 점은 생일 문제가 우리의 직관을 비웃는 것 같은 결과를 보인다는 것이다.

예를 들어 당신이 누군가를 만났다고 하자. 그 사람이 당신과 생일이 같을 확률은 얼마일까? 당신의 생일이 정해져 있으므로 그 사람의 생일은 365일 중 같은 날인 하루여야 한다. 이 때의 확률은 1/365로 약 0.274% 밖에 안된다. 이처럼 1년의 날 수가 365일이나 되기 때문에 생일이 같아질 확률이 매우 작아 보인다.

생일 문제 더보기

asyncio의 동기화수단들

asyncio는 단일 스레드에서 비동기 코루틴을 사용하여 동시성 처리를 한다. 따라서 asyncio의 세계에서는 적어도 멀티 스레드에서 발생할 수 있는 자원 선점문제가 없을 것이라 생각할 수 있다. 전적으로 틀린 것은 아니다. 스레드가 1개밖에 없기 때문에 메모리 내의 특정한 객체를 동시에 액세스하는 일은 없을 것이다. 그러나 그외의 IO와 관련된 자원은 여전히 선점 문제가 발생할 수 있다. 이러한 문제를 피하기 위해서 asyncio는 threading과 유사한 동기화 수단들을 제공하고 있으며, 이들의 사용 방법 또한 거의 유사하다. asyncio에서 제공하는 동기화 수단에는 다음과 같은 것들이 있다.

  • 락(Lock)
  • 이벤트(Event)
  • 컨디션(Condition)
  • 세마포어(Semaphore)
  • 바운디드세마포어(BoundedSemaphore)
asyncio의 동기화수단들 더보기

타입 지우기 – Type Erasure (Swift)

프로토콜 타입

우리가 만약 타입을 알 수 없는 어떤 객체의 특정한 메소드를 호출해야 하는 상황을 생각해보자. (어렵게 생각할 것 없이, 델리게이트 패턴에서 이것은 매우 흔한 일이다.) 타입을 알 수 없다는 것은, 그 객체가 공개하고 있는 인터페이스를 알 수 없다는 뜻이며, 따라서 어떤 메시지를 보내는 것이 불가능하다는 것을 의미한다. 하지만, 서로 다른 타입들이 같은 이름의 메소드를 구현해 둘 것을 약속만 한다면, 이야기가 달라진다.

프로토콜은 미리 정의된 인터페이스의 모음으로, 이를 따르는 타입들은 그 프로토콜에 명시된 인터페이스를 구현해놓은 것으로 가정할 수 있다. 동적 프로그래밍에서는 어떤 객체가 A타입처럼 행동하면 A타입으로 간주할 수 있다고 한다. (어떤 새가 오리처럼 날고, 오리처럼 꽥꽥거린다면 그 새를 오리라 부르지 않을 이유가 무엇인가) 굳이 동적 언어가 아니더라도, 어떤 객체가 그 실제 타입 T가 무엇이든간데, 프로토콜 P를 준수하고 있다면 우리는 P 타입에 대한 상호작용만 한다는 가정하에서 그 객체를 P 타입으로 보아도 무방할 것이다. 아니면 다른 S타입의 객체가 P를 준수한다고 하면, 두 객체를 여전히 같은 P 타입으로도 볼 수 있을 것이다.

타입 지우기 – Type Erasure (Swift) 더보기

Opaque 리턴타입(Swift 5.1)

이 글을 다음 문서를 부분 번역한 것입니다.
https://docs.swift.org/swift-book/LanguageGuide/OpaqueTypes.html

Opaque 리턴 타입이 있는 함수나 메소드는 리턴 값에 대한 정보를 숨깁니다. 함수의 리턴 타입에 대한 구체적인 타입 정보를 제시하는 대신에, 리턴 값은 그 것이 따르는 프로토콜만으로 기술됩니다. 타입 정보를 숨기는 것은 모듈이 외부에 내놓는 코드에서 실제 리턴값의 타입은 내부에서만 유지관리될 수 있게 만들기 때문에 유용하게 사용될 수 있습니다. 리턴 값의 타입이 프로토콜 타입인 것과는 달리 Opaque 타입은 동일성을 유지합니다. 그리고 이때 컴파일러는 타입 정보에 액세스할 수 있지만, 모듈의 클라이언트는 그렇게 할 수 없습니다.

Opaque 리턴타입(Swift 5.1) 더보기