배열
- 자료구조
자료구조는 연속 방식이냐 연결 방식이냐로 나뉨
- 연속 방식
메모리 공간 기반
배열이 가장 기본 자료형
- 연결
포인터 기반의 연결
연결 리스트가 가장 기본 자료형
- 배열
연속 방식의 가장 기본이 되는 자료형
크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당하는 작업을 수행함
컴파일러는 메모리에 대한 접근을 바이트 단위별로 함
메모리 주소가 연속되기 때문에 어느 위치에나 O(1) 에 조회가 가능
- 메모리와 포인터
- 포인터
메모리 영역을 1바이트 단위로 가리키는 주소
컴퓨터의 명령어 길이에 따라 지정할 수 있는 메모리 주소의 수가 다름
- 정적/동적 배열
배열은 크기를 어떻게 관리하느냐에 따라 정적/동적 배열로 나뉨
- 정적 배열
배정된 크기만큼 연속된 메모리가 할당되는 것
- 동적 배열
메모리 공간이 동적으로 변하는 배열
대부분 언어들이 지원하며 파이썬이 채택함
초깃값을 작게 잡아 배열을 생성하고 데이터가 추가되어 꽉 채워지면 더블링을 사용하여 배열을 채워넣음
- 더블링
동적 배열에서 초깃값을 작게 잡아 배열을 생성하고 데이터가 추가되어 꽉 채워지면 늘려주고 모두 복사하는 방식
파이썬은 2배보다 작은 정도로 늘림
배열을 복사하는 방식이 사용되므로 최악의 경우 O(n)이 걸릴 수 있지만 분할 상환 분석에 따른 입력시간은 여전히 O(1)
- in
시퀸스를 조회하는 연산자
C로 작성해서 리소스가 많이 들어가지 않음
- 투 포인터
두 점을 (양 끝점 이나 왼쪽 포인터와 오른쪽 포인터 두 지점을)기준으로 하는 문제 풀이 전략
배열에서 주로 사용함
요소가 정렬되어 있을때가 효율적임
- 다른 언어
같은 로직이라도 Python 보다 C++, Go, Java 가 훨씬 빠를 수 있음
Python 으로 풀다가 시간 초과될 시 다른 언어로 풀이하는 방법도 있음
- 시각화
어려운 문제에서 풀이에 대한 직관이 떠오를 수 있음
- 최댓값과 최솟값
Python 에서 지원하는 +-system.maxsize, float(‘+-inf’) 를 이용하면 최대, 최소 쉽게 사용 가능
문제에서 최대/최소값 주는 경우가 많아서 적용하는게 더 좋을 수 있음