전체 글

Binary search tree Search Tree 데이터 구조는 다음과 같은 operations를 제공한다. - Search : 탐색 - Minimum : 최솟값 - Maximum : 최댓값 - Predecessor : 다음에 오는 요소 - Successor : 이전 요소 - Insert : 삽입 - Delete : 삭제 이와 같은 operations들은 트리의 깊이에 실행 시간이 비례한다. 완벽한 binary tree를 이룰 때에는 $\Theta(\lg(n))$ 의 시간 복잡도를, 만약 한쪽으로 치우쳐져 linear chain에 가깝다면 $\Theta(n)$의 시간 복잡도를 가지게 된다. What is a binary search tree?그렇다면 이분 탐색 트리란 무엇일까? 이분 탐색은 이분 트..

앞서 분할 정복 알고리즘의 예시 중에는 퀵 정렬도 있었는데, 이번 시간에는 퀵 정렬에 대해 알아보려고 한다. 우리는 계속해서 더 나은 Complexity를 가진 알고리즘을 알아보고 있기 때문에 퀵 정렬의 장·단점 또한 알아두는 것이 중요할 것이다. pros and cons 앞으로 다룰 정렬에는 더 나은 복잡도가 있을지도 모르겠다 (아직 공부 중이므로 알 수 없다). 하지만 퀵 정렬의 경우 앞서 살펴본 병합, 힙 정렬처럼 일반적으로 $\Theta(n·\log{n})$의 시간 복잡도를 가지며, 추가적인 메모리 공간이 필요하지 않은 in-place 알고리즘에 속한다. 그러나 다른 알고리즘과 다른 특이한 점은 퀵 정렬의 경우 최악의 상황에서는 $\Theta(n^{2})$의 시간을 가진다는 것이다. divide ..

우리는 보통 알고리즘을 공부할 때 가장 많이 다루는 게 바로 정렬 알고리즘이다. 왜 이렇게 중요하게 여겨질까? 그 이유는 프로그램 자체에서 정렬된 정보를 원하는 경우가 많고, 대부분의 알고리즘의 기초를 다질 수 (basic building block)가 있으며, 알고리즘에서 sorting 이 key subroutine으로 종종 사용되기 때문이다. insertion, merge sort 우리는 지금까지 analysis, divide and conquer 등 알고리즘에 대해 공부해 나가면서 항상 정렬 알고리즘을 다뤄왔다. 지금까지 다룬 알고리즘 중 insertion sort, merge sort는 각각의 장단점이 존재한다. 먼저 insertion sort는 $O(n^{2})$의 다소 느린 계산 속도를 가지고..

이번에는 분할 정복으로 해결할 수 있는 Maximum Subarray 문제를 알아보자. Goal 주식 시장에서 가장 큰 수익을 얻기 위해서는 낮은 가격에 사서 높은 가격에 사는 것이 중요하다. 다음 그래프를 보자. 어떤 상품의 가격을 날짜별로 나타내고 있고 Change는 그날 기준으로 전날과의 차이를 의미한다. 어떻게 이 문제를 해결할 수 있을까? 단순히 생각해 보면 주어진 표에서 가장 높은 가격과 가장 낮은 가격을 찾으면 된다. 하지만 여기에는 반례가 존재한다. 가장 높은 가격이 가장 낮은 가격보다 전에 해당하는 경우이다. 따라서 이 방법으로 모든 문제를 해결할 수 없다. Solution #1, Brute-force solution 주어진 n개의 인스턴스 중에 2개를 고르는 모든 경우의 수를 따지는 방..

Divide and conquer 대표적인 알고리즘의 갈래 중 하나인 분할 정복은, 하나의 커다란 문제를 여러 작은 문제로 나눈 후 (Divide), 작은 문제를 해결하고 나서 다시 합쳐 (Combine) 해결하는 (Conquer) 방법이다. Insertion sort 분할 정복이 주는 이점이 무엇일까? 그걸 알아보기 전에 앞서 배웠던 삽입 정렬 (Insertion sort)을 생각해보자. 삽입 정렬은 incremental approach로, 모든 요소를 순차적으로 방문하는 방식을 택한다. 그러다 보니 input instance의 (이미) 정렬된 정도에 따라 최소 Ω(n)에서 최대 O(n2)의 시간 복잡도를 지니게 된다. 그렇다면 mergesort의 시간 복잡도는 어떨까? 결론부터 말하자면 O(n lg ..

Analyzing an algorithm 알고리즘을 분석한다면 다양한 요소들을 고려해야 할 것이다. Memory, communication bandwidth, or computer hardware 등 알고리즘이 요구하는 자원을 예측하는 것도 중요하지만, 대부분의 경우 Computational time이 제일 중요하게 여겨진다. 우리는 다양한 알고리즘 중에서 가장 효율적인 알고리즘을 찾아낼 수 있고, 상대적으로 빈약한 알고리즘을 걸러낼 줄 알아야 한다. Complexity 어떤 알고리즘이 효율적인 알고리즘인지 알기 위해서 중요한 것은 바로 복잡도이다. 주어진 수 집합을 정렬하는 문제 해결의 경우를 생각해 보면, 같은 크기의 수 집합이라고 하더라도 그 구성에 따라 알고리즘의 수행 시간이 다를 것이다. 우리는..

반례를 찾을 수 없다 ≠ 좋은 알고리즘이다 우리는 어떠한 명제가 자명하다는 사실을 증명을 통해 밝혀내야 한다. 대표적인 방법으로는 Induction이 있다. Induction Principle 수학적 귀납법의 원리를 따른다. 1. State that the proof uses induction - induction을 이용하여 증명할 것을 명시 2. Define an appropriate predicate P(n) - 최종적으로 증명할 명제를 명시 3. Prove that P(0) is true - 이 시작점을 우리는 Base case or Basis step이라고 부름 4. Prove that P(n) implies P(n+1) for every natural number n - 이걸 inductive ..

Thread?- A single unique execution context- Mechanism for concurrency (동시성) + can also run in parallel (병렬성)- Protection (보호) → 쓰레드 간 자원 접근을 제어하고 안전하게 관리하기 위한 메커니즘 MTAO (multiple things at once)- 운영 시스템은 프로세스, 인터럽트, 백그라운드 시스템 유지 등 다양한 것들을 한 번에 핸들링할 수 있어야 함- 네트워크 서버, 병렬 프로그램, UI를 지닌 프로그램, 그리고 network/disk bound 프로그램도 마찬가지→ 이러한 것들을 가능하게 해주는 것이 바로 Thread스레드는 동시성의 유닛이고, 각각의 쓰레드는 하나 혹은 한 태스크를 표현할 수 있..

Algorithm 좋은 알고리즘의 특성 1. Correct 2. Efficient 3. Easy to implement 이 순서대로 중요하게 여기고, 이 세가지를 동시에 만족시키지 못할 수도 있음. Collect algorithm? - 모든 input에 대해 정확한 output에 멈춰야 한다. - 프로그램이 멈추지 않거나, 오답에서 멈춘다면 옳은 알고리즘이 아님. - 가끔 incorrect algorithm이 유용하게 쓰일 데가 있음! → Error rate 제어가 가능하다면 - Correct vs Incorrect를 구별하려면 Proof가 필요 Correctness를 증명하려면 입력 가능한 instance를 명확히 알아야 하고. 알고리즘의 출력값의 요구되는 특성을 명확히 알아야 함. 문제에 대한 오류 ..

서버 개발자가 아니거나, 간단한 사이드 프로젝트를 하는 입장에서 백엔드를 필요로 하는 상황이 굉장히 많이 발생한다. 이를 해결해 줄 것이 바로 Google의 Firebase인데, 지금 내가 서비스 운영 중인 명언 iOS 앱 또한 간단한 명언 데이터를 수집/제공해 줄 목적으로 Firebase의 Realtime Database 서비스를 이용 중이다. 이 앱의 Android OS는 동료 개발자가 운영하고 있는데, 현재는 서비스 앱 말고도 수집된 명언 데이터를 처리하는 간단한 앱 또한 이 친구가 만들어 둬 좀 더 수월한 데이터 처리를 돕고 있었다. 이 앱을 운영한 지가 어엿 4년 차가 돼 가는데, 둘 다 소프트웨어 공학적 지식이 불충분한 상태에서 시작했기에 디자인 패턴을 고려하지 않았고, 기능을 추가할수록 코드..