이전에 배운 collection의 ADT(e.g., stack, queue)는 삽입 순서에 기반해 객체를 삭제했다. 이번 글에서는, 객체 값에 기반해 객체를 삭제하는 collection의 ADT(=PQ)를 살펴볼 것이다. PQ에는 2가지 방식이 존재한다. 1). 가장 높은 값을 가진 객체를 삭제하는 방식과 2). 가장 낮은 값을 가진 객체를 삭제하는 방식이 존재한다. PQ를 통해 다음과 같은 과정을 쉽고 빠르게 수행할 수 있다. 수집한 객체들 중 가장 큰 객체 5개를 찾는다. 기존 객체들에 10개의 새로운 객체를 추가한 후, 가장 큰 객체 3개를 찾는다. Priority Queue Priority Queue는 객체의 집합을 가지고 있는 동시에, 추가/제거 연산을 지원하는 ADT다. 이때, 제거 연산은 가..

수 많은 applications은, 객체들의 집합(=collection of objects)를 사용한다. 뿐만 아니라 집합의 기본 연산들(e.g., 새로운 객체 추가, 기존 객체 제거)도 사용한다. 이번 글에서는, 이러한 요구사항에 맞게 설계된 기본적인 data types(e.g., stack, queue)에 대해 살펴볼 것이다. stack과 queue의 차이점은 객체 제거 방식이다. stack은 가장 최근에 추가된 객체를 제거하고, queue는 가장 늦게 추가된 객체를 제거한다. 더보기 Modular programming 모듈화 프로그램(modular programming)의 개념은 인터페이스(interface)와 구현(implementation)을 완전히 분리시키는 것이다. implementation..

이번 글에서는 알고리즘 분석(=실행 시간 및 메모리 사용량 예측)에 대해 살펴볼 것이다. 알고리즘 분석을 하는 대표적인 이유는 "알고리즘 성능을 예측하여, 클라이언트에게 확신을 주기 위함"이다. "Scienific method"을 사용해 알고리즘을 분석할 것이다. Scienitic method Observe: 프로그램 실행 시간(=event)의 특징(=feature)을 관찰한다. (computer = natural world) Hypothesize: 실행 시간(=data)과 일치하는(or 비슷한) 가설을 설계(=modeling)한다. Predict: 가설을 사용해, (입력값이 다른) 프로그램 실행 시간(=another event)을 예측한다. Verify: 더 많은 events을 예측해본다. Valida..

이번 글에서는 (dynamic connectivity 알고리즘으로 유명한) Union-Find에 대해 살펴볼 것이다. 더보기 Dynamic Connectivity Dynamic connectivity 문제는 동적 객체(= 관계가 변할 수 있는 객체)들이 주어졌을 때, "두 객체 연결성 판별 문제"다. Union-Find는 객체 간의 연결성 정보를 가지고 있는 동시에, 2가지 연산을 지원하는 ADT다. union: 두 객체 간의 연결성 부여 find: 두 객체 간의 연결성 질의 "연결성 소멸" 연산까지 있으면 보다 좋은 ADT가 될 수 있다. 더보기 What is API? API(Application Programming Interface)는 생성자들과 함수들의 signature와 설명이 있다. What ..