자료구조란

본 글은 윤성우님의 "열혈자료구조" 책을 토대로 작성한 글입니다. 

언어 베이스는 C언어입니다.

교재가 학습하는데 정말 많은 도움이 되었습니다.

제가 정리해서 쓴 글이라 본 서적에서 생략되어 있는 부분이 있지만 직접 구매하셔서 심도있는 공부 추천드립니다 (다른 책들도 가능합니다 !)

 

참고 : https://andrew0409.tistory.com/148

 

자료구조는 데이터를 표현하고 저장하는 방법에 대해서 설명합니다.

 

" 프로그램이란 데이터를 표현하고 그렇게 표현된 데이터를 처리하는 것이다. "

 

위에서 말하는 데이터 표현은 데이터 저장을 포함하는 개념입니다.

그리고 이렇게 데이터의 저장을 담당하는 것이 바로 자료구조입니다. 

" 목적은 명확합니다. 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있습니다. "

출처: https://andrew0409.tistory.com/148
[코인하는 프로그래머]

 

 

" 정수를 저장하기 위해서 int형 변수를 선언한다 " 
" 개인정보를 저장하기 위한 목적으로 구조체를 정의한다. "

 

넓은 의미에서 int형 변수도 구조체의 정의도 자료구조에 속합니다. (배열또한)

 

하지만 앞으로 제가 공부할 자료구조는 저렇게 단순하지 않고 복잡한 형태의 자료구조를 배울 계획입니다. (두근두근)

 

아래는 기본적인 자료구조의 분류 입니다. 

 

https://jungmonster.tistory.com/m/80?category=1053746

 

보시다시피 파일도 데이터를 저장하는 도구이기 때문에 자료구조에 포함됩니다. 

저는 우선적으로 윤성우님의 열혈자료구조 책을 베이스로 선형구조와 비선형구조를 포스팅 하겠습니다.

 

선형구조
 - 자료를 표현 및 저장하는 방식이 선형(linear)이다. 
 - 데이터를 나란히 혹은 일렬로 저장한다.

비선형구조
 - 선형구조의 반대 나란히 저장하지 않는다.

* 실무에서는 자료구조를 직접 구현하지 않고 검증된 라이브러리를 쓴다고 합니다. 그리고 이것이 합리적인 선택입니다. (저도 동감하는 바입니다.)

 왜냐하면 검증 라이브러리를 쓰는것이 안전과 성능면에서 우월하기 때문이죠(코테를 공부할때 느꼈던 부분)

자료구조의 선택 기준
- 자료의 처리 시간
- 자료의 크기
- 자료의 활용 빈도
- 자료의 갱신 정도
- 프로그램의 용이성

출처: 
https://andrew0409.tistory.com/148
 [코인하는 프로그래머]

 

 

" 어떤 정보를 리스트와 트리구조로 저장할 수 있다고 생각하자 그렇다면 나는 어느것을 선택할 것인가 ..? "

해당 명제를 해결하기 위해선 각각의 자료구조의 특성을 잘 이해하고 있어야 합니다. 그래야 필요에 맞게 쓸 수 있기 때문입니다.

그리고 선택을 하는데 있어서 자료구조의 구현 능력은 그리 중요하지 않을 수도 있습니다.

하지만 책에 나온내용과 같이 " 자료구조의 구현 경험은 프로그래밍 능력을 향상시켜 줄 것이다 " 2000% 동의하는 바입니다.

 

그렇기 때문에 저도 공부하는 것이죠

 

 

자료구조와 알고리즘

사실 저도 자료구조와 알고리즘의 개념 자체를 헷갈려 했습니다. 찾아보면 금방 나오는것을 알려고도 하지 않았죠(반성중...) 그렇지만 이제부터 다시 바로잡으려 합니다.

자료구조
 - 데이터의 표현 및 저장법

알고리즘
 - 표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법

 

해당 코드는 자료구조적 측면입니다.

int arr[10] = {1,2,3,4,5,6,7,8,9,10}; // 자료구조적 측면

 

해당 코드는 알고리즘적 측면입니다. 

// 알고리즘적 측면
// 배열에 저장된 모든 값의 합을 구하는 알고리즘
for(int i=0;i<10;i++){
	sum += arr[i];
   }

 

이와 같이 자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있습니다. (자료구조와 알고리즘은 밀접한 관계를 갖는다.)

 

과연 자료구조가 배열이 아니었어도 반복문과 인덱스 값을 이용한 순차적 접근이 가능할까...? 이것은 배열이 아니면 달라져야 합니다. 더 합리적이고 타당한 방법으로 !!

 

 

쌓여있는 상자중에 머그컵이 들어있는 상자를 찾아보자. 
쌓여있는 상자 : (자료구조)
머그컵을 찾는 문제 해결 : (알고리즘)

 

??? : 머그컵이 있을거 같은 상자를 꺼내 찾아보면 되지 않나 ㅋㅋㅋ (윤성우님 각색해봤습니다...ㅎㅎ) 
(이러신분은 없을겁니다.)

핵심은
 * 자료구조에 따라 알고리즘은 달라진다 => 저장방식에 따라 문제해결법은 달라진다
 * 알고리즘은 자료구조에 의존적이다
 * 우리는 문제 해결을 위해 타당한 방법을 생각해야한다 ...

이것입니다.

 

 

알고리즘 성능 분석 방법

- 이제 본 내용을 들어가기 전 마지막 단계입니다.

- 수학이 없어도 알고리즘 학습은 가능합니다. 하지만 있으면 더많은 의미를 부여하여 학습할 수 있습니다. 

 

윤성우님의 열혈자료구조에서는 지수식 로그식만 알고 있어도 이해할 수 있게 풀이하셨습니다.

(긴장 !! 저는 수포자입니다.)

 

지수식, 로그식에 대한 기본 정의 : https://m.blog.naver.com/freewheel3/220853009691 
* 모르시는 분들은 저기에서 한번 쑥 훑고 오세요.

 

해당 그림은 좌표평면상으로 지수식, 로그식을 표현한 그래프 입니다.

출처 : 윤성우의 열혈 자료구조

 

시간 복잡도와 공간 복잡도

 

아래를 한번 보시죠

" 잘동작하는것은 물론 좋은 성능까지 보장 받길 원함 "
" 자료구조와 알고리즘을 평가할 수 있어야함. "
" 모든 경우에서 항상 우월하고 만능키와 같은 자료구조와 알고리즘은 존재하지 않음 "

 

- 어떤 알고리즘이 어떤 상황에서 더 빠르고 또 느린가

- 어떤 알고리즘이 어떤 상황에서 메모리를 적게쓰고 또 많이 쓰나?

 

이렇듯 하나는 속도 하나는 메모리 사용량으로 성능을 평가합니다.
(속도 : 알고리즘의 수행시간 분석결과) > 시간 복잡도
(메모리 사용량 : 메모리 사용량 분석결과) > 공간 복잡도

 

메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘이라고 할 수 있습니다.

그런데 일반적으로는 메모리보단 실행속도를 우선시 하죠
* 특정 알고리즘에 대해서는 메모리도 고려되지만 이미 검증이 끝난 알고리즘의 적용 고려는 속도에 초점을 둡니다.

 

아.. 아니 그럼 속도는 어떻게 측정하죠 ...?

 

이것은 직접 저희가 시계를 들고 초 분으로 시간을 재고 기록해야 합니다 (맞는 소리입니다. 쳐맞는,, 각색입니다) 

 

 

- 처리해야 할 데이터 양의 변화에 따른 속도의 증가 및 감소의 정도도 알아야 합니다.
- 알고리즘 수행속도 평가
 * "연산 횟수 세기", "처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n) 구성"

말 그대로 연산횟수를 통해 알고리즘 빠르기를 판단합니다 => 횟수가 적어야 빠르다 !

 

즉, 알고리즘 별 연산횟수를 함수 T(n)의 형태로 구성하면 그래프를 통해 데이터 수의 변화에 따른 연산 횟수의 변화정도를 한눈에 파악 가능합니다. 

 

아래 그림을 그려봤습니다.

출처 : 윤성우의 열혈 자료구조

 

위 그래프에 따른 시나리오 입니다. (책 내용을 인용했습니다.)

해당 그래프로 추측할 수 있습니다.

A : 데이터 수가 적으면 알고리즘 B가 더 빠르네?
B : 아 그럼 데이터 수가 늘어나면 알고리즘 A가 더 빠르겠다.

C : 데이터의 수가 적은 경우에는 알고리즘 B를 적용하고 많으면 A를 적용해야 합니다.

- 나름 합리적인 판단입니다. 중요한 것은 데이터수가 많아짐에 따른 연산횟수 증가 속도입니다.


A : 오 그럼 알고리즘 A가 좋네요? 
- 그것은 사실입니다.

B : 그럼 알고리즘 B는 없앨까요?
- 큰일나는 소리입니다. A와 같이 안정적인 것은 B에 비해 구현난이도가 높습니다.
따라서, 데이터 수가 많지 않고 성능에 덜 민감한 경우라면 구현의 편의를 이유로 B를 선택하기도 합니다.

A, B : 엥 그럼 알고리즘 분야는 정답이 없나요 ? (부들부들 ....)
- 그것이 아니고 상황에 맞게 답을 내려야 합니다.

A, B : (삐익)

 

위에서 알 수 있듯 결론적으로

알고리즘 구현 능력에만 관심을 두는 것이 아닌, 종합적으로 사고하고 판단하는 능력이 중요하다

 

 

 

 

여기까지 책 안에서의 인트로였습니다. 

구구절절 이론 내용만 적었는데요 복습겸 적는거라 노트에 정리된 내용을 옮겼습니다. 

 

저는 첫 자료구조 서적을 윤성우의 열혈 자료구조로 시작해서 블로그 포스팅도 그렇게 되었는데요 다른 블로그 분들의 자료구조 내용들도 참고하면서 공부했습니다. 정말 많은 도움이 됩니다. 

 

참 그리고 광고받거나 이런거 절대 아닙니다 .....