Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 이론

Do it 알고리즘 코딩테스트 하루코딩 3장 자료구조 요약

# 5 배열과 리스트 java

배열

메모리에 연속적인 공간에 값을 저장하는 자료구조

특징

1. 인덱싱O, 접근속도 ↑

2. 값 삽입, 삭제 번거로움, 속도 ↓, 주변 값 이동시키는 과정 필요

3. 크기 선언할 때 지정O, 크기 고정

4. 구조 간단

 

리스트

값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조

특징

1. 인덱싱X, 접근속도 ↓, Head 포인터부터 순서대로 접근하여 속도 느림

2. 값 삽입, 삭제 편리, 속도 ↑, 주변 값 이동시키는 과정 필요X

3. 크기 선언할때 지정X, 크기 가변

4. 구조 복잡

 

java에서는

ArrayList

LinkedList

 

상황별 유리한 자료구조

배열: 크기고정, 값 접근

리스트: 크기가변, 삽입, 삭제 빈번

 

#6 배열과 리스트 python

파이썬에서는 배열과 리스트 구분없이 리스트 사용

다른 프로그래밍 언어와 달리 리스트가 배열의 특징도 포함하고 있기 때문

 

파이썬에서 리스트

특징

1. 인덱싱 O

2. 크기가변

 

# 7 구간합

구간합

배열의 인덱스 구간의 요소 합인 구간합을 구하는 알고리즘이다.

합배열을 이용하여 시간 복잡도 ↓

 

합배열의 정의

S[i] = A[0] + A[1] + ... + A[i] // 원본 배열 A의 인덱스 0~ i번째 요소의 합

ex) S[4] == A[0] + A[1] + A[2] + A[3] + A[4]

 

합배열 만드는 공식

S[0] = A[0]

S[i] = S[i-1] + A[i] # i가 0이 아닌 경우

 

합배열을 이용하여 구간합을 구하는 공식

S[j] - S[i-1] # 원본 배열 A의 인덱스 i~j까지 요소의 구간합 

 

원본 배열이 바뀌지 않는 경우 합배열 이용하여 구간합

원본 배열이 바뀌는 경우 segment tree(index tree) 를 이용하여 구간합

 

# 8 스택과 큐 java

배열에서 발전된 자료구조

 

스택

후입선출 LIFO, 한 쪽에서만

push() // 삽입

pop() // 삭제, 확인

peek() // 확인만

top // 위

 

DFS, 백트래킹 // 재귀함수 알고리즘 원리와 유사

 

큐

선입선출 FIFO, 양 쪽에서

add() // 삽입

poll() // 삭제, 확인

peek() // 확인만

front // 앞

rear // 뒤

 

BFS

 

우선순위 큐

들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

front에 항상 최솟값 또는 최댓값 위치 // 그 이하의 데이터가 모두 정렬되어 있다는 뜻은 아니다.

힙을 이용하여 구현

 

# 9 스택과 큐 python

리스트에서 발전된 자료구조

 

스택

s.append() # 삽입

s.pop() # 삭제, 확인

s[-1] # 확인만

top # 위

 

큐

파이썬에서 list, deque를 이용하여 구현 # 코딩테스트에서 deque가 유리

s.append() # 삽입

s.popleft() # 삭제, 확인

s[0] # 확인만

front # 앞

rear # 뒤

 

투포인터

슬라이딩 윈도우