[알고리즘]파이썬 알고리즘 인터뷰 7장. 배열

배열

배열은 값 또는 변수 앨리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.

• 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 때로는 너무 작은 영역을 할당하여 모자라거나, 너무 많은 영역을 할당하여 낭비될 때도 있다
• 이를 위해 미리 크기를 지정하지 않고 자동으로 조정할 수 있는 배열인 동적 배열이 등장했다(파이썬에는 리스트가 바로 동적 배열 자료형이다)

동적배열

미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가 되면서 꽉 채워지면, 늘려주고 모두 복사하는 방식이다.

 

• 두 수의 합
  • 풀이 1: 브루트 포스로 계산
  • 풀이 2: in을 이용한 탐색
  • 풀이3: 첫 번째 수를 뺀 결과 키 조회
  • 풀이4: 조회 구조 개선
  • 풀이 5: 투 포인터 이용
  • 풀이 6: 고 구현
• 빗물 트래핑
  • 풀이1: 투 포인터를 최대로 이동
  • 풀이2: 스택 쌓기
• 세 수의 합
  • 풀이1: 브루트 포스로 계산
  • 투 포인터로 합 계산
• 배열 파티션1
  • 풀이1: 오름차순 풀이
  • 풀이2: 짝수 번째 값 계산
  • 파이썬다운 방식
• 자신을 제외한 배열의 곱
  • 풀이1: 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
• 주식을 사고팔기 가장 좋은 시점
  • 풀이1: 브루트 포스로 계산
  • 풀이2: 지점과 현재 값과의 차이 계산
  •