![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/y5iby/btsGlTlcD8z/0u2kkkjZOoc18ZHvAIFYw1/img.png)
이번에는 분할 정복으로 해결할 수 있는 Maximum Subarray 문제를 알아보자. Goal 주식 시장에서 가장 큰 수익을 얻기 위해서는 낮은 가격에 사서 높은 가격에 사는 것이 중요하다. 다음 그래프를 보자. 어떤 상품의 가격을 날짜별로 나타내고 있고 Change는 그날 기준으로 전날과의 차이를 의미한다. 어떻게 이 문제를 해결할 수 있을까? 단순히 생각해 보면 주어진 표에서 가장 높은 가격과 가장 낮은 가격을 찾으면 된다. 하지만 여기에는 반례가 존재한다. 가장 높은 가격이 가장 낮은 가격보다 전에 해당하는 경우이다. 따라서 이 방법으로 모든 문제를 해결할 수 없다. Solution #1, Brute-force solution 주어진 n개의 인스턴스 중에 2개를 고르는 모든 경우의 수를 따지는 방..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/cgkcPM/btsGhEQzwhB/QC7NxqI73ylSatfAiVXFnK/img.png)
Divide and conquer 대표적인 알고리즘의 갈래 중 하나인 분할 정복은, 하나의 커다란 문제를 여러 작은 문제로 나눈 후 (Divide), 작은 문제를 해결하고 나서 다시 합쳐 (Combine) 해결하는 (Conquer) 방법이다. Insertion sort 분할 정복이 주는 이점이 무엇일까? 그걸 알아보기 전에 앞서 배웠던 삽입 정렬 (Insertion sort)을 생각해보자. 삽입 정렬은 incremental approach로, 모든 요소를 순차적으로 방문하는 방식을 택한다. 그러다 보니 input instance의 (이미) 정렬된 정도에 따라 최소 Ω(n)에서 최대 O(n2)의 시간 복잡도를 지니게 된다. 그렇다면 mergesort의 시간 복잡도는 어떨까? 결론부터 말하자면 O(n lg ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/qxrts/btsFUCYrJpt/piNAAMGuryKqJjoLNOUag0/img.png)
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 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/AzSrT/btsFACTvurz/SbmNji234ZtnMUBcYJxajk/img.png)
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를 명확히 알아야 하고. 알고리즘의 출력값의 요구되는 특성을 명확히 알아야 함. 문제에 대한 오류 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/cEDnvl/btsD0J7AC1N/qpdPc9Zk82GEUpcHedNxkK/img.png)
서버 개발자가 아니거나, 간단한 사이드 프로젝트를 하는 입장에서 백엔드를 필요로 하는 상황이 굉장히 많이 발생한다. 이를 해결해 줄 것이 바로 Google의 Firebase인데, 지금 내가 서비스 운영 중인 명언 iOS 앱 또한 간단한 명언 데이터를 수집/제공해 줄 목적으로 Firebase의 Realtime Database 서비스를 이용 중이다. 이 앱의 Android OS는 동료 개발자가 운영하고 있는데, 현재는 서비스 앱 말고도 수집된 명언 데이터를 처리하는 간단한 앱 또한 이 친구가 만들어 둬 좀 더 수월한 데이터 처리를 돕고 있었다. 이 앱을 운영한 지가 어엿 4년 차가 돼 가는데, 둘 다 소프트웨어 공학적 지식이 불충분한 상태에서 시작했기에 디자인 패턴을 고려하지 않았고, 기능을 추가할수록 코드..
본격적인 객체 지향 프로그래밍의 시작이다. 클래스를 선언하고 초기화하고 사용하는 법까지 account라는 Class를 통해 알아보도록 하자. 헤더 파일 먼저 class를 선언하는 곳은 소스 파일이 아닌 헤더 파일이라는 사실이 중요하다. 그 이유는 클래스를 헤더 파일에 선언함으로써 코드의 재사용성, 가독성, 유지 보수성을 높일 수 있고, 컴파일 타임 최적화와 컴파일 시간 단축을 이룰 수 있기 때문이며, 객체 지향 프로그래밍의 핵심 중 하나이다. 우리가 만들 account라는 클래스는 다음과 같은 구조를 가진다. 1. 계좌의 잔액 2. 계좌의 잔액을 로그에 출력하는 메서드 3. 계좌의 잔액을 다른 계좌에 전달하는 메서드 // account.h class account { int balance; public:..
- Total
- Today
- Yesterday
- DP
- D3
- 정보시각화
- 백트래킹
- 백준
- c++
- DFS
- Array
- 하노이탑이동순서
- SceneDelegate
- swift
- SVG
- pyrebase
- PS
- CSV
- 알고리즘
- how to remove border of tabbarcontroller
- 파이썬
- Python
- 보라매사옥
- 자료구조
- CSS
- HTML
- Javascript
- how to start without storyboard
- TIP
- BOJ
- ios
- xcode
- 곱셈의 역원
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |