[3부] 07장 배열

선형 자료구조 & 비선형 자료구조

출처: 파이썬 알고리즘 인터뷰

선형 자료구조 (Linear)

• 자료를 구성하는 데이터를 순차적으로 나열한 형태
• 자료들 간의 앞뒤 관계가 1:1의 선형 관계
• 배열, 스택, 큐, 연결 리스트, 데크 등

선형 자료구조

비선형 자료구조  (Non Linear)

• 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태
• 자료들 간의 앞뒤 관계가 1:n, n:n 의 관계
• 트리, 그래프 등 (계층적 구조)

비선형 자료구조

디스크 공간 할당 (Dist Space Allocation)

파일 할당 (사용자가 하나의 파일을 불러올 때, 디스크에 블록 단위로 흩어져 있는 파일을 신속하게 찾아내고, 신속하게 저장하기 위해서) 에는 다양한 방법이 있음. 크게 3가지 방법을 알아봄. 

• 연속 할당 (Contiguous allocation)
• 연결 할당 (Linked list allocation)
• 색인 할당 (Index allocation)

연속 할당 (Contiguous allocation)

각 파일에 대해, 디스크 상의 연속된 블록을 할당하는 방법. 

• 하드 디스크에 block 들이 나열되어 있는데, 여기에 연속된 순서대로 파일 저장. 

연속 할당

장점	단점
디스크가 읽어 들어갈 때, 이동 경로 최소화	특정 파일이 삭제되면, 중간에 빈 공간인 hole 생성 -> 반복해서 hole이 생성, 외부 단편화 -> 디스크 공간 낭비 매우 심함
빠른 I/O 성능	연속되게 파일을 할당하면, 중간에 파일의 크게를 계속 증가시킬 수 없음. (파일의 크기 조절 불가능)
순차적으로 읽을 수 있고, 특정 부분을 바로 읽을 수 있음

연결 할당 (Linked list allocation)

각 파일을 linked list의 형태로 저장하는 것.

• 파일은 각자 디렉토리를 가지고 있는데, 어떤 block에 할당되었는지 이 디렉토리에 저장됨. 
• 연속 할당에서는 디렉토리에 제일 처음 저장되는 block을 저장하고, 각 block은 다음 block을 지칭함. (포인터 저장을 위한 4바이트 이상을 가지고 있음.

연결 할당

장점	단점
외부 단편화 없앰.	각각 순서대로 포인터로 연결되어 있기 때문에, 순서대로 읽는 것 밖에 할 수 없음 (즉, 중간에 있는 자료만 읽지 못함)
	포인터 저장을 위해 4바이트 이상 손실
	만약 포인터가 끊어지면, 이하 접근 불가능
	포인터를 따라가는 과정 때문에 속도 면에서 느림

색인 할당 (Index allocation)

파일 당 인덱스 block을 사용하여 파일 할당

• 인덱스 block: 각 파일에 할당된 포인터를 저장하는 모음
• 연결 할당과 같은 방식으로 할당을 하지만, 인덱스 block을 둔다는 점에서 다름. 

색인 할당

장점	단점
연속 할당의 장점) 순서적으로 읽을 수 있음, 특정 부분을 바로 읽을 수 있음	인덱스 블록에 할당에 따른 저장 공간의 손실
연결 할당의 장점) 외부 단편화 없음

---

파이썬에 한정된 이야기 아님!
프로그래밍 언어 전반에 대한 이야기임.

책) 자료구조는 크게 메모리 공간 기반의 연속 방식 (Contiguous) 방식과 포인터 기반의 연결 방식 (Linked) 으로 나뉨. 

• 연속 방식의 (Contiguous allocation) 가장 기본이 되는 자료형: 배열 (7장)
• 연결 방식의 (Linked list allocation) 가장 기본이 되는 자료형: 연결 리스트 (8장)

배열: 값 또는 변수 엘리먼트의 집함으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별됨. 

• 정적 배열
• 동적 배열

정적 배열 

• 배열은 크기를 지정하고, 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형. 
• 크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능. 

정적 배열

동적 배열 

• 크기를 지정하지 않고, 자동으로 리사이징 하는 배열. 
• 동적 배열의 원리
  
  • 처음 동적 배열이 생성되었을 때, 일정한 크기를 갖는 배열 할당하고 원소 추가. 
  • 추가된 원소의 총 개수가 동적 배열이 가진 크기를 넘어가면 기존의 크기의 n배의 크기를 갖는 배열을 새로 할당
    • 대개는 더블링 (Doubling) 이라 하여 2배씩 늘려주는데, 모든 언어가 항상 그런 것은 아니며 각 언어마다 늘려가는 비율은 상이함.
    • 재할당 비율을 Growth Factor (재할당 비율; 성장 인자) 라고 함. 파이썬의 그로스 팩터는 초반에는 2배씩 늘려가지만, 전체적으로 1,125배로, 다른 언어에 비해서는 다소 조금만 늘려가는 형태로 구현됨. 
    • 참고) 자바의 ArrayList는 1.5배, C++의 std::vector, 루비는 2배
  • 기존의 원소를 새로운 배열에 복사한 후, 새로운 배열로 바꿔치기. 

동적 배열

언어별 비교

구분	배열	리스트	비고
C	배열 지원	리스트 지원하지 않음	리스트를 사용하려면, 직접 만들거나 라이브러리를 사용해야 함
JavaScript	배열에 리스트의 기능이 포함되어 있음
Java	배열 지원 (Array)	리스트 지원	배열과 리스트가 완전히 분리되어 있음 두 가지 형태의 리스트 지원 (LinkedList, ArrayList)
Python	배열 지원하지 않음	리스트 지원

+Java 추가)

Array (정적 배열)

• 정적인 길이를 제공하는 배열

ArrayList (데이터 검색 유리, 추가 및 삭제 불리) (동적 배열)

• 배열을 이용해서 리스트를 구현한 것. 즉, 내부적으로 데이터를 배열에 저장.
• 데이터 추가: 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면, 이후의 데이터들이 한칸씩 뒤로 물러남. 
• 데이터 삭제: 빈자리가 생기면, 빈자리를 채우기 위해서 순차적으로 한칸씩 땡김. 
• 데이터 조회: 인덱스를 이용하여 데이터를 가져옴. (메모리 상의 주소를 정확하게 참고해서 가져옴)
• 장점: 내부적으로 배열을 사용하기 때문에 인덱스를 이용해서 접근하는 것이 빠름. 
• 단점: 데이터의 추가와 삭제가 느림. 

ArrayList

LinkedList (추가 및 삭제 유리, 데이터 검색 불리) (연결리스트)

• 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있음. 
• 데이터 추가, 삭제: 이전 노드와 다음 노드를 참조하는 상태만 변경
  • 데이터 추가, 삭제 시, ArrayList와 비교해 굉장히 빠름. 

LinkedList

---

no.	title	leetcode	status
7	두 수의 합	리트코드 1	O
8	빗물 트래핑	리트코드 42	O
9	세 수의 합	리트코드 15	O (02/15)
10	배열 파티션 1	리트코드 561	O
11	자신을 제외한 배열의 곱	리트코드 238	X
12	주식을 사고팔기 가장 조은 시점	리트코드 121	X

No.07 두 수의 합

출처: 리트코드

My Solution) Brute-Force

48ms, 14.6MB
시간 복잡도 O(n^2)

My Solution) Brute-Force

책 풀이

Solution 1) Brute-Force

• 브루트 포스 (Brute-Force): 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방식
• 무차별 대입 방식인 브루트 포스는, 비효율적인 풀이 방식임. 풀이 시간 복잡도는 O(n^2)

44ms, 14.2MB

Solution 1) Brute-Force

Solution 1) Brute-Force

Solution 2) in을 이용한 탐색

• 같은 시간 복잡도라도, in 연산 쪽이 브루스 포트 연산보다 가볍고 빠름. (파이썬의 내부 함수로 구현된 in 은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 더 빨리 실행됨.)

48ms, 14.4MB

Solution 2) in을 이용한 탐색

Solution 2) in을 이용한 탐색

Solution 3) 첫 번째 수를 뺀 결과 키 조회

52ms, 14.3MB

Solution 3) 첫 번째 수를 뺀 결과 키 조회

Solution 3) 첫 번째 수를 뺀 결과 키 조회

• i != nums_map[target_num]: 
  • e.g. [3, 2, 4], target = 6 일 때, 맨 앞의 3을 두 번 더하는 중복을 막기 위함. 

Solution 4) 조회 구조 개선

• 전체 값을 모두 딕셔너리에 저장할 필요 없이, 정답을 찾게 되면, 함수를 바로 빠져나올 수 있음. 그러나 3번 풀이에 비해 성능상의 큰 이점은 없은 듯. 

40ms, 14.4MB

Solution 4) 조회 구조 개선

Solution 4) 조회 구조 개선

No.08 빗물 트래핑

출처: 리트코드

My Solution)

68ms, 14.9MB
시간 복잡도: O(n^2)

My Solution)

My Solution)

책 풀이

Solution 1) 투 포인터를 최대로 이동

Solution 1) 투 포인터를 최대로 이동

Solution 1) 투 포인터를 최대로 이동

Solution 2) 스택 쌓기

이해를 못 했음..

No.09 세 수의 합

출처: 리트코드

My Solution 1) 브루트 포스로 계산 -> Time Limit Exceeded

My Solution 2)

5352ms, 17.5MB
시간 복잡도: O(n^2)

의사코드 (허점 많음)

My Solution 2)

책 풀이

Solution 1) 투 포인터로 합 계산

3360ms, 17.6MB

Solution 1) 투 포인터로 합 계산

 

No.10 배열 파티션 1

출처: 리트코드

My Solution)

260ms, 16.9MB
시간 복잡도: O(n^2)

My Solution)

My Solution)

책 풀이

Solution 1) 오름차순 풀이

296ms, 16.9MB

Solution 1) 오름차순 풀이

Solution 1) 오름차순 풀이

Solution 2) 짝수 번째 값 계산

• 매번 min()을 계산하지 않고, 단순히 해당 인덱스를 찾기만 하면 되므로, Solution 1) 보다 좀 더 성능이 좋음.

288ms, 17MB

Solution 2) 짝수 번째 값 계산

Solution 2) 짝수 번째 값 계산

Solution 3) Pythonic Way

• 슬라이싱 활용

264ms, 16.6MB

Solution 3) Pythonic Way

Solution 3) Pythonic Way

No.11 자신을 제외한 배열의 곱 (아직 못 품)

No.12 주식을 사고팔기 가장 좋은 시점 (아직 못 품)