지난 글에는 벡터로 통해 통적 배열 (dynamic array)을 조정하는 방법을 알아봤다. 벡터에 어떤 기능들이 주어졌는지 살펴보고 응용하는 방법도 살펴보았다. 이번 계시물에서는 array 템플리 클라스로 인해 어떻게 고정 배열을 안정시키는 방법을 알아보겠다. array 오브젝트를 선언하는 법은 다음과 같다. #include using namespace std; ... array arr1 = { 1, 2, 3, 4 }; array arr2; array arr3 = { 'G', 'E', 'T' }; array arr4{{ 3, 4, 5, 1, 2 }}; 1. 벡터랑 유사한 array 컨테이너의 기능들 이 기능들은 말 그대로 벡터에서 사용 가능한 기능들과 유사하다. 벡터를 공부해봤으면 아래 기능들이 낯이 ..

해당 계시물은 내가 벡터에 대한 주제를 아래와 같이 이해 했으니 정확하지 않을 수도 있다. 자료구조 처음 접하자마자 바로 배열 (Array)로 복습 들어가봤을 것이다. 그 중에서 고정 배열 (static arrays)와 통적 배열(dynamic)에 대해서 접해 봤을 것이다. 씨언어의 경우 통적 배열의 크기를 조절하려면 수동으로 할당 (malloc, realloc, dealloc) 대해서 배웠을 것이다. 씨플플 언어에서는 씨언어와 비해 더 쉽게 수동으로 new 와 delete 키워드로 메모리 할당이 비교적으로 더 수월하다. 또한 씨플플은 씨언어와 다르게 vector 템플릿 클래스로 자동으로 배열 메모리 할당이 가능하다. 이번 글은 vector로 메모리 할당을 살펴보고 다음 글에서는 array템플릿 클래스로..

이진 탐색은 주어진 배열 A의 가운데 요소 (정수)를 탐색하는 키 요소랑 비교하고 배열 A를 왼쪽 오른쪽 하위배열들로 나눈다. 물론 가운데 요소가 키 요소보다 작으면 오른쪽 하위 배열에서 탐색을 시작하고 키 요소보다 크면 왼쪽 하위 배열에서 탐색을 시작한다. 이런 식으로 반복적으로 배열 A가 왼쪽/오른쪽 하위 배열들로 나뉘어진다 키 요소가 발견 되거나 배열 A가 더이상 나뉘어질 수 없을 때 까지. 여기서 전 글에 계시한 순차 탐색 (Linear Search)과 이진 탐색의 차이점을 들어난다. 순차 탐색은 배열 A가 정렬 되어있지 않은 상태로도 탐색이 가능하지만 이진 탐색의 조건은 배열 A가 이미 정렬되어야 있는 상태여야 한다. 안그러면 있는 요소를 제대로 못 찾을 수도 있다. 비주얼을 아래에 첨부하겠다...

기본 탐색 알고리즘 중 하나다. 말 그대로 배열 A의 모든 소요들을 차례대로 (왼쪽부터 오른쪽)으로 탐색을 한다. 정렬되지 않아도 된 배열도 탐색 가능하다. 추가 설명이 필요없어서 바로 비주얼을 아래에 첨부하겠다. 의사코드 마저 되게 간단하다. 특별한 메서드는 필요없고 네이브로 구현했다. Linear-Search(A, n, T) for i = 0 to n - 1 do if A[i] = T then return i i = i + 1 if i = n then return false 시간 복잡도는 그냥 간단한 O(n)이다 (nested for loop이 없어서). 공간 복잡도도 역시 O(1)이다. 아래 레포지토리에 순차 탐색 프로그램을 완성하였다. 다른 알고리즘들에 비해 매우 간다나고 짧지만 그래도 참고하기엔..

중학교 및 고등학교 수학 과정에서 한 번쯤 행렬을 접해봤을 것이다. 대학교 선형대수학 과정에서 행렬의 무효공간 (null space)을 배우게 되지만 적어도 중학교/고등학교 수학 과정에서 행렬을 접했을때 주로 기본적인 행렬 덧셈 곱셈을 배웠을 것이다. 이번 글은 먼저 두 행렬을 더하는 알고리즘을 이용해 프로그램을 완성하였다. 네이브 메서드를 사용했고 의사코드는 다른 알고리즘들에 비해 매우 짧고 간단하다. Matrix-Add(A[][N],B[][N],C[][N]) for i = 0 to N for j = 0 to N // Add all the elements from Matrix A and Matrix B. C[i][j] = A[i][j] + B[i][j] 해당 알고리즘은 nested for loop을 이..

합병 정렬 (Merge Sort)와 같이, 퀵 정렬도 분할 정복 메서드를 이용하는 정렬 알고리즘이다. 다른 분할 정복 알고리즘과 같이 정렬되지 않은 한 배열을 둘로 나누다. 바로 배열을 나누기 위해 파티션 (partition)알고리즘을 추가로 구현했다. 합병 정렬과 다르게, 퀵 정렬은 가운데 지점 (midpoint)에서 배열을 나누지 않는다. 배열은 나눌때 한 배열은 지점 (pivot)보다 작은 정수들이 들어있고 나머지 한 배열은 지점보다 큰 정수들이 들어있다. 반복적으로 지점이 바뀌어지면서 배열은 반복적으로 나누어진다 각 배열에 1개의 정수가 남을 때 까지. 이제, 합병 정렬과 마찬가지로, 모든 배열들을 다시 한 배열로 합치면서 동시에 정렬 시킨다. 이해하기 쉽게 비주얼을 추가했다. 메서드: 분할 정복..

이번 글에서는 정렬 알고리즘들 중에 가장 기초적인 거품 정렬에 대해 살펴보겠다. 만약 알고리즘 스터디, 혹은 컴퓨터 공학 과정에서 자료구조 중에 정렬 알고리즘들을 배웠다면, 아마 거품 정렬을 제일 먼저 접해봤을 것이다. 간략하게 설명하자면, 배열 A에서 위치 x가 주어졌다. 그럼 A[x] > A[x + 1]을 비교하게 된다. 만약 진짜 A[x] > A[x + 1]이 맞으면, A[x]값과 A[x + 1] 값이 서로 교체 (swap)한다. 그리고 비교 지점이 한 칸씩 앞으로 이동한다. 만약 마지막 위치가 n이고 배열 A[n - 1]과 A[n] 비교가 마치면, 다시 첫번째 배열 위치 A[0]로 돌아가서 다시 A[1]을 비교하게 된다. 모든 배열들이 정렬했을 때 까지 이런식으로 반복된다. 만약 위에 있는 글이 ..

선택 정렬은 간략하게 설명하자면 끝에서 잡던, 앞에서 잡던, 한 지점을 잡고 시작하며 현재 찾은 제일 낮은 값을 맨 앞으로 옮긴다. 예를 들면 한 배열이 A가 다음 숫자들을 다음과 같이 정의했다: [5, 4, 7, 3]. A[0...3]에서 가장 적은 값이 3이며, 3이 맨 앞자리 A[0]에다 옮겨지며 기존에 있던 A[0]값 -> 5는 기존에 있던 3의 위치 -> A[3]에 옮겨진다. 이제 A[1...3]에서 가장 적은 값을 찾아야하는데 가장 적은 값은 A[1]에 위치한 4이다. 따라서 A[1]에 4가 유지되며 바꿔치기를 할 필요가 없다. 대충 A[3]까지 반복이 되면서 [3, 4, 5, 7]로 정렬된다. 이해가 안 갔으면 다음 비쥬얼을 참고하면 된다. 메서드: Naive 네이브 의사코드는 다음과 같다...

분할 정복 (Divide and Conquer) 메서드의 기초 알고리즘 중 하나다. Insertion Sort랑 같은 목표 (배열을 정렬하기)를 갖고 있지만 과정은 Insertion Sort보다 많다. 배열을 계속 반복적으로 둘로 분할한다 한 개씩 남을 때 까지. 정복하는 과정은 여기서 부터 시작된다. 먼저 방금전 까지 나누어진 배열 요소들 끼리 정렬한 다음에 반복적으로 Insertion Sort와 같은 방식으로 정렬 시켜서 왼쪽과 오른쪽 배열들을 만든다. 왼쪽 배열에 소속이 되있는 요소들과 오른쪽 배열에 소속이 되있는 요소들 끼리 비교하면서 정렬하고 합치면 정렬된 배열이 완전체가 된다. 위 설명을 못 알아들었으면 비주얼을 참고하자. 메서드: 분할 정복 (Divide and Conquer) 의사코드는 다..

이름과 다르게 추가 키 값을 삽입하지는 않는다. 그냥 입력한 배열에 있는 숫자들을 두 묶음으로 나뉘어 진다. 왼쪽 묶음은 정렬된, 오른쪽 묶음은 정렬 안 된. 정렬되지 않은 오른쪽 묶음에 있는 숫자들이 하나하나 왼쪽 묶음으로 옮겨지면서 각 정렬된 숫자들을 비교하며 적절한 자리를 잡는다. 물론 처음에 배열 전체가 정렬되지 않았을 초기 때는 둘 째 숫자 array[1] 가 첫 째 숫자 array[0]이랑 서로 비교를 시작하고 나서야 정렬된 왼쪽 묶음이 탄생한다. 말 그대로 array[n]이 array[n - 1]을 계속 비교한다. 내가 방금한 설명을 이해 못 했다면 비쥬얼로 설명하자. 메서드: 네이브 (Naive) 의사 코드는 다음과 같다. Insertion-Sort(A) for j = 1 to A.leng..