메모리가 동작하는 방법

메모리게 무언가를 저장 할 때마다 컴퓨터에 공간을 요청한다. 그러면 컴퓨터는 저장할수 있는 주소를 알려준다. 만약 여러 개의 원소를 저장해야 한다면 배열과 리스트라는 두가지 방법중 하나를 사용해야한다.

배열과 연결 리스트

생활속에서 예시를 들어보면 3명의 친구와 영화티켓을 예매했는데 중간에 2명의 친구가 추가 되었지만 나란히 앉을수 없어 다시 예약을 했다. 또 얼마 지나 1명이 추가 되어 총6명이 앉을수 있는 좌석을 예매 했다. 이런식으로 매번 친구(원소)가 추가될때 마다 메모리의 새로운 위치로 옮긴다면 작업은 아주 느려질 것이다.

이러한 상황은 개선시킬수 있는 방법은 미리 넉넉하게 자리를 예약하는 거지만 어차피 정해놓은 갯수가 넘어버리면 다시 그러한 상황이 올수 있고 , 또 다 사용하지 않는다면 메모리를 낭비하는 단점이 있다.

이러한 문제를 해결할수 있는게 연결리스트 사용이다.

연결리스트 (linked list)

원소의 메모리의 어느 곳에나 둘수 있다.즉 메모리가 같이 있지 않더라도 메모리 주소들이 하나의 목록으로 연결되어있다. 단점으로는 한번에 원하는 원소의 값을 알수 없다.

배열

연결리스트에서 한번에 원하는 원소의 값을 알수 없는 단점을 보완할수 있는게 배열 이다. 배열은 모든 원소의 주소를 다 알고 있다.
(위치 번호는 0,1,2.... 순이다)

 [10,20,30,40]
// 0, 1, 2, 3 : index

원소의 위치를 index라고 한다. 그래서 "20은 위치 1"에 있다고 하지 않고 "20은 인덱스 1"에 있다.라고 말하는 것이 올바른 표현이다.

선택 정렬

저장된 음악중 가수별로 몇곡이 있는지 기록한 목록이 있다고 하자. 가장 많이 들은것 부터 가장 적게 들은 순서로 정렬하여 순위를 알고 싶을때 어떻게 할까?

방법으로는 리스트의 모든 항목을 살펴보고 가장 많이 연주된 가수를 찾아 새로운 리스트에 기록하는 것이다.이러한 행위를 끝날때 까지 반복하게 된다.

연주횟수 가장 많은 사람 찾아서 새로운 배열에 넣는것을 빅오표기법으로 표현할때 O(n)이 걸린다. 모든 횟수를 반복 하려면 , O(n)실행시간이 걸리는 연산을 n번해야 한다.

모두합해서 O(n * n) 즉 O(n²) 시간이 걸린다.

선택 정렬은 깔끔한 알고리즘이지만 빠르지 않다!!

요약

• 컴퓨터 메모리는 거대한 서랍장과 같다
• 여러개의 항목을 저장하고 싶을 때는 배열이나 리스트를 사용한다.
• 배열을 사용하면 모든 항목은 이웃하는 위치에 저장한다.
• 리스트를 쓰면 모든 항목이 흩어지지만, 각 항목은 다음 항목의 주소를 저장하고 있다.
• 배열은 읽기가 빠르다.
• 연결리스트는 삽입과 삭제가 빠르다
• 배열의 모든 원소는 같은 자료형(예를들면, 모든 정수형이거나 모두 실수형)이어야 한다.

---

참고

'Hello Coding 알고리즘' 책을 공부하여 요약정리한 내용입니다.