3. 배열

728x90

Array (배열)

언어를 배우다보면 무조건 등장하는 개념이 나왔다. 완전 처음 언어를 공부하다가 어려움을 느끼게 되는 구간이라 볼 수 있다. 마치 초급 던전 보스처럼

배열은 cs에서 가장 기초적인 자료 구조 중 하나다. 이것은 단순한 데이터 원소들의 리스트이기도 하다. 배열의 첫번째 인덱스는 0번째임을 다들 알 것이다. 간단한 예시로 MT를 가는데 필요한 술을 사려 마트에 들렀다고 가정해보자.

array = ["진로", "카스", "테라", "위스키"]

배열에 들어있는 네 가지 문자열은 마트에서 살법한 주류들이다. 배열의 인덱스는 특정 데이터가 배열의 어디에 있는지 알려주는 숫자이다. 0번째부터 시작하니
0 , 1, 2, 3 으로 진행됨을 알 수 있다 그리고 각 요소(진로, 카스 등등)들은 0, 1 ... 인덱스에 대응 된다.

배열이 어떤식으로 구성되는지 알았다면 성능은 어떨까? 이런 자료 구조의 성능을 알기 위해선 코드가 어떻게 자료구조와 상호작용하는지 알아야한다. 여기서 자료구조는 대부분 네 가지 기본 방법을 사용하며 이것을 우리는 연산이라고 한다.

연산의 구조 ✏️

읽기 - 읽기는 자료 구조 내 특정 위치를 찾아보는 것이다. 이것이 검색이 아니냐고 할 수있는데 검색은 값을 찾는 것이라 둘의 성질이 다르다. 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻한다. 배열 인덱스2에 들어있는 물건 (테라)를 찾는 것이 배열 읽기의 예시라 볼 수 있다.

검색: 검색은 자료 구조 내에서 특정 값을 찾는 것이다. 배열에서는 특정 값이 배열에 있는지 없지는 만약에 있다면 어떤 인덱스에 있는지 알아보는 것을 뜻한다. 만약 "위스키"가 있는지 그리고 어느 인덱스(위치)에 있는지 알아내는 것이 검색이다.

삽입: 삽입은 자료 구조에 새로운 값을 추가하는 것이다. 이것이 배열이라면 배열내에 새로운 슬롯(칸)을 만들어 새 값을 추가하는 것을 말한다. 술을 모두 샀지만 갑자기 칵테일이 마시고 싶어 "진"을 추가하는게 배열에 새 값을 삽입하는 것이다.

삭제: 삭제는 자료 구조에서 값을 제거하는 것이다. 배열에서는 배열의 값 중 하나를 제거하는 것을 말한다. 위 배열에서 "진로"를 삭제하는 것이 배열삭제다.

연산에서 빠르기는 시간의 빠르기라고 생각하기 쉬운데 사실 시간적으로 생각해야하는 것이 아니라 단계적으로 생각해야한다.

연산의 빠르기는 시간인가 단계인가?

결론부터 말하자면 단계이다. 왜 일까?

그 이유는 그 누구도 특정 연산이 정확하게 2초가 걸린다고 단정할 수 없기 때문이다. 같은 연산이라도 10년전 노트북과 현재 최신형 노트북에서는 다를 수도 있고 더 훨씬 오래된 구형 하드웨어라면 또 다른 결과가 나올 수도 있기 때문이다. 이에 시간은 연산을 실행하는 하드웨어에 따라 항상 달라지니 신뢰할 수 없다.

연산의 속도를 측정할 때 얼마나 많은 단계(Step)가 필요한가를 따져봐야한다.

만약 A연산에선 5단계
B연산에선 100단계가 걸린다고 가정하면 모든 하드웨어에서 A연산이 B연산보다 빠를 것이라고 가정할 수 있다. 그러니 시간보단 단계를 측정하는 것이 연산의 속도를 분석하는 중요한 핵심이다.

연산의 속도 측정은 연산의 시간 복잡도 측정으로도 알려져 있다. 앞으로

속도
시간 복잡도
효율성
성능

이 네 가지 용어들은 각자 다른것이 아닌 같은 의미로 사용할 것을 미리 고지한다.

읽기 📖

앞서 말한대로 읽기는 배열 내 특정 인덱스에 어떤 값이 들어있는지 살펴보는 것이라 했다. 배열에서 읽기는 딱 한 단계다. 컴퓨터는 배열내 특정 인덱스에 한 번에 접근해서 볼 수 있다.

array = ["진로", "카스", "테라", "위스키"]

여기에서 인덱스 2를 찾아본다면 컴퓨터는 인덱스 2로 가서 "테라"라는 값이 있다고 알려줄 것이다. 그렇다면 어떻게 한번에 찾을 수 있을까? 먼저 컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이라고 볼 수 있는데 모두 차있는 것이 아니라 어느 곳은 비어있고 어느 곳은 차있다(데이터가 들어있다).

💻 메모리

프로그램에서 배열을 선언하면 컴퓨터는 프로그램이 쓸 수 있는 연속된 빈 공간이 모여있는 곳을 선택하는데 위에 표시한 곳에 할당한다. 그러니까 위에 배열이 5가지 요소로 되어있다면 5개의 빈 공간 그룹을 찾아서 배열로 지정한다. 끝이 아니다

컴퓨터 메모리 내에 각 공간은 특정 주소들이 있다. 그리고 그 주소는 각 앞 공간의 주소에서 1씩 증가한다.

위 그림과 대응시켜서 설명하자면

1010번 주소 부터 1013번째 까지 배열 요소들이 하나하나 대응되어 있다고 생각하면 된다.
컴퓨터가 배열의 특정 인덱스에 있는 값을 읽을 때 한 번의 단계로 바로 갈 수 있는 데는 아래와 같은 이유들이 복합적으로 작용해서 그렇다.

컴퓨터는 모든 메모리 주소에 한번에 갈 수 있다.
각 배열에 저장된 내용은 메모리의 시작 주소다. 따라서 컴퓨터는 손쉽게 시작 주소를 알 수 있다.
배열의 인덱스는 0부터 시작한다.

값을 읽으라고 명령해보자.

배열의 인덱스는 0부터 시작하며 인덱스 0의 메모리 주소는 1010이다.
인덱스 3("위스키")는 인덱스 0부터 정확히 세 슬롯 뒤에 있다.
따라서 인덱스3을 찾으려면 1010+3인 1013메모리 주소로 간다.

1013 메모리 주소로 접근한 컴퓨터는 "위스키"라는 값을 반환한다. 이러니 한 단계만에 접근이 가능했던 것이다. 그리고 한 단계로 끝나는 연산은 가장 빠른 연산 유형이다. 배열이 강력한 이유는 어떤 인덱스 값이든 빠르게 찾아 낼 수 있기 때문이다.

검색 🔎

인덱스 3에 있는 값을 꺼내지 말고 차라리 "위스키"가 있는지 아닌지 물어보자. 배열의 검색은 값이 있다면 그 값이 어디에 있는지 까지 알려준다.

컴퓨터는 배열에서 값을 찾을때 인덱스 0부터 시작해서 값을 확인한 후 그 값이 아니라면 다음 주소로 넘어간다. 그리고 이 것을 찾기까지 계속 반복한다.

인덱스 0 ("진로") <- 찾는 값("위스키")아님. 다음 인덱스로 이동
인덱스 1("카스") <- 찾는 값("위스키")아님. 다음 인덱스로 이동
인덱스 2("테라") <- 찾는 값("위스키")아님. 다음 인덱스로 이동
인덱스 3("위스키") <- 찾았음. 종료.

드디어 위스키를 찾아냈다. 이제 발견했으니 다음 공간으로 이동할 필요가 없어졌다. 값을 발견하기 까지 총 4개의 셀을 확인했으므로 총 4단계가 걸렸다고 볼 수 있다.

인덱스 3("위스키")를 검색해서 찾아내기 까지 총 4 단계 연산이 걸렸다.

이렇게 하나하나 확인 하는 연산을 선형 검색이라고 한다. "위스키" 처럼 찾고 있는 값이 맨 마지막에 있다면 컴퓨터는 셀 하나하나를 모두 뒤져서 찾아야한다. 그리고 만약 없는 값을 검색한다면 모든 셀을 하나하나 검색을 끝내야 비로소 연산이 끝난다. 검색에 해당하는 최대 한도는 없는걸까??

한도는 명확하다. 만약 위 처럼 배열의 셀이 4개라면 최대 한도는 4가 된다. 500개의 셀이있었다면 최대 한도는 500이 된다.

N개의 셀로 이뤄진 배열에서 선형 검색에 최대 한도는 N개이다.

검색이 읽기와 다른점은 시간이 오래 걸릴 수 있다는 점이다. 읽기는 배열이 얼마나 크든 바로 값을 불러올 수 있지만 검색은 1부터 셀의 끝까지 찾아봐야 한다는 점에서 다르다.

삽입 🎯

배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.

내가 술을 또 사고 싶어서 쇼핑 리스트를 추가한다고 해보자. 그리고 쇼핑 목록 맨 끝에 "진"을 추가하였다. 이 삽입에는 몇단계가 필요할까?

정답은 한 단계만 필요하다.
앞서 설명했듯이 컴퓨터는 배열이 시작되는 메모리 주소를 알고있다.
컴퓨터는 배열이 얼마나 원소를 포함하는 지도 알고 있으므로 새 원소를 추가해야하는 메모리 주소가 어딘지 계산할 수 있고 이는 한 단계면 가능하다.

맨 끝에 배열을 추가한다면 다음과 같이 새로운 1014의 주소를 가진 셀에 "진"이라는 값을 넣어 붙이면 끝난다. 이는 한 단계로 이뤄진다. 하지만 만약 배열 중간에 값을 넣는다면?

만약 "진"이라는 것을 인덱스 1에 집어 넣는다고 가정해보자. 그렇다면 그림은 다음과 같이 변한다.

무슨 차이인지 알 수 있겠는가? 먼저 이렇게 되기 위해선 총 네 단계에 연산이 필요하다.

먼저 위와 같이 되려면 삽입하려는 장소를 기준으로 오른쪽 셀들을 모두 한칸씩 옆으로 옮겨야 한다.
1. "카스"를 오른쪽으로 옮긴다.
1. "테라"를 오른쪽으로 옮긴다.
1. "위스키"를 오른쪽으로 옮긴다.
1. "진"을 인덱스1에 삽입한다.

이렇게 총 4 단계가 걸린다.

위 예시 배열처럼 짧아서 다행이지 만약 엄청나게 길었을 경우에 최악은 배열의 인덱스0번째 바로 옆에 요소를 추가하는 것이다. 그만큼 옮겨야 하는 요소들이 많아 지기 때문이다.

다시말해 원소 N개를 포함하는 배열에서 최악의 시나리오일때 삽입에는 N+1단계가 걸린다.

삭제 ❌

삭제는 삽입과 비슷한데 순서가 반대다.
배열의 삭제는 특정 인덱스의 값을 제거하는 과정이다. 만약 삽입하기 전의 배열로 돌아가고 싶어서 인덱스 1번째에 있는 "진"을 삭제했다고 가정해보자.

삭제를 한 후 저렇게 빈 곳은 가만히 놔둘까? 당연히 그렇지 않다. 삽입은 오른쪽으로 원소들을 밀어냈다면 삭제는 빈곳을 메꾸기 위해 왼쪽으로 당겨온다.

1. 진을 삭제한다.
1. 카스를 왼쪽으로 당겨온다.
1. 테라를 왼쪽으로 당겨온다.
1. 위스키를 왼쪽으로 당겨온다.

다시 처음으로 돌아왔다!

첫 번째 단계는 삭제이고 나머지 3 단계는 모두 데이터를 옮긴 연산들이다. 그래서 총 네 단계가 걸렸다. 삽입과 비슷하게 삭제의 최악의 시나리오는 첫 번째 원소를 제거하는 것이다. 그렇다면 배열에서 허용하지 않는 인덱스 0이 비게 되고 그것을 매꾸기 위해 모든 원소들을 한번씩 왼쪽으로 움직여야 한다.

자료 구조의 시간 복잡도를 분석하는 법을 알았으니 이제 사로 다른 자료 구조가 어떻게 효율성을 내는지 볼 차례가 왔다. 사용자가 만든 프로그램에서 올바른 자료 구조의 선택이 코드의 성능에 중대한 영향을 끼치기 때문에 아주아주 중요하다.

다음은 Set(집합)을 살짝 알아볼 것이다. 집합은 배열과 비슷하면서 다르기 때문에 알아 두면 좋을 것이다.