[CS] 배열과 리스트, 선택 정렬

dygreen·2022년 4월 6일
0

CS 지식

목록 보기
2/2
post-thumbnail

📌 배열과 리스트

: 여러 개의 원소를 저장해야 한다면 배열리스트라는 두 가지 방법 중 하나를 사용해야 합니다!

1. 배열(array)

[ 단점 ] : 원소를 추가하기에 좋지 않음

  • 배열에 새 원소를 추가하는 일은 쉽지 않음
  • 만약 공간이 모자라서 매번 모든 원소를 메모리의 새로운 위치로 옮긴다면 배열에 원소를 추가하는 작업은 아주 느려짐
  • 이를 개선하기 위해 메모리를 미리 가지고 있는데, 이는 만약 추가할 일이 생기지 않으면 메모리를 쓸데없이 낭비함과 동시에 다른 사람도 사용할 수 없음

    연결 리스트를 사용하면 원소를 추가할 때 생기는 문제 해결 가능

[ 장점 ] : 모든 원소의 주소를 다 알고 있음 (임의접근=읽기에 좋음)

  • 배열은 배열 안의 어떤 원소든 바로 찾을 수 있기 때문에 임의의 원소의 값을 읽는데 최고임
  • 임의의 원소에 접근하는 것이 가능하기 때문에 배열을 쓰는 경우가 더 많음(읽기 속도가 빠름)

2. 연결 리스트(linked list)

[ 장점 ] : 원소를 추가하기에 좋음 (삽입&삭제에 좋음)

  • 연결 리스트를 사용하면 원소를 메모리의 어느 곳에나 둘 수 있음
  • 메모리의 아무 곳에나 원소를 넣고, 그 주소를 바로 앞의 원소에 저장해 놓으면 됨(원소 추가가 아주 쉬움)
  • 연결 리스트를 사용하면 원소를 옮길 일이 없음
  • 원소를 중앙에 삽입해야 될 때 좋음-이전 원소가 무엇을 가리키는지 바꾸기만 하면 됨
  • 원소를 삭제할 때도 좋음-이전 원소가 가리키는 위치만 바꾸면 됨

[ 단점 ] : 특정한 원소만 알고 싶다면 연결 리스트는 최악임

  • 원소가 이웃하고 있지 않음(마지막 원소의 위치를 알고 싶다면, 1~마지막까지 하나하나 원소의 주소로 가야 함)
  • 모든 원소의 값을 한 번에 읽어야 한다면 연결 리스트가 좋지만, 특정 원소만 알고 싶다면 좋지 않음
  • 연결 리스트는 순차 접근밖에 할 수 없음(임의 접근 불가)

    배열을 사용하면 훨씬 쉽게 원소의 위치를 파악할 수 있음


📌 선택 정렬(selection sort)

: 배열을 작은 정수에서 큰 정수 순서로 정렬하는 알고리즘
선택 정렬은 깔끔한 알고리즘이지만 빠르지는 않음

(* 퀵 정렬은 O(n log n) 시간밖에 걸리지 않는 더 빠른 알고리즘임)


📚 Reference

: [book] Hello Coding 알고리즘

profile
✨감명깊은 앞단을 향한 꾸준한 여정✨

0개의 댓글