Hello Coding 그림으로 개념을 이해하는 알고리즘 Study Note 02
Chapter 2 선택 정렬 배열(array)과 연결 리스트(linked list) - 자료구조(Data structure)의 기본 - 메모리에 데이터가 어떻게 저장되는 지 미리 알아야 한다 - 데이터 저장을 위해서는 메모리의 주소를 할당 받고 나서 데이터가 저장됨 - 데이터 접근에는 임의 접근과 순차 접근이라는 두 가지 방식이 있다 (Random access, Sequential access) 배열 - 미리 원소의 갯수 만큼(초기화 단계에서) 메모리 주소를 할당 받고 원소를 각각의 주소에 저장하는 방식 - 인덱스(index)로 원소의 위치를 표시, 0부터 시작 - 읽기 O(1) 고정시간, 삽입 O(n) 선형시간, 삭제 O(n) 선형시간 - 임의 접근이 많은 경우 유리함 - 간단하고 빠른 데이터 접근이 가능하지만, 유연성이 부족하고 데이터 삽입/삭제에 비효율 적일 수 있음 - 배열의 모든 원소는 같은 자료형이여야 함 장점 - 미리 원소의 갯수를 알고 있을 때 유리 - 임의 접근에 유리하여(인덱스를 통한 빠른 접근) 특정 원소에 접근할 때 유리 (읽기) - 고정된 크기만큼 연속된 메모리 공간을 할당하여 사용되기 때문에 캐시 친화적이다 - 구현이 간단하며 대부분의 프로그래밍 언어에서 지원함 단점 - 원소를 추가하거나 삭제할 때 미리 할당 된 주소를 전부 옮겨야 하는 경우가 발생할 수 있음 - 따라서 처음 설정한 크기에서 원소를 추가/삭제하는 경우 불리함 (삽입, 삭제) - 실제 사용하는 데이터보다 더 큰 크기를 할당할 경우 메모리가 낭비 될 수 있음 활용 - 정렬된 데이터 저장 : 정렬된 데이터를 빠르게 검색해야 할 때 유리 - 행렬 연산 : 행렬을 표현하고 연산하는 데 사용 - 캐시 : CPU캐시는 배열과 유사한 구조로 작동하여 데이터에 빠르게 접근 - 단순한 데이터 목록 : 정적이거나 크기가 미리 예측 가능한 데이터 목록을 저장하는데 적합 연결 리스트 - 각 원소에서 그 다음 원소의 메모리 주소를 포인터로 연결되어 있는 방식 - 연속적인 메모리 공간...