📗

파이썬 알고리즘 인터뷰 - 박상길

1. 기본 개념

가. 빅오, 자료형

1. 기본 개념

가. 빅오, 자료형

1) 빅오(big-O)란

•

입력값(n)이 무한히 커질 때, 함수의 실행 시간의 상한을 설명하는 수학적 표기 방법입니다.

2) 빅오메가(big-omega), 빅세타(big-theta)

•

빅오는 함수 실행 시간의 상한인 반면, 빅오메가와 빅세타는 각각 하한과 평균에 대한 표기입니다. 

3) 분할 상환 분석

•

‘실행 시간의 상한’만으로 알고리즘의 복잡도를 계산하는 것은 비관적이라는 관점에서 분할 상환 분석이 등장했습니다.

•

분할 상환 분석 방법은 최악의 경우를 여러 번으로 나눠서 계산합니다. 따라서 실행 시간의 상한에 치닫는 경우가 적을 경우, 상대적으로 복잡도가 낮게 표기됩니다.

4) 자료구조, 자료형, 추상 자료형

•

자료구조는 데이터를 효율적으로 관리하기 위한 데이터의 관리 구조입니다.

•

자료형은 프로그래머가 인터프리터에게 데이터를 사용하는 방법을 알려주는 데이터의 속성입니다.

•

추상 자료형(ADT)는 자료형에 대한 수학적 모델로, 자료형의 행동을 표현하지만 실제 구현 방법은 명시하지 않습니다.

나. 문자열 조작

1) 슬라이싱 내부 동작 원리

•

슬라이싱 문법의 인덱스가 지정되면 배열 포인터를 토대로 실제 값에 해당하는 객체를 반환합니다.

•

슬라이싱으로 반환된 객체는 새로운 자료구조에 값을 할당하는 것이나 반복문을 사용하는 것 보다 성능 면에서 우월합니다. 따라사 문자열을 조작하는 경우, 슬라이싱을 우선적으로 고려하는 것이 바람직합니다.

2) 람다와 리스트 컴프리헨션

•

람다 표현식이란 함수 시그니처를 생략하여 함수의 식을 다른 함수의 인자로 전달하는 것입니다. 예를 들어, 이하의 두 식은 동일한 결과를 가져옵니다.

•

람다의 단점은 표현식이 길어지면 전체적인 가독성이 떨어진다는 것입니다. 특히 map이나 filter 함수와 함께 사용할 때 가독성이 떨어집니다.

•

아래의 예시와 같이 다른 함수와 함께 사용하지 않고, 표현식이 짧을 경우에만 사용하는 것이 바람직합니다.

list.sort(key=lambda x: (x.split()[1:], x.split()[0]))
Python
복사

list.sort(key=func)

def func(x):
	return (x.split()[1:], x.split()[0]))
Python
복사

3) dictionary 활용

•

동일한 키 값을 갖는 요소들을 key:value 형태로 맵핑할 경우, defaultdict을 활용할 수 있습니다.

: 키가 없는 경우에 대비할 수 있습니다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list)

        for word in strs:
            anagrams["".join(sorted(word))].append(word)

        return anagrams.values()
Python
복사

4) sort() vs sorted()

•

sorted(list): 인자로 전달 받은 리스트의 요소를 직접 조작하지 않습니다. 인자로 받은 리스트를 토대로 정렬한 새로운 리스트를 반환합니다.

•

주어진 값을 오염시키지 않는다는 점에서 sorted 사용이 권장됩니다.

# 리스트가 아닌 문자열을 반환하려면 아래와 같이 join 연산이 필요합니다
str = “”.join(sorted(list))
Python
복사

•

list.sort(): 수신 객체인 리스트의 내부 요소를 정렬하며 반환값이 없습니다.

alist = list.sort() # 잘못된 사용법
Python
복사

5) split vs join

•

split

: 구분자를 토대로 문자열 내 문자를 요소로 갖는 리스트로 반환합니다.

: split() 기본형으로 사용될 때 whitespace characters (ex spaces, tabs, and newlines)를 제거합니다.

s = " hello world "
s.split() # ["hello", "world"]
Python
복사

•

join(): 리스트 요소를 수신객체 전달 받은 값으로 이어서 생성한 문자열을 반환합니다.

class Solution:
    def reverseWords(self, s: str) -> str:
        result = s.split() # ["the", "sky", "is", "blue"]
        result.reverse() # ["blue", "is", "sky", "the"]
        return " ".join(result)

Input: s = " the sky is blue "
Output: "blue is sky the"
Python
복사

라. 문자열 문제

1) 팰린드롬(회문) 구별

•

Queue 활용

•

정규표현식 & 슬라이싱 활용

•

문제: https://leetcode.com/problems/valid-palindrome/

2) 문자열 뒤집기

•

two pointer 활용

•

pythonic way

•

문제: https://leetcode.com/problems/reverse-string/

3) 문자열 재정렬

•

람다 활용

•

문제: https://leetcode.com/problems/reorder-data-in-log-files/

4) 가장 빈번한 단어 찾기

•

리스트 컴프리헨션 & counter 활용

•

문제: https://leetcode.com/problems/most-common-word/

5) 문자열 배열 정렬

•

정렬과 딕셔너리 활용

•

문제: https://leetcode.com/problems/group-anagrams/

6) 부분 문자열 반환 - 어렵다 추후 다시 보자

•

two pointer 활용

•

문제: https://leetcode.com/problems/longest-palindromic-substring/