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캐시는 배열과 유사한 구조로 작동하여 데이터에 빠르게 접근
- 단순한 데이터 목록 : 정적이거나 크기가 미리 예측 가능한 데이터 목록을 저장하는데 적합
연결 리스트
- 각 원소에서 그 다음 원소의 메모리 주소를 포인터로 연결되어 있는 방식
- 연속적인 메모리 공간을 차지 않아 유연하게 데이터를 관리 할 수 있음(동적)
- 읽기 O(n) 선형시간, 삽입 O(1) 고정시간, 삭제 O(1) 고정시간
- 삽입, 삭제가 자주 일어나는 경우 유리함
- 단순 연결 리스트, 이중 연결 리스트 가 존재
장점
- 동적 할당을 하기 때문에 (포인터의 값만 바꾸면 됨) 원소의 삽입/삭제에 유리함 (삽입/삭제)
- 메모리 재할당없이 유연하게 크기 조절 가능
단점
- 순차 접근만 가능하여 특정 원소에 접근하려면 불리함 (읽기)
- 다음 노드를 가르키는 포인터를 저장해야해서 추가 메모리 필요
- 배열에 비해 구현이 복잡하고(포인터를 사용한 노드간 연결 유지), 다양한 경우의 수를 고려해야 함
활용
- 스택, 큐 구현 : 연결 리스트를 통해 스택, 큐를 쉽게 구현 할 수 있음
- 동적 메모리 관리 : 운영체제의 메모리 관리 시스템에서 연결 리스트를 사용하여 메모리 블록을 관리
- 그래프 표현 : 그래프의 인접 리스트 표현에 사용
선택 정렬 (Selection sort)
- 정렬을 위하여 가장 크거나 작은 값(정렬 기준에 따라)을 맨 앞으로 보내는 작업을 반복하여 전체를 정렬하는 알고리즘
- 가장 작은 값 순서라고 할때, 가장 작은 값을 찾아 첫번째 위치로 보내고, 첫번째 위치를 제외한 나머지의 리스트에서 가장 작은 값을 찾아 두번째 위치로 보내는 식으로 리스트의 끝까지 반복
- 시간 복잡도 O(n²)
- 안정 정렬이 아님 => 같은 값을 가지는 요소들의 상대적인 순서가 보장 되지 않는다
- 구현이 비교적 쉽고 메모리를 적게 사용하나 시간 복잡도가 높고 안정 정렬이 아니다
02_selection_sort.py 작성 + 테스트
Chapter 2 정리
컴퓨터의 메모리는 거대한 서랍장과 같다 (메모리 주소, 데이터)
여러 개의 항목을 저장하고 싶을 때 배열 또는 리스트를 사용한다
각 자료구조의 특징을 알고 용도에 맞는 자료구조를 사용해야 한다 (배열은 읽기, 연결 리스트는 삽입/삭제에 유리)
댓글
댓글 쓰기