키워드 : 배열, 연결리스트, 스택, 큐, 해시테이블

알고리즘 ㅠㅠ
키워드 정리 - 배열은 자료형.
연결리스트, 스택, 큐, 해시테이블은 자료구조.
제일 자주 쓸건 스택이랑 데크.

Array 배열

파이썬에서 배열은 여러 원소(element가 될수도 있고 object가 될수도 있음)를 하나의 묶음으로 관리하는 자료형을 말한다.
각 원소간에는 순서가 존재하여 인덱스(Index)를 통해 접근하거나 뒤집을 수 있다.

리스트 list 와 튜플 tuple이 여기에 속한다.
인덱스는 슬라이싱을 사용할 수 있어서 좋다.

배열 조작

https://yaraba.tistory.com/1225

- 배열 자체를 조작하는 함수

연산자

a+=b : a 변수를 유지한채로 a에 b의 값을 더해주는 연산자 (a + b는 새로운 배열이다.)
a*=i : a 변수를 유지한채로 a를 복사해서 i만큼 늘려주는 연산자

내장함수

a.append(object) : 배열 맨 뒤에 요소를 추가한다.
a.insert(object, index) : 지정한 인덱스에 오브젝트를 밀어넣고 나머지는 옆으로 한칸씩 밀어낸다. (우측)
a.remove(object) : array 내에서 인자와 동일한 첫번째 object를 찾아 삭제하고 나머지를 옆으로 땡겨온다(좌측)
del a[index] : 지정한 인덱스에 있는 오브젝트를 삭제하고 나머지를 한칸씩 옆으로 땡겨온다. (좌측)

a.pop() : 배열 맨 뒤에서 요소를 뽑아낸다. (배열에서 삭제하고 나에게 리턴)
a.pop(0) : 배열 맨 처음에서 요소를 뽑아낸다. ==

a.extend(b) : 리스트 맨 뒤에 리스트를 붙여준다. (리스트 두개 합치기)

a.reverse() : 배열을 뒤집는다. 슬라이싱의 a = a[::-1]과 동일한 효과.
a.sort() : 배열을 오름차순으로 정렬.
a.sort(reverse=True) : 배열을 내림차순으로 정렬.

- 배열 내부를 스캔하는 함수

a.index(object) : array 내에서 인자와 동일한 첫번째 object를 찾아 그 index를 리턴한다.
a.count(object) : array 내에서 인자와 동일한 첫번째 object를 찾아 그게 몇개나 있는지 리턴한다.

min과 max가 리턴하는 것 : https://blockdmask.tistory.com/411

max(a) : 배열이 문자열일 경우 반복이 가능한 가장 긴 글자, 숫자일 경우 가장 큰 숫자를 리턴한다.
인자를 두개 넣을 경우, 두 배열을 비교하여 반복이 가능한 최소단위 중 가장 긴 값을 리턴.

min(a) : 배열이 문자열일 경우 가장 짧은 값, 숫자일 경우 가장 작은 숫자를 리턴한다.
인자를 두개 넣을 경우, 두 배열을 비교하여 반복이 가능한 가장 작은 값을 리턴.

object in a : 지정한 항목이 배열 내에 존재하면 True를 리턴한다.
all(a) : 배열 내 모든 원소가 True이면 True를 리턴한다.
any(a) : 배열이 빈 배열이 아니면 True를 리턴한다.

len(a) : 배열의 길이를 리턴해준다. 되게 자주 씀 ***

- 새로운 배열을 리턴하는 함수

연산자/슬라이싱

a+b : 배열 a와 b를 연결하여 새로운 배열을 리턴한다. 단 a와 b는 동일한 타입이어야 한다.
ex) list/list, tuple/tuple
a*i : 배열을 복사해서 배열 갯수를 지정한 수만큼 늘려준다.

b = a[::-1] : 배열을 뒤집은 새로운 배열을 리턴한다.

a[i:j:k] : 배열의 i 위치 부터 j위치까지(j는 제외. 직전 위치의 항목까지만)
k만큼씩 움직이며 각 원소를 추출하여 새로운 배열을 리턴한다.
이때 k가 음수면 역방향, i를 생략하면 맨 앞, j를 생략하면 맨 끝, k를 생략하면 1을 의미

a[::] 배열하고 똑같은 배열을 하나 복사해준다.

그냥 함수 (전부다 굉장히 자주쓰니까 외워두자)

• 제너레이터 함수
  range(i, j) : for문하고 같이쓰면 좋음. i 부터 j 직전의 정수를 list 타입으로 리턴하는 제너레이터 함수.
  range(j) = range(0, j)
  range(i,j,k) = i 부터 j 직전까지 k만큼씩 건너뛰어서 생성

• 빈 배열 만들기
  list() : 빈 list를 리턴.
  tuple() : 빈 tuple을 리턴.
  [0] * i : i만큼의 길이를 가진 빈 배열들을 리턴(연결리스트)

• 분리하는 새 배열
  list(a) : string a에 담긴 모든 문자를 각각 분리한 list를 리턴한다.
  tuple(a) : string a에 담긴 모든 문자를 각각 분리한 tuple을 리턴한다.
  a.split('sep') : 스트링 a를 sep = 구분자 기준으로 분리한 리스트를 리턴.
  sep을 따로 지정하지 않으면 공백으로 구분하여 리턴한다.

divmod(a, b) : a를 b로 나눈 몫과 나머지로 구성된 tuple을 리턴.

• 합쳐지는 새 배열
  'sep'.join(a) : 배열 a의 모든 원소를 구분자를 넣은 하나의 string으로 합쳐서 리턴한다.
  배열의 모든 원소가 문자열일때만 가능.
  sep을 따로 지정하지 않으면 공백으로 구분하여 리턴. 해당 스트링으로 각 항목들을 붙인다.
  '.\n'.join(a) : 각 열마다 온점과 개행을 덧붙여준다.

sum(a) : 배열 a의 모든 원소를 더한 결과를 리턴한다. 배열의 모든 원소가 숫자형일때만 가능.

zip(a, b,...) : 인자로 지정된 배열 또는 문자열의 각 원소들을
원소개수가 가장 작은 것을 기준으로 동일 인덱스로 묶어 새로운 배열을 리턴한다.

zip([1,2,3],('a','b','c'),['qqq','rrr'],"222222")

[(1, 'a', 'qqq', '2'), (2, 'b', 'rrr', '2')]

Linked list 연결리스트

배열의 단점을 보완하기 위해 만들어진 자료구조.
인덱스를 통해 빠른 접근이 가능한게 장점인 배열은 처음에 최대 크기를 정하고 시작하는거라
데이터를 추가/삭제하는 과정이 어려웠다, 그래서 유연성을 위해 연결이라는 개념을 만들었지만...

파이썬에서는 그냥 리스트가 연결리스트의 일을 전부 할 수 있어서 굳이 필요가 없는 자료구조다.

https://ybworld.tistory.com/85

연결리스트의 장점

배열과 배열 이어붙이기가 쉽다.
요소의 중간 삽입, 삭제가 쉽다.
연결리스트의 수정시 시간복잡도가 O(1)이다.

연결리스트의 단점

데이터 내부에 별도의 주소공간이 필요해서 저장효율이 높지 않다.
연결리스트의 검색시 연결 된 정보를 찾기 위해 주소를 확인하고 다음 데이터를 탐색하는 시간이 추가로 필요하다.
중간데이터를 삭제시, 앞뒤 데이터를 연결하고 재구성하는 코드가 추가로 필요하다.
검색시 시간복잡도가 O(n).

연결리스트의 구성요소

• Node : '데이터'와 다음 데이터를 가리키는 주소 = 'Pointer'로 이루어져 있다.

포인터의 종류

• Head : 링크드리스트에서 가장 시작점인 데이터를 의미.

• Tail : 링크드리스트에서 가장 마지막 데이터를 의미.

• Next, prev : 이름은 바꿀 수 있다. 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이 된다.

Stack 스택

데이터의 빠른 비교를 위한 후입선출 자료구조.
파이썬에서는 list를 가지고 자료의 출입에만 신경쓰면 바로 스택처럼 쓸수 있어서 딱히 구현에 고민할 필요는 없다.

https://ooeunz.tistory.com/7

stack의 구성

• init : 스택을 쌓을 빈 배열
• push : 자료를 넣을 때는 마지막에 추가되도록 append 함수를 꼭 사용해준다.
• pop : 자료를 뺄 때는 마지막에서 뺄 수 있도록 pop() 함수로 차례대로 빼준다.
• top : 자료를 빼지 않고 top에 뭐가 있는지만 확인하고 싶을때는 새배열을 리턴해주는 슬라이싱[-1]을 활용한다.
• is_empty : 간단하게 true false로 확인할 수 있다.

저 다섯가지의 메서드를 가진 클래스를 만들어도 되고 그냥 함수를 저걸 사용해줘도 된다.

스택은 데크와 더불어 코테에서 가장 많이 쓰이는 자료형이다!

Queue 큐

https://www.daleseo.com/python-queue/

데이터를 추가한 순서대로 제거할 수 있다는 특징으로 스트리밍(streaming),
너비 우선 탐색(breath first search) 같은 곳에 쓰이는 선입선출 자료구조.
파이썬에서는 list를 가지고 자료의 출입에만 신경쓰면 바로 큐처럼 쓸수 있어서 딱히 구현에 고민할 필요는 없다.
큐 모듈로 큐를 구현할 수도 있긴 하다!

사실 데크가 편리하게 이어서 큐를 잘 안쓰기 한다.

queue의 구성

• init : 큐를 쌓을 빈 배열
• push : 자료를 넣을 때는 마지막에 추가되도록 append 함수를 꼭 사용해준다.
• pop : 자료를 뺄 때는 첫번째에서 뺄 수 있도록 pop(0) 함수로 차례대로 빼준다.
• front : 자료를 빼지 않고 front에 뭐가 있는지만 확인하고 싶을때는 새배열을 리턴해주는 슬라이싱[0]을 활용한다.
• is_empty : 간단하게 true false로 확인할 수 있다.

queue 모듈에서의 구성

• 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리
• que.put(object) : 추가하면 그냥 하나하나 쌓인다.
• que.get() : 빼면 자동으로 첫번째꺼가 빠진다.

Deque 데크

collections 모듈의 deque는 double-ended queue의 약자로, 코테에서 많이 쓰이는 자료형이다!
같은 로직에서 시간복잡도를 획기적으로 줄여준다.
리스트의 처음과 끝에서 뭔가 찾아와야 하는 문제라면 데크를 쓰는게 좋다.
중간 어딘가면 오래걸리니까 그냥 다른거 쓰기...

deque의 구성

• init : 데크를 쌓을 빈 배열
• push : appendleft()를 하면 첫번째에, append()를 하면 마지막에 추가된다.
• pop : popleft()를 하면 첫번째에서 pop()을 하면 마지막에서 빼준다.
• is_empty : 간단하게 true false로 확인할 수 있다.
• 검색리턴은 슬라이싱을 적절히 활용한다.

hash table 해시테이블

https://jinyes-tistory.tistory.com/10

파이썬에서는 딕셔너리가 있어서 굳이 만들 필요는 없지만...
보안에 좋다!
데이터를 서칭하는 과정에서 배열을 순차적으로 탐색할 필요없이 해시 값으로 데이터를 빠르게 찾을 수 있다.

해시테이블의 구성

• 키(Key): 인풋 데이터 *ex) John Smith, Lisa Smith

• 값(value): 저장할 데이터 *ex) 521-8976, 521-1234

• 해쉬 함수(Hash Function): '키'를 해시로 변경해주는 함수 John Smith -> 002

• 해시(Hash): 인풋 데이터를 고정된 길이의 숫자열로 변환한 결과물

해시테이블의 단점 : 해시 충돌(Hash Collision)

해결법 1 : https://jinyes-tistory.tistory.com/11

해결법 2 : https://jinyes-tistory.tistory.com/12?category=841411