언제나 휴일

안녕하세요. 언제나 휴일, 언휴예요. 이번에는 알고리즘에 관한 이야기를 해 볼게요. 알고리즘은 9세기 페르시아 수학자 알콰리즈미(al khowarazmi)에서 시작하였다고 하네요. 알콰리즈미는 숫자를 상호 관계적인 개념으로 해석하면서 대수학의 아버지로 불리는 인물입니다. 그리고 본격적인 알고리즘은 유클리드(Euclid)의 호제법에서 출발했다고 합니다. 유클리드의 호제법은 다음과 같은 이론이예요. 자연수 a와 b가 있고 a ≥ b이고 a%b = r일 때 r이 자연수이면 GCD(a,b) = GCD(b,r) 이고 r이 0이면 GCD(a,b) = b 이다. ( GCD, Greatest Common Divisor) 예를 들어 a가 36, b가 24일 때 36 % 24 = 12 GCD(36, 24) = GCD(24..

알고리즘 알고리즘 문제를 해결하기 위한 논리 데이터베이스에서 다루는 주요 알고리즘 정렬 알고리즘: 레코드를 특정 키 항목을 배치하는 알고리즘 검색 알고리즘: 기억 공간에 보관한 데이터 중에 원하는 레코드를 찾는 알고리즘 정렬 방식 내부 정렬: 주기억장치에서 정렬하는 방식 버블 정렬, 선택 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬, 힙 정렬, 2-Way 병합 정렬, 기수 정렬 외부 정렬: 보조기억장치에서 정렬하는 방식 균형 정렬, 폭포 정렬, 다상 정렬, 오실레이팅 정렬 정렬 알고리즘 선택 시 고려 사항 데이터의 양, 초기 데이터의 배열 상태, 키 값들의 분포 상태, 소요 시간, 작업시간 검색 방식 선형 검색: 순차적으로 검색하는 방식 제어 검색: 비교할 대상을 선택하여 비교한 후 다음 비교할 대상을 선택하..

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:=..

1. 소개 앞으로 이 글에서는 컴퓨터 프로그래머의 기초 지식인 알고리즘과 자료구조를 이론적인 접근과 실질적인 구현을 다룰거예요. 자료구조는 프로그램에 관라할 데이터를 어떠한 구조로 보관하고 접근할 것인가를 다루는 것입니다. 선형 자료구조인 배열이나 연결리스트, 스택, 큐와 비선형 자료구조인, 트리, 그래프 등이 있습니다. 알고리즘은 문제를 해결하기 위한 논리의 집합이예요. 문제 해결 방법으로 분류하면 반복 알고리즘, 재귀 알고리즘, 분할 정복, 동적 프로그래밍, 탐욕 알고리즘 등이 있죠. 컴퓨터 프로그래밍을 업무로 하는 이들에게 알고리즘과 자료구조는 실질적인 구현에서 필수적으로 필요합니다. 그리고 이들을 다루는 책은 매우 다양하죠. 이론적으로 접근하는 책들은 다양한 알고리즘과 자료구조를 다루지만 실제적인..