자료구조 학습) 2. 자료구조를 배우기 위한 전반 지식

안녕하세요, Readder입니다.

 

이전에는 자료구조란 어떤 것이고, 왜 자료구조라는 것이 필요하고, 왜 우리가 알아야 하는지에 대해 간단하게 정리해 보았습니다.

 

이번에는 자료구조 기초. 즉, 자료구조를 이해하기 위해 반드시 알아야 할 사항들에 대해서 정리해 보고, 다음 챕터부터는 자료구조에 대해 실질적으로 학습을 진행해보고자 합니다.

 

자료 구조의 예시와 그 자료구조를 하나 하나 뜯어보기 전에, 제가 생각하기에는 다음과 같은 지식이 필요합니다.

1. 하나의 언어에 대한 전반적인 지식

2. 빅오 표기법과 복잡도

이에 대해 하나씩 설명해보도록 하겠습니다

 

1. 하나의 언어에 대한 전반적인 지식

첫 언어를 어떤 것으로 시작하셨든 상관 없습니다. C, C++, Java, Python 등 많은 프로그래밍 언어가 있고, 이 프로그래밍 언어들은 기본적으로 비슷한 뼈대를 갖고 있기 때문에 자료구조를 학습하는 데에는 문제가 없습니다. 다만, 저는 예제 코드를 작성할 때 Java 언어를 기반으로 작성할 예정이기 때문에 같은 언어를 사용한다면 더 좋을 것 같습니다.

자료구조를 배우기 전, 하나의 프로그래밍 언어는 처음부터 끝까지 배우고 오셨을 거라고 생각합니다. 만약, 그러지 않고 여기로 오셨다면 순서가 잘못되었기에 프로그래밍 언어 하나에 대해 제대로 학습하고 오신 뒤에 자료구조를 학습하는 것이 맞다고 생각합니다.

따라서 따로 하나 하나에 대해 다루지는 않을 것이지만, "내가 제대로 배우고 온 건가?" 하시는 분들을 위해 대략적으로 체크리스트를 몇 개 작성했으니, 해당 내용을 들었을 때 잘 모르겠다 싶으시면 복습을 추천드립니다.

 

-자료구조를 학습할 준비가 된 프로그래밍 언어 전반적인 지식

□ 자료형에 대한 이해와 사용

□ 제어문(조건문, 반복문)에 대한 이해와 활용

□ 필요한 함수를 정의할 수 있다

□ 기본적인 메모리 구조에 대한 개념

□ 기초 지식들을 사용하여 구구단 출력, 소수 찾기, 문자열 내림차순 정렬, 등의 문제를 스스로 해결할 수 있음

 

위 체크리스트들 중 크게 걸리는 부분이 없다면, 이제 자료구조를 위한 지식을 배울 때가 되었습니다.

 

2. 빅오 표기법과 복잡도

빅오 표기법은 간단하게 말해서 시간/공간 복잡도를 나타내기 위함입니다.

빅오 표기법과 복잡도를 배워야 하는 이유부터 설명드릴게요.

 

배열을 기준으로 설명드리겠습니다.

1부터 10까지의 값을 저장하는 배열을 하나 선언해 보겠습니다.

int[] arr = {5, 6, 1, 2, 7, 3, 4, 10, 9, 8};

당장은 눈대중으로 어떤 값이 몇 번째에 있는지 알 수 있지만, 실제 배열을 사용할 때는 값이 저장된 순서는 언제든 바뀔 수 있습니다.

다시 위 배열로 돌아와서, 여기서 8이란 숫자를 찾을 때는 다음과 같은 방법을 거쳐야 합니다

1. 가장 앞에서부터 값 하나를 확인한다.

2. 그 값이 8인지를 확인한다

3. 8을 찾거나 전체 배열을 다 확인할 때까지 반복한다.

 

그러면 다음과 같은 순서로 숫자 8을 찾게 됩니다

5 -> 6 -> 1 -> 2 -> 7 -> 3 -> 4 -> 10 -> 9 -> 8

 

총 10개의 값을 확인했죠? 

  

우리가 어떤 자료구조에서 특정한 값을 찾는 것을 탐색이라고 하고, 지금처럼 찾는 값이 가장 마지막의 있는 경우를 최악의 경우라고 하는데, 배열은 탐색 시 최악의 경우 배열에 저장된 값의 총 개수(N)만큼의 시간이 걸리는 자료구조입니다.

 

그런데 배열이 아닌, 어떤 자료구조는 늘 한 번에 값을 찾아가는 자료구조도 존재해요.

예를 들어, 배열을 다음과 같이 활용해 본다고 합시다.

String[] arr = {
	"zero",
	"one",
  	"two",
	"three",
	"four",
	"five",
	"six",
	"seven",
	"eight",
	"nine"
};

그러면, arr[0]는 "zero"를 나타내고, arr[1]은 "one"이라고 저장되어 있는 것처럼, 배열의 인덱스가 특정 숫자를 나타내는 규칙을 갖도록 한다고 가정한다면, 내가 seven이란 값을 찾기 위해서는 arr[7]을 조회해야 한다는 것을 알고, eight란 값을 찾기 위해서는 arr[8]을 조회해야 한다는 것을 알아요. 이렇게 언제나 자신이 찾는 값의 인덱스를 알면, 그 값을 바로 찾아갈 수 있으니까 해당 값을 찾는데에 걸리는 시간은 1밖에 소요되지 않아요. 하지만, 이런 경우는 흔치 않고 특정한 상황에서만 가능하겠죠.

 

이렇듯 특성과 용도에 따라 사용하기 적절한 알고리즘들이 나뉘어져 있어요.

그리고 이 자료구조들을 활용하기 위해 해당 시간이 얼마나 걸리는지를 알아야 하고, 그 시간을 나타내는 지표가 빅오 표기법이기 때문에, 자료구조를 배우기 위해서는 이 두 내용을 익히는 것이 반드시 필요합니다.

 

필요성만 해도 생각보다 얘기가 길어졌는데, 빅오 표기법과 시간 복잡도에 대한 내용 자체도 그렇게 어렵지는 않아요.

제가 이전에 포스팅한 내용이 있으니, 다음 글을 읽어 주시기를 바랍니다.

2021.11.09 - [Programming/Algorithm 학습] - 빅오(Big-O) 표기법과 시간 복잡도의 의미와 필요성

 

 

다음 포스팅에서는 실제 자료구조들을 하나씩 알아보는 내용을 다루도록 하겠습니다.

감사합니다.