이 포스팅은 가볍게 이해하는 컴퓨터 시리즈 7 편 중 6 번째 글 입니다.
목차
컴퓨터에서 사용하는 자료구조와 알고리즘을 알아보자.
최호성님의 유튜브 강의를 보며 기본적인 컴퓨터 구조를 이해하고 정리하자.
자료를 정리해야 하는 이유
정리를 잘 해둬야 필요할 때 빨리 꺼내 쓸 수 있다!
처음엔 몰랐지만.. 갈 수록 유지 보수를 위해 정리하는 것이 중요함을 느낀다.. ㅠㅠ
어떻게 정리할까?
정리 는 상황에 맞는 적절한 규칙이 존재한다.
일련번호도 아무런 규칙이 없어보이지만, 그 숫자들에 규칙이 존재한다.
자료구조
선형 구조
배열
물리적으로 순차적인 자료구조
장점
- 단순하다.
- 한 자료에서 다음 자료 넘어갈 때 생각할 것이 없다. 인덱스가 단순 증가한다.
단점
- 크기를 늘리거나 줄이려면 구조를 변경해야 한다.
- 중간에 새로운 자료를 넣거나 빼는 경우 문제가 발생한다.
Linked List
화살표룰 가지고 원하는 요소를 가리키는 구조
장점
- 순서를 바꾸기 매우 쉽다.
- 중간에 새로운 자료를 넣거나 뺴기가 쉽다.
단점
- 한 자료 접근 후 다음으로 넘어가기 위해서 위치정보를 활용해 찾아가야한다.
- 찾아간다는 점에서 배열에 비해 복잡하다.
Stack
뚜껑식 김치 냉장고 : 출입구가 하나다!
사용처
- 되돌아 가기 위한 구조
한 스텝 전진하고, 전으로 가기 위해서는 pop 한다. - 가장 최근 값을 가져온다
- 대칭 구조
Queue
줄을 선다!
버스에서 줄을 서는 것이나 은행의 대기열을 생각하면 된다. 이 때 버스는 순차적으로 처리가 진행이 되고, 은행은 병렬적으로 처리된다. 각각을 순차 처리, 병렬 처리라 한다.
비선형 구조
Binary Tree
선형 구조, 정렬이 안된 상황에서 특정 값을 찾는다고 생각해보자. 이런 경우 해당 배열의 크기만큼 탐색을 진행해야 한다. 결과적으로 선형 구조에서 값을 찾는 것은 상대적으로 효과적이지 않다.
그래서 새로운 구조가 필요했는데 그 중 가장 효과적으로 사용한 구조가 이진 트리이다. 이진 트리에 대한 내용 정리
선형 구조, 비선형 구조 비교
| 비선형 | 선형 | |
|---|---|---|
| 구조 | 복잡 | 간단 |
| 접근효율 | 좋다 | 나쁘다 |
물론 데이터 개수에 따라 판단을 달라질 수 있다. 상황 판단을 잘해야 한다.
알고리즘
Sort
선형 구조에서 정렬하는 방법에 대해 생각해본다. 이 부분은 나열만 해두겠다. 정렬에 대한 기초적 내용 정리
선형 구조에서의 정렬 알고리즘
- Bubble
- Quick
- Merge
- Selection
- Insertion
- Heap
- Radix