자료구조란 뭘까? (+추상자료형) (1)

자료구조에 대해 알아보겠습니다.

 

프로그램이라는 것은 data + 명령 또는 자료구조 + 알고리즘 이라고 볼 수 잇는데

여기서 좋은 프로그램이란 "시간 효율성" 과 " 공간 효율성" 이 뛰어난 것을 말한다.

 

 

또한 알고리즘이 잘 짜여져 있다는 것도 좋은 프로그램이라 말할 수 있겠죠?

(알고리즘이란 문제 해결 과정을 뜻합니다.)

 

알고리즘의 조건에는 5가지정도가 있는데..

1.입력: 0개 이상의 입력

2.출력: 1개 이상의 출력

3.명백성: 명령어의 의미가 명확

4.유한성:  일정한 단계 후에는 종료

5.유효성: 명령어들이 실행 가능해야 한다.

 

 

시간 효율성이란 말 그대로 같은 시간동안 얼마나 더 할 수 있느냐?

공간 효율성이란 말 그대로 같은 공간 (메모리) 안에서 얼마나 더 할 수 있느냐?

를 말한다. 

 

 

일반적으로는 pc에서 메모리 부족한 경우는 없다고 볼 수 있다.

왜냐하면 부족하면 메모리 늘리면 되잖아.. 

아무튼 그렇다면  시간 효율을 좋게 해야 되는구나를 생각한다.

 

시간복잡도는 연산의 수로 따진다.. ㅇㅋ??

쉽게 말하면 어떠한 일을 하는데 1번에 하느냐 100번에 하느냐 이런차이

 

 

?? 시간 효율성은 어떻게 올리느냐??? 바로 자료 구조 설계로 해결한다.

계산 N^2번 하기 싫으면 자료구조 잘 배워놔야함

 

 

 

 

 

 

 

그렇다면 자료구조에는 무슨 종류가 있을까???

 

 

어차피 다 설명은 할 수 없음... 넘많자너..ㅠ

 

 

 

 

Stacks은 아래의 그림과 같은 형태로 입구와 출구가 같습니다.

결국 마지막으로 들어간 것이 처음으로 꺼낼 수 있습니다.

LIFO( Last - in First - out) 이라고 합니다.

push/pop의 통로가 하나라는 것이죠.

 

 

얘는 Calculation 이나 

Backtracking에 이용된다고 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

다음으론 Queues 입니다.

입구따로 출구 따로있는 형태입니다.

그렇다면 얘는 처음 들어간 것이 처음 나오겠죠.

FIFO라고 합니다. (First In First Out)

얘는 들어가는 것을 Inqueue

나가는 것을 Dequeue라고 합니다.

push/pop과 다른 용어죠? 

물론 통상적으로 Add, Delete를 써도 무방합니다.

 

얘는 service/job scheduling 에 사용된다고 하네요.

 

 

 

 

 

 

 

 

 

 

그 다음으로는 Trees 입니다

 

얘는 일반적으로 binary trees로 많이 쓰여서

가지가 2개가 최대입니다.

 

나무를 생각해보면 Root 부터 Leaf 까지 인데

거꾸로 되있겠죠? 맨위가 root 맨 아래가 leaf

 

 

 

 

 

 

 

 

 

 

 

다음으로는 Graphs가 있습니다.

 

얘는 일반적으로 Node와 Link 를 가지고 있는데요.

Node를 vertex  그리고  Link 를 Edge 라고 부르는 것이 더 정확하다고 하는데 둘다 됩니다.

path finding 이나 social network mining에 쓰인다고 합니다.

 

 

 

 

 

 

 

그리고 다음은 Sorting 입니다.

 

자세한 것은 모르겠고 Quick sorting 을 제일 많이 쓴다고 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

다음으로는 Hashing 입니다

얘는 keys 라는 값을 hash fuction에 넣으면

hash라는 주소? 같은 곳으로 저장됩니다. 

 

예를 들어 2번에는 john smith의 정보나 관련된 사항만

들어가게 hash function을 할 수도 있겠죠?

 

그러나 얘가 아직 1:1 대응인지는 의문사항으로 남아있습니다.

안 배웠어요 ㅋㅋㅋ

 

 

 

 

대충 자료구조에 대한 것들은 마치고

 

추상자료형에 대해서 간단히 알아보자면

ADT라고도 불리며 java에서 class랑 비슷한 개념입니다.

추상 자료형의 데이터에 접근하거나 연산을 시도하려면 ADT에 포함된 연산 같은 것들을 이용해야하죠.

즉 직접 접근이 안된다는 겁니다.

 

 

더욱 더 자료를 찾고 싶다면 

https://visualgo.net/ko

VisuAlgo - 영상을 통한 자료구조와 알고리즘의 시각화 (한국어판) (Korean)

 

모든 내용은 자료구조를 배운 내 머리에서 나옴... 틀릴,,,수 ....있....다....