Priority Queue ( 우선순위 큐) 컴퓨터 과학에서, 우선순위 큐는 평범한 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 갖는다면 그들은 큐에서 그들의 순서에 의해 처리된다(선입선출). * 우선순위 큐가 힙이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념이다. 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다. 우선순위 큐는 최소한 다음의 연산이 지원 되어야 한다: - insert_with_priority: 하나의 원소를..

Sorting 입력: 배열 A [ 1...n ] 의 수들 출력: A의 원소들을 갖는 B[1] ≤ B[2] ≤ … ≤ B[n] 의 배열 B => 이를 어떻게 하면 효율적으로 수행할 수 있을까? * Sorting의 응용분야 - MP3 라이브러리 정렬하기 - 전화번호부 관리 - 정렬함으로써 쉬워지는 문제들: 중간값 찾기, 가장 가까운 수 찾기, 이진탐색, 큰 오차값 걸러내기 - 데이터 압축 => 정렬로 복제품을 찾을수도 있음 - 컴퓨터 그래픽스에서의 렌더링 Insertion Sort ( 삽입 정렬 ) 삽입정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째 반복 후의 결과 배열은..

배우는 것: - 알고리즘이란 무엇인가? 시간이란 무엇인가? - 랜덤 접근 기계 (Random Access Machine) - 포인터 머신 - 파이썬 모델 - 문서 간 거리 (Document distance): 고찰과 알고리즘 알고리즘이란 무엇인가? - 컴퓨터 프로그램의 수학적 추상화 - 문제를 해결하기 위한 computational procedure *model of computation은 다음을 명세한다 : 알고리즘이 수행 가능한 연산들, 각 연산의 비용(시간, 공간 등) 알고리즘의 비용 = 모든 연산의 비용의 합 랜덤 액세스 머신 (Random Access Macine) - 랜덤 액세스 머신은 큰 배열로 표현될 수 있다. - 시간복잡도 Θ(1)의 레지스터들 (각 1워드) - Θ(1) 시간동안, > l..

역시나 마이클 센델의 베스트 셀러였던 와 마찬가지로 읽으면서 무엇이 옳은 지, 고민에 고민을 거듭하게 만드는 책이다. 도덕적 가치를 더욱 더 돈으로 쉽게 눌러버릴 수 있는 요즘. 하지만 생각해보면 범위만 늘어났을 뿐이지 돈으로 특권을 누리는 것은 인간의 역사와 늘 함께한 것 같기도 하다. 새치기 할 권리, 대리모 문제, 탄소 배출권, 명문대 입학권 등 저자는 돈이 많은 사람들만 더욱 더 기회가 많아지고 윤택한 삶을 누릴 것이라고 주장한다. 하지만 왠지 샌델이 인간부류를 부자와 가난한 자로 너무 극명하게 나누는 점이, 덜 부자인 사람들을 기회도 못 잡고 늘 패배하는 삶을 사는 불쌍한 사람들로 묘하게 보는 것이 읽는 이로 하여금 오히려 불편함을 느끼게 했달까. 나는 그랬다. 인센티브 측면도 공감이 안 가는 ..

배우는 것 : Efficient procedures for solving problems on large inputs Scalability Classic data structures and elementary algorithms Real implementations in Python Peak Finder (극댓값 찾기) 1차원 배열의 경우: 만약 어떤 위치에서 해당 수가 오른쪽 값보다 크거나 같고, 왼쪽 값보다도 크거나 같으면, 극대라고 할 수 있다. 단도직입적인 접근: 왼쪽에서 시작해서 순차적으로 오른쪽으로 이동, 해당 값을 왼쪽 오른쪽 값과 비교하며 극대값을 찾는다. 분할 정복 알고리즘: 만약 가운데에서 시작한다면? 중간 원소를 선택, 왼쪽 원소, 오른쪽 원소와 중간 원소를 비교한다. 오른쪽이 크다면..