전체 글

[Ch.02 - 알고리즘 설계와 분석의 기초] 점근적 표기

알고리즘의 수행 시간은 항상 입력의 크기가 충분히 클 때 분석한다. 즉, 점근적 분석을 한다. 이는 고등학교 수학의 무한의 개념을 이용한 분석이 점근적 분석의 한 예다. 변수의 크기가 충분히 큰 경우 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 것을 함수의 점근적 증가율이라 하고 그 표기법을 점근적 표기법이라 한다. 무한의 개념을 사용하면 \(\lim\limits_{x \to \infty}\cfrac{2n^2+3n}{n}=2n+3\)이다. 이것은 "함수 \(f(n)=\lim\limits_{n \to \infty}\cfrac{2n^2+3n}{n}\)는 \(2n+3\)의 비율로 증가한다"는 뜻이다. 점근적 표기법은 이 보다 더 간명하다. 점근적 표기법은 계수가 중요하지 않다. 그 이유는 다음과 같다...

[Ch.02 - 알고리즘 설계와 분석의 기초] 몇 가지 기초 사항들

1. 알고리즘 분석의 필요성 어떤 알고리즘을 설계하고 나면 이 알고리즘이 자원을 얼마나 소모하는지 분석해야 할 때가 많다. 여기서 자원이란 다양한 것이 되겠지만, 대부분 소요 시간이 가장 중요한 관심 대상이 된다. 시간 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적이다. 시간 분석을 하면 알고리즘이 어느 정도 입력에서 어느 정도의 시간이 필요한지 미리 짐작할 수 있다. 알고리즘의 소요 시간은 설계하는 방법에 따라 소모 시간이 다양해진다. 예로 입력의 크기가 \(n\) 일 때, 최악의 경우 \(n^2\)에 비례하거나 \(n\log n\)에 비례하는 시간을 소모할 수 있다. 2. 알고리즘의 수행 시간 알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다. 입력의 크기..

[Ch.01 - 운영체제의 개요] 운영체제 소개

1. 일상생활 속의 운영체제 '운영체제'라는 말은 모두가 쉽게 접할 수 있는 말이다. 'OSOperating System'라고도 일컫는 운영체제는 컴퓨터를 켜면 가장 먼저 만나게 되는 소프트웨어로, 대표적인 운영체제는 개인용 컴퓨터의 운영체제인 Windows와 Mac OS, 스마트폰 운영체제인 Android와 iOS, 대형 컴퓨터에서 사용하는 Unix와 Linux가 있다. 컴퓨터와 스마트폰뿐만 아니라 MP3, 내비게이션, 스마트 TV 등에도 운영체제가 있다. 이처럼 성능이 낮은 CPU와 낮은 메모리를 사용하는 시스템에 내장하도록 만든 운영체제를 Embedded operating system 또는 Embedded system이라고 한다. 성능이 낮은 하드웨어에 탑재되는 운영체제이기 때문에 일반적인 운영체제..

[Ch.01 - 자료구조 소개] 자료구조와 알고리즘

1. 자료구조와 알고리즘의 관계 알고리즘은 문제를 해결하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 자료구조는 알고리즘과 밀접한 관계가 있다. 자료구조는 그 자체로도 알고리즘을 포함한다. 2. 알고리즘 표기법 알고리즘을 만들 때는 받은 입력으로부터 원하는 출력을 만들어내기까지의 과정을 모든 이가 알아볼 수 있도록 애매하지 않고 명쾌하게 기술되어야 한다. 알고리즘은 다양한 방법으로 표현될 수 있다. 1. 자연어를 이용한 서술적 표현 알고리즘을 작성하는 사람의 자연어로 표현하는 방법이다. 이 방법은 알고리즘을 쓰는 사람에 다라 일관성이나 명확성을 유지하기 어렵다. 따라서, 누구나 쉽게 이해해야 하는 알고리즘을 표현하는 데는 한계가 있다. 2. 순서도를 이용한 도식화 알고리즘을 순서도..