자료구조(6) - 배열

 - 배열이란

               : 같은 자료형을 가진 원소가 순서를 가지고 만들어진 집합.

               : 배열 원소들은 인덱스에 의해 참고됨, 배열의 인덱스는 배열 원소의 순서를 의미

               : 배열을 선언하면, 배열에 대한 기억 공간이 메모리에 할당됨.

                           : 할당되는크기는 자료형에 대한 메모리 할당 크기별 배열 요소의 개수 만큼이다.

 - 배열의 이점

               : 많은 요소들을 각각의 변수명을 만들지 않아도됨

               : 많은 요소를 탐색해올때 메모리와 검색효율이 모두 향상됨

               : 프로그램 작성시 인덱스 값만을 액세스 함으로써, 원소값을 참조하는데에 효율적인 표현가능

 

 - 리스트란

               : 리스트란 자료를 나열한 목록

               : 순서 리스트란 자료들 간에 순서를 갖는 리스트

               : 집합으로 표현하는 방법

                           : A = {a1, a2, a3, ...., an} 과 같이 집합으로 표현하는 방법.

                           : 각 원소간의 순서의 개념이 없음.

 

(( 책에는 리스트는 순서를 갖는다 되어있는데, 집합으로 표현하는 방법에는 순서의 개념이 없어 순서 리스트라 표현한다 함.. 순서 리스트는 상식적으로 순서가 있기에 이름에 순서가 들어갔을거라 유추됨 ))

(( 검색시에도 순서리스트란 순서가 있는 것으로 조회됨. 참고바람 ))

 

               : 배열로 표현하는 방법

                           : 원소들이 논리적 순서와 같은 순서로 기억공간에 저장됨

                           : 순서 리스트 중간에 원소가 삽입되면 이후의 모든 원소들이 한 자리씩 자리 이동.

                           : 줄지어 있는 사람들처럼 사람이 중간에 혹은 앞 뒤에 들어오고 나가는 것에 따라,

                             다른 사람들의 이동이 발생할 수 있음.

                             즉, O(n)의 복잡도를 가지므로 원소갯수와 무관한 O(1) 의 복잡도는 갖는 배열로 표현하는 방법이

                             효율이 더 좋다.

 

 - 다차원 배열

               : 내 시각으로는 다차원 배열은 기본적인 구조를 언어를 배울때 배우므로, 자료구조에서는

                 저장방법에 대해서만 공부해보도록 하겠다.

               : 행 우선 방법

                           : arr[3][3]의 배열이 있다고 가정해보자, 행을 우선해 배열이 저장되므로

                             arr[0][0] arr[0][1] arr[0][2] 가 먼저 저장되고

                             arr[1][0] arr[1][1] arr[1][2] 가 이후 저장되는 방식이다.

               : 열 우선 방법

                           : arr[0][0]

                            arr[1][0]

                            arr[2[0] 가 먼저 저장되고

                                        arr[0][1]

                                        arr[1][1]

                                        arr[2][1]

                                                    가 다음 저장되는 방식이다.