배열 삽입 검색 삭제
목차
배열, 링크드리스트, 해쉬테이블 등 자료구조를 다루는 기본은 삽입(Insertion), 검색(Search), 삭제(Deletion) 입니다.
어렵게 생각하면 끝이 없으니 쉬운 일상의 비유를 들어보겠습니다.
수업시간에 필기를 하는 노트가 있습니다. 공책에 무언가 적는 행위는 입력입니다. 필기한 내용을 찾기 위해서는 노트를 넘기면서 검색을 해야 합니다. 그 내용이 필요없어졌거나 잘못된 내용이라면 지울수도 있고 혹은 그 페이지만 떼버릴 수도 있습니다.
노트도 물론 배열처럼 순차적으로 저장되는 자료구조입니다. 노트의 아이디어를 그대로 가지고 배열 삽입 검색 삭제를 작성하면 됩니다.
배열 알고리즘 분석
아래의 코드는 배열의 원리를 설명하기 위한 코드입니다. 배열의 원리를 이해하도록 풀어헤친 코드이며 실제 자료구조의 역할을 하려면 좀 더 손을 봐야한다는 점에 주의합니다.
#include <iostream>
using std::cout;
using std::endl;
int main() {
int myArray[50]; // 배열 선언 사이즈 50개
int element = 0; // 아이템 개수
int search; // 검색할 숫자
// 배열에 삽입한다
myArray[0] = 142;
myArray[1] = 256;
myArray[2] = 311;
myArray[3] = 777;
myArray[4] = 999;
myArray[5] = 175;
myArray[6] = 595;
element = 7; // 7개 요소를 사용
// --------------------------------------
// 배열에 저장한 요소를 출력
for (int i = 0; i < element; i++)
{
cout << myArray[i] << ", ";
}
cout << endl;
// --------------------------------------
// 이 숫자를 검색한다
search = 311;
for (int i = 0; i < element; i++)
{
if (myArray[i] == search) {
cout << search << "를 찾았습니다. 인덱스 넘버:" << i << endl;
break;
}
}
// --------------------------------------
// 이 숫자를 삭제한다
search = 999;
int index = 0; // 삭제할 인덱스를 저장
cout << endl << search << "를 삭제하겠습니다." << endl;
for (int i = 0; i < element; i++)
{
if (myArray[i] == search) {
cout << "찾았습니다. 인덱스 넘버: " << i << endl;
index = i;
break;
}
}
// --------------------------------------
// 삭제로 인한 구멍을 메꿔준다
for (int k = index; k < element; k++)
{
myArray[k] = myArray[k + 1];
}
element--;
// --------------------------------------
// 배열에 저장한 요소를 출력
for (int i = 0; i < element; i++)
{
cout << myArray[i] << ", ";
}
cout << endl;
return 0;
}
142, 256, 311, 777, 999, 175, 595, 311를 찾았습니다. 인덱스 넘버:2 999를 삭제하겠습니다. 찾았습니다. 인덱스 넘버: 4 142, 256, 311, 777, 175, 595,
지난 학습에서 배열을 생성하고 배열에 값을 할당하는 부분을 배웠습니다. 배열은 인덱스를 사용해서 입력을 합니다. 인덱스를 일일히 지정해야 하는 부분이 귀찮긴 하지만 for루프와 랜덤함수를 사용하면 한꺼번에 큰 배열의 초기화도 가능합니다.
배열의 모든 요소에 인덱스로 접근한다는 점이 for 루프로 사용하기 쉬운 이유입니다. 검색은 0부터 배열의 실제 사이즈까지 모든 요소를 traverse 하여 비교하는 것으로 충분합니다.
여기서는 인덱스를 찾지 않았을 때의 처리는 생략했습니다. 우선 찾는 법을 터득하면 찾지 못했을 때의 처리도 어렵지 않습니다. 우선 for 문과 if 문을 어떻게 사용해서 찾았는지 확인합니다.
for문이 index 를 전진시키면 그 index 로 배열의 값을 가지고 와서 검색하려는 값과 비교를 합니다. for 문은 첫번째 요소인 인덱스 0 부터 끝까지 검색을 하겠죠? 찾았을 때 break 를 하는 경우는 찾는 값이 하나만 있을 때이고 끝까지 갈 때는 찾는 값이 여러개 있는 경우 입니다.
배열도 중복된 값을 허용하는가 허용하지 않는가에 따라 검색에 차이가 있습니다. 여기서는 중복된 요소가 없다고 가정하였습니다.
삭제의 경우 삭제하려는 요소를 우선 검색해야 합니다. 따라서 삭제 이전에 검색 기능이 있어야 합니다. 위 코드에서는 main 에다가 주욱 작성했지만 실제 프로그램을 작성하면 함수로 분리해줬을 테니까 삭제 함수에서 검색 함수를 부르는 방법으로 사용할 수 있습니다.
검색함수가 인덱스를 가져다 주면 삭제함수는 해당 배열의 요소를 그냥 0으로 초기화할 수도 있겠지만 그렇게 하면 구멍이 뚫립니다. 구멍을 메꿔주기 위해서는 myArray[인덱스] = myArray[인덱스+1] 할당으로 한칸씩 땡겨줍니다.
이것만 보면 매우 비효율적으로 보이죠? 하나의 데이터를 삭제하면 구멍을 메우기 위해 나머지를 모두 이동시켜야 합니다. 어쨋든 이것은 배열이란 자료구조의 특성입니다.
배열이라고 해도 목적에 따라 사용하는 방법이 다양하다는 점에 주의합니다.
배열 검색 삽입 삭제 클래스
C++은 객체지향 프로그래밍 언어이므로 OOP의 장점을 충분히 살리기 위해 클래스를 사용해서 배열 알고리즘을 구현해 보겠습니다.
다만 클래스에서 날 것의 배열 구조를 사용하는 것은 또 다른 번거로움이 있기 때문에 이런 경우 C++ 대표적 STL인 vector container 를 클래스와 함께 사용하면 편하게 구현할 수 있습니다.
vector 컨테이너는 쉽게말하면 데이터를 관리하게 편하게 만든 클래스입니다. 순수 배열과는 다르게 내장된 기능이 많고 그 이름과는 다르게 데이터를 직관적으로 이해할 수 있는 도구입니다.
어쨋든 C++에서는 매우 자주 보게되므로 알아두는게 좋습니다.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
class myArray
{
private:
// vector 를 선언한다
vector<double> vt;
public:
// 생성자
myArray(int maxSize) {
vt.resize(maxSize); // 최대 사이즈
}
void setArray(int index, double value)
{
vt[index] = value; // 인덱스에 값을 할당한다
}
double getArray(int index)
{
return vt[index];
}
};
int main() {
myArray arr1(70);
int length = 0;
int k;
// 입력한다 (insertion)
arr1.setArray(0, 13);
arr1.setArray(1, 25);
arr1.setArray(2, 79);
arr1.setArray(3, 54);
arr1.setArray(4, 82);
arr1.setArray(5, 99);
arr1.setArray(6, 29);
length = 7; // 배열의 길이를 기록
// ------- 출력하기 -------------
for (k = 0; k < length; k++)
{
cout << "idx: " << k << " : " << arr1.getArray(k) << endl;
}
cout << endl;
// ------- 검색하기 -------------
int search = 82; // 이 숫자를 검색한다.
for (k = 0; k < length; k++)
{
if (arr1.getArray(k) == search) {
cout << search << "를 찾았습니다. 인덱스 넘버: "
<< k << endl;
break;
}
}
if (k == length)
cout << search << "를 찾지못했습니다. 인덱스 초과: " << k << endl;
// 요소 삭제하기
double deleteIndex = 79; // 이 숫자를 삭제한다
cout << " ----------------------------- " << endl;
cout << "다음 숫자를 삭제합니다. " << deleteIndex << endl;
for (k = 0; k < length; k++)
{
if (arr1.getArray(k) == deleteIndex) {
cout << "찾았습니다. 인덱스: " << k << endl;
break;
}
}
for (int i = k; i < length; i++)
{
arr1.setArray(i, arr1.getArray(i + 1));
}
length--;
// ------------- 출력하기 ------------
for (int i = 0; i < length; i++)
{
cout << "idx: " << i << " : " << arr1.getArray(i) << endl;
}
return 0;
}
idx: 0 : 13 idx: 1 : 25 idx: 2 : 79 idx: 3 : 54 idx: 4 : 82 idx: 5 : 99 idx: 6 : 29 82를 찾았습니다. 인덱스 넘버: 4 ----------------------------- 다음 숫자를 삭제합니다. 79 찾았습니다. 인덱스: 2 idx: 0 : 13 idx: 1 : 25 idx: 2 : 54 idx: 3 : 82 idx: 4 : 99 idx: 5 : 29
C++의 클래스 문법에 대해서 따로 설명 하지는 않겠습니다. 클래스와 OOP 에 대하여는 C++에서 별도로 학습해야 하는 부분으로 참고하시면 되겠습니다.
클래스에서 가장 기본적인 생성자와 getter and setter 를 사용해서 배열 알고리즘을 구현하는 모습을 볼 수 있습니다.
클래스라서 데이터를 집어넣고 가져오는 방식이 기존 C++ 의 방식과는 차이가 있지만 큰 틀에서 보면 별 차이는 없습니다.
문법의 지엽적인 부분에 집중하기 보다는 큰틀을 바라보고 코드를 구성하도록 합니다. 첫번째 예제에서 충분한 설명을 한 부분을 클래스 사용환경으로 바꿔주기만 하면 됩니다.
- 자료구조를 구현하고 데이터를 삽입한다.
– 배열은 하나씩 순차적으로 삽입할 수 있다 - 검색은 어떻게 할 것이냐?
– 인덱스 0부터 끝의 요소까지 Traverse(주사) 한다 - 삭제의 요건과 처리 방법은?
– 삭제를 하기 전에 2번 검색으로 인덱스를 반환받아야 한다
– 삭제 후에 구멍(중간에 빈 부분)을 어떻게 매울 것인가
간단한 자료구조라도 예외사항까지 고려하면 보완해야 할 부분이 많습니다. 때문에 C++ 이나 자바와 같은 고수준 언어로 갈수록 개인이 만든 자료구조가 아니라 STL, Collection (자바의 경우 Collection Framework) 같이 언어 개발사의 자료형을 사용하게 되는데요.
STL을 사용하더라도 최소한의 이해가 뒷받침 되지 않으면 발전하기가 힘듭니다. 그냥 만들어진 클래스만 사용할 줄 알아서야 새로 나오는 프레임워크에 적응하다가 시간이 다 갈 겁니다. 물론 프레임워크도 실무에서 다룰 알아야 하는 중요한 도구지만 알다시피 프로그래밍 기술의 진화속도는 매우 빠릅니다.
지금도 추세를 보면 결국 프로그래머 중에서 코딩만 하는 코더(coder)는 대부분 사라지고 엔지니어 (Engineer)만 살아남을 확률이 큽니다.
프로그래밍 기술의 발전을 볼 때 흔히 프로그래밍의 결과물이 진화하는 것으로 생각하는 경향이 있는데요. 그만큼 중요한 것은 프로그래밍을 하기 위한 도구가 진화한다는 것 입니다. 제조업을 예를 들면 예전에 공장에서 노동자가 100명이 하는 작업을 자동화 시킨 공장에서 불과 4-5명의 운영자(Operator)가 관리하고 있습니다.
그건 굴뚝 산업의 예이고 인간의 정신 노동인 프로그래밍은 다를까요?
아닙니다. 정신 노동의 효율은 무한하기 때문에 자동화가 본격화 되었을 때 AI가 정말 모든 사람을 해고할 수도 있습니다. 그런 가능성을 보여주는 기술 중의 하나가 블록체인 기술입니다.
알고리즘 튜토리얼에서 블록체인 이야기까지 확대하긴 뭐하지만 우리가 알고리즘을 배우는 이유는 최대한 컴퓨터에 대체되지 않기 위해서 이기도 합니다. 알고리즘은 컴퓨터가 사고하는 방식을 만드는 일이라 알고리즘을 만들고 관리할 수 있는 프로그래머는 항상 필요합니다.
요약
C++의 배열 삽입 검색 삭제에 관하여 알아봤습니다.
자료구조는 다르지만 삽입, 검색, 삭제의 문제를 해결하는 것은 동일합니다.
스택, 큐, 링크드리스트 등 여러가지 자료구조를 구현하지만 기본은 삽입(Insertion), 검색(Search), 삭제(deletion) 이라는 것에 대해서는 확실한 아이디어를 갖도록 합니다.
프로그래밍은 매우 정직한 기술입니다. 매우 정직하다는 것은 장단점이 있습니다.
단점은 대부분 사람들에게 재미가 없다, 지루하다는 것이고
장점은 내가 다소 프로그래밍에 부족한 실력이더라도 성실하고 꾸준히 노력하는 경우 프로의 단계까지 도달 할 수 있다는 것입니다.
따라서 누가 이 알고리즘을 공부해야하는지 나왔습니다.
- 천재
- 노력파 거북이
천재가 공부한다는 것은 즐긴다는 것이라 대다수 범인(평범한 사람)에게는 해당하지 않습니다.
노력파 거북이는 처음엔 느리지만 결승선은 토끼보다 먼저 넘어 우승합니다.
소프트웨어가 발전하기 위해서는 많은 천재들을 필요합니다. 그리고…
IT사회가 발전하기 위해서는 많은 노력파 거북이들이 필요합니다.
묵묵히 노력하는 사람들은 멋집니다-
외부참고문서
How to Insert an element at a specific position in an Array in C++ – GeeksforGeeks
HOW TO INSERT A VALUE IN AN ARRAY – C++ Forum (cplusplus.com)
C++ Program to Insert an Element in an Array (codescracker.com)