언제나 휴일

3.1.1 이 책에서 공통으로 사용하는 것들 앞으로 이 책에서 사용할 클래스 ehglobal을 소개를 하겠습니다. ehglobal 클래스에는 이 책에 소개되는 전반적인 예제 프로그램에서 공통으로 사용할 만한 함수들을 정적 멤버 메서드로 캡슐화되어 있습니다. 이 책에 공통으로 사용 가능한 것들에 대한 정의에서는 형식 명과 메서드 명 모두 소문자만을 사용하고 있습니다. class ehglobal { public: 콘솔 화면을 지우는 메서드를 제공합시다. static void clrscr();//화면을 지우는 메서드 시간을 지연시키는 메서드도 제공합시다. static void timeflow(int millisecond); //원하는 시간동안 지연시키는 메서드 정수를 입력받는 메서드도 제공합시다. static..

3.1 배열과 vector 배열은 같은 종류의 자료를 연속적인 메모리에 보관하는 자료구조예요. C언어와 C++언어에서 제공하는 배열 형식은 개발 단계에서 원소 형식과 원소의 개수를 결정하는 정적인 구조를 갖고 있죠. 이러한 배열은 개발 도중에 원소의 개수를 변경할 수 없는 한계를 갖고 있어요. 하지만 C언어와 C++언어에서도 동적으로 메모리를 할당하는 함수와 연산을 제공하여 프로그램 동작 시에 연속적인 메모리를 할당하여 자료를 관리할 수 있어요. 특히 할당한 메모리에 보관한 자료의 개수를 기억해 두었다가 꽉 차면 메모리를 재할당하여 개발자가 배열의 크기를 신경쓰지 않게 구현할 수도 있어요. STL에서 제공하는 vector는 이러한 원리로 동작하게 만든 템플릿 클래스예요. 여기에서는 STL에서 제공하는 v..

3. 선형 자료구조 자료를 선형으로 보관하는 자료 구조에는 배열, 연결리스트, 스택, 큐, 덱 등이 있어요. 이와 같은 자료구조에 자료를 보관하거나 삭제, 검색 등의 연산을 수행할 때 반복적인 방법으로 해결할 때가 많아요. 배열은 자료를 연속적인 메모리에 보관하는 자료구조예요. 순차리스트라고도 부르죠. 연결리스트는 하나의 자료를 보관하는 노드들을 선형으로 그릴 수 있어요. 실제 메모리는 순차적이지 않지만 논리적으로 선형으로 나타낼 수 있어요. 연결리스트를 구성하는 노드는 하나의 데이터와 링크의 조합이예요. 링크는 노드의 위치 정보로 노드에 하나의 링크가 있으면 단순 혹은 단일 연결리스트라 부르고 두 개 있으면 이중 연결리스트라 불라요. 특히 배열은 프로그래밍 언어에서 제공하는 형식 배열만 있는 것이 아니..

2.4 삽입 정렬(Insertion Sort) 이번에는 반복적인 방법으로 해결하는 삽입 정렬(Insertion Sort) 알고리즘을 살펴볼게요. 삽입 정렬도 순차 정렬처럼 맨 앞에서부터 정렬 범위를 확장해 나가는 알고리즘이예요. 차이점은 확장할 범위의 끝에 있는 원소를 앞의 원소와 비교하며 자신보다 크면 위치를 바꾸고 그렇지 않으면 반복을 멈춘다는 것이죠. 순차 정렬에서 확장할 위치에 배치할 원소를 뒤쪽 원소와 비교하며 교환했지만 삽입 정렬에서는 확장할 위치에 있는 원소를 앞의 원소와 비교하며 교환하며 자신의 위치를 찾는다는 것이 다릅니다. 삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=1->n) 반복(j:=i->1) 조건(compare(base[j-1],..

2.3 선택 정렬(Selection Sort) 이번에는 반복적인 방법으로 해결하는 선택 정렬(Selection Sort) 알고리즘을 살펴볼게요. 선택 정렬도 순차 정렬처럼 맨 앞에서부터 제일 작은 원소를 배치하게 만들어 나가는 알고리즘이예요. 차이점은 맨 앞의 원소를 최소값이 있는 위치로 설정한 후에 뒤에 원소들과 비교하여 더 작은 값을 발견하면 최소값의 위치를 바꾸는 거예요. 순차 정렬에서 원소를 교환했던 것과 다릅니다. 선택 정렬은 내부 반복문을 수행한 후에 최소값과 맨 앞의 원소와 교환해요. 선택 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=0->n) min=i 반복(j:=i+1->n) 조건(compare(base[min], base[j]) > 0) mi..

2.2 거품 정렬(Bubble Sort) 이번에는 반복적인 방법으로 해결하는 거품 정렬(Bubble Sort) 알고리즘을 살펴볼게요. 거품 정렬은 앞에서부터 이웃하는 원소의 값을 비교하여 위치를 교환하는 것을 반복해요. 이를 끝까지 수행하면 제일 큰 값이 맨 뒤에 위치합니다. 그리고 정렬할 개수를 1 줄인 후에 다시 반복해요. 정렬할 개수가 1일 때까지 반복하면 정렬 작업이 끝나요. 거품 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=n->1) 반복(j:=1->i) 조건(compare(base[j-1], base[j]) > 0) 교환(base[j-1],base[j]) 예: 2 9 4 1 5 6 8 3 7 (정렬 전, n:9) 2 9 4 1 5 6 8 3 7 (i..

2.1 순차 정렬(Sequential Sort) 이번에는 반복적인 방법으로 해결하는 순차 정렬(Sequential Sort) 알고리즘을 살펴볼게요. 정렬 알고리즘은 배열의 자료를 원하는 순으로 배치하는 알고리즘을 말해요. 정렬 알고리즘은 입력 인자로 정렬할 자료들이 있는 배열의 시작 주소와 원소 개수, 비교 알고리즘이 필요합니다. 그리고 수행 후에는 배열 내의 자료들은 원하는 순서로 배치한 상태여야 합니다. 순차 정렬은 맨 앞에서부터 제일 작은 원소를 배치하게 만들어 나가는 알고리즘이예요. 이를 위해 배치할 자리에 있는 원소를 뒤쪽에 있는 원소들과 비교하면서 작은 것을 발견하면 배치할 위치의 원소와 교환해요. 순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=..

2. 반복 알고리즘 문제를 해결하는 다양한 방법 중에서 반복적인 방법으로 문제를 해결하는 것은 매우 흔합니다. 이번 장에서는 반복적인 방법으로 문제를 해결하는 반복 알고리즘을 다룰게요. 특히 반복 알고리즘으로 어떠한 문제를 해결할 수 있다는 것을 증명하기 위해서는 어떠한 특징을 고려해야 하는지 살펴볼 거예요. 반복 알고리즘으로 어떠한 문제를 해결할 수 있는지 증명할 때는 루프 변성과 루프 불변성을 이용합니다. 루프 변성은 반복문을 수행하면서 변하는 성질이며 루프 불변성은 변하지 않는 성질이예요. 예를 들어 정수 start에서 end 사이의 합계를 구하는 문제가 있다고 가정할게요. 이 문제는 다음과 같은 방법으로 해결할 수 있어요. 특정 범위의 합계 구하기(start:시작 값, end: 끝 값) sum:=..

1.3 점근식 표기 같은 문제를 해결하는 알고리즘은 여러 개가 있을 수 있죠. 전산에서 알고리즘을 평가하는 방법은 여러가지가 있어요. 그 중에서 수행 속도를 평가하거나 메모리 효율을 평가하는 점근식 방법을 많이 사용하죠. 점근적 표기에서는 n개의 자료가 있을 때 알고리즘 수행 시간(혹은 메모리 사용)이 n과 어떠한 상관관계가 있는지 표현하는 방법입니다. 예를 들어 어떠한 알고리즘이 n개의 자료가 있을 때 수행 시간 T(n)= 3n+27이라고 가정할게요. 만약 n이 충분히 큰 수라면 가장 높은 차수의 항이 결과에 가장 큰 영향을 주겠죠. 점근식 표기에서는 가장 높은 차수의 항을 제외한 나머지 차수의 항은 버리고 계산해요. 그리고 상수도 생략하여 평가합니다. 따라서 T(n)=3n+27과 같은 수행 시간을 가..

1.2 알고리즘 소개 알고리즘은 특정 문제를 해결하기 위한 논리를 말해요. 해결해야 할 어떠한 문제가 주어지면 문제에 주어지는 선행 조건과 영향 인자와 후행 조건을 알아겠죠. 선행 조건은 알고리즘을 수행 하기 전의 상태를 말합니다. 그리고 영향 인자는 문제를 해결하는데 영향을 주는 인자예요. 후행 조건은 문제를 해결하고 난 후의 상태를 말해요. 결국 알고리즘은 선행 조건인 상태에서 주어진 영향 인자를 가지고 후행 조건에 맞게 문제를 해결하는 것이죠. 예를 들어 특정 범위 내의 정수의 합계를 구하는 문제를 살펴봅시다. 이 때는 선행 조건은 특별한 것이 없네요. 문제를 해결하는 데 영향을 주는 인자는 범위의 시작과 끝이겠죠. 따라서 알고리즘을 함수로 구현한다면 입력 인자로 범위의 시작 정수와 끝 정수가 필요..