파이썬 알고리즘 인터뷰 - 배열, 투 포인터 기법, 최댓값과 최솟값

배열

• 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.
• 어느 위치에서나 O(1)에 조회가 가능하다는 장점이 있다.

 

자료구조는 크게 메모리 공간 기반의 연속 방식, 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. 연결 방식의 기본이 되는 자료형은 연결 리스트이다. 추상 자료형(ADT)의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다.

Ex.) 스택을 연결 리스트로 구현, 큐는 배열로 구현 

 

파이썬에서는 정적 배열 x, 동적 배열인 리스트만 제공된다.

동적 배열의 원리 : 초깃값을 작게 잡아 배열생성 -> 데이터 추가되면서 채워지면 늘려지고 복사하는 방식(더블링이라고함)

이러한 재할당 비율을 그로스 팩터(Growth Factor), 성장 인자라고 한다. 파이썬의 그로스 팩터는 초반에 2배, 전체적으로 1.125배 씩 늘려가고 다른 언어에 비해 조금씩만 늘려가는 형태로 구현되어 있다.

 

 

투 포인터

투 포인터 예시

• 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략 
• 투 포인터는 주로 정렬된 배열을 대상으로 하며, 2개의 포인터가 좌우로 자유롭게 움직이며 문제를 풀이한다.
• 실전적으로 많이 쓰이는 알고리즘 풀이이다.

#투포인터 예시
def reverseString(self, s: List[str]) -> None:
    left, right = 0, len(s) -1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

 

 

최댓값과 최솟값

• 최댓값과 최솟값의 초깃값을 지정하는 방법에는 여러가지가 있다. 최댓값에는 가장 낮은 값을 초깃값으로 해야 어떤 값이든 최댓값과 교체될 수 있고 최솟값에는 가장 높은 값을 초깃값으로 해야 어떤 값이든 최솟값으로 바로 교체될 수 있다.
• 파이썬의 sys 모듈을 사용하면 좀 더 편리하게 높은 값, 낮은 값을 활용할 수 있다.

import sys

mx = sys.maxsize  # 최댓값
mn = sys.maxsize  # 최솟값

# float()를 이용해 다음과 같이 무한대 값을 지정하는 방법도 있다.
mx = float('-inf')
mn = float('inf')

• 가장 좋지 않은 방법은 다음과 같이 큰 값을 설정해야 하는데 9999999와 같은 임의의 값을 지정하는 것이다.

mn = 999999

• 파이썬의 숫자형은 임의 정밀도를 지원하며 사실상 무한대의 값을 지정 할 수 있다. 얼마든지 더 큰 수가 지정될 수 있으므로 이런 방식으로 최솟값을 정하는 것은 문제가 될 수 있다.