[1장] 자료 구조가 중요한 까닭

코딩 초짜면 코드가 올바르게 돌아가는게 목표여야 한다. 하지만 좀만 경험이 쌓이면 코드 품질 측면을 생각하기 시작한다. 그럼 코드 품질의 척도엔 무엇들이 있을까?

• 코드 유지 보수성 : 가독성, 조직, 코드 모듈성 등등
• 코드 효율성 : 무엇이 더 빠르게 실행되는 코드인가
  
  

1. 자료구조

자료 구조란 데이터를 조직하는 방법을 말한다. 그리고 이 데이터 조직 방법에 따라 코드의 실행 속도가 드라마틱하게 바뀌게 된다.

1.1 배열 : 기초 자료 구조
알다시피 배열은 단순한 데이터 원소들의 리스트를 말한다. 배열에만 쓰이는 기술 용어에는 아래와 같은 것들이 있다.

• 배열의 크기 : 데이터 원소가 몇개나 들어있는지
• 배열의 인덱스 : 특정 데이터가 배열의 어디에 있는지 알려주는 숫자
• 예시
  

  배열	"A"	"B"	"C"	"D"	"E"
  인덱스	0	1	2	3	4

 

1.2 자료구조와 연산
자료 구조의 성능을 알고싶다면 코드가 자료 구조와 어떻게 상호작용하는지 분석해야한다. 대부분의 자료 구조는 네 가지 기본 방법을 사용하는데, 이를 연산이라고 부른다.

• 읽기 : 자료 구조 내 특정 위치를 찾는 일 ex) 배열[1] = ???
• 검색 : 자료 구조 내에서 특정 값을 찾는 일
• 삽입 : 자료 구조에 새로운 값을 추가하는 일
• 삭제 : 자료 구조에 값을 제거하는 일
  
  

이때 각 연산을 수행하는데 '얼마나 많은 스탭을 필요로하는지'는 곧 코드 효율성와 직결된다. 만약 연산 수행에 소요되는 스탭이 적다면 이를 두고 흔히들 '속도가 빠르다'라고 말한다.

 

1.3 자료구조와 속도

위에서 연산 수행에 소요되는 스탭이 적다면 속도가 빠르다고 표현했는데, 왜 굳이 연산의 '시간'이 아니라 '단계'로 측정할까? 이는 각 컴퓨터 사양과 작업 환경에 따라 동일한 연산이라도 측정 시간은 얼마든지 달라질 수 있기 때문이다.

 

따라서 연산의 속도측정 = 연산의 시간 복잡도 측정 = 시간 복잡도 = 효율성 = 성능 다 같은말이라고 취급할 수 있다.

 

 

2. 메모리와 컴퓨터

메모리는 쉽게 말해 셀로 구성된 매우 큰 컬렉션이다. 그리고 컴퓨터는 이 셀들에 값을 저장하고 꺼내 쓰는 방식으로 동작한다(문자열, 숫자, 배열 기타 등등)

2.1 메모리 특징

컴퓨터가 메모리를 사용할 때 아래와 같은 특징들을 갖는다.

 

1) 컴퓨터는 모든 메모리 주소에 한 번에 접근이 가능하다

  Q. 메모리 주소 1012 찾아주셈
  A. 1단계 소요

2) 값 할당시 메모리 주소의 시작지점을 기록해둔다
  Q. 배열의 인덱스 2에 있는 값 찾아주셈
  A. 1012부터 +2해서 됐다 1014에 3이란 값이 저장돼있네. 퉤.

 

 

3. 연산

앞서 언급했듯 주요 연산은 읽기, 검색, 삽입, 삭제 네 가지로 나뉘며, 각 연산이 어떻게 수행되는지 살펴보자.

 

3.1 읽기

가장 빠른 연산으로, 딱 1스탭만 필요하다. 예를 들어 constarr = [1, 2, 3, 4]라는 에서 arr[2] 값이 필요하다면 컴퓨터는 다음과 같은 과정으로 결과를 반환한다.

 

나 : arr[2] = ?

컴퓨터 : 메모리 주소 1012부터 +2번째 1014에 3이 있네요

3.2 검색
자료내 특정 값을 찾는 연산으로, 최악의 시나리오 기준 N단계가 소요된다. 그 이유는 코드를 짠 '나'는 어디에 무슨 값이 있는지 알겠지만, 컴퓨터는 이에 대해 알 길이 없기 때문이다. 예를 들어, 배열에서 3이란 값 찾게 시킨다면 컴퓨터는 자료내 모든 요소들을 하나하나 뒤져봐야 한다(선형 검색 기준)

 

나 : 배열에서 3을 찾아와라 노예야
컴퓨터 : ㄱㄷ 하나씩 뒤져봄

컴퓨터는 자료에 어떤 값이 저장돼있는지 알 길이 없다.

3.3 삽입
배열 중간에 값을 삽입하려면 그 뒤쪽 값을 한칸씩 밀어서 자리를 하나 마련한 뒤 값을 꽂아넣어야한다. 따라서 최악의 시나리오 기준, N+1단계가 소요된다.

배열 = [ 1, 2, 3, 4 ]
나 : 배열의 2번째 자리에 '퇴근' 이란 값을 넣어라 노예야
컴퓨터 : 뒤쪽 다 밀고 넣어드림 ㄱㄷ

하나씩 뒤로 밀어줘야 한다

 

1.8 집합 (중복을 허용하지 않는 자료 구조)
배열 기반 집합을 기준으로 설명(자바스크립트 new Set( [ 1,2,3,4 ] )하고 비슷)

중복 금지라는 단 하나의 제약이 추가됐지만 효율성이 어떻게 달라지는지 보자
- 읽기 : 똑같음
- 검색 : 똑같음
- 삭제 : 똑같음
- 삽입 : 최악의 시나리오 2N+1 (집합 맨 앞에 값 삽입)

ㅇ삽입 과정(최악 시나리오 기준)
배열 = [ 1, 2, 3, 4 ]
나 : 배열의 제일 처음에 '퇴근' 이란 값을 넣어라 노예야
컴퓨터 : ㄱㄷ 일단 중복값이 있는지 한번 확인해봄
[ 1(확인완료), 2, 3, 4 ]
[ 1, 2(확인완료), 3, 4 ]
[ 1, 2, 3(확인완료), 4 ]
[ 1, 2, 3, 4(확인완료) ] ㅇㅋ 중복되지 않는 값이군 곧 넣어드림
[ 1, 2, 3, 빈칸, 4 ]
[ 1, 2, 빈칸, 3, 4 ]
[ 1, 빈칸, 2, 3, 4 ]
[ 빈칸, 1, 2, 3, 4 ]
[ '퇴근', 1, 2, 3, 4 ]