코딩 테스트를 위한 파이썬 문법과 알고리즘 정리

변수 선언 & 타입 힌트
컴프리헨션
제너레이터
Range
enumerate
나눗셈 연산자
print 함수
locals 함수
컨벤션
시간복잡도
자료형
슬라이싱
DFS, depth-first search
BFS, breadth-first search
DFS/BFS 특징
Dijkstra & Heap
재귀 - Recursion
동적 프로그래밍 - Dynamic Progamming
백트레킹 - Backtracking
문자열 입력받기

A. 기타 정보들
A-1. 10^8을 넘지 않는 N^M 정리

읽기 전에

코테를 풀기 위한 제한적인 문법만 설명한다.
어떤 알고리즘이나 자료구조는 다양한 구현 방법이 있지만, 이 글에서는 나에게 익숙하고 쉬운 방법으로 설명한다.

변수 선언 & 타입 힌트 - variable declaration & type hint

명시적 선언을 통해 가독성 up, 버그 발생 확률 down

num = 1
num_type_hint: int = 1
string: str = "1"
arr: list = ['A', 'C', 'B']  # = list("ACB")
dictionary: dict = {0: 'A', 1: 'B', 2: 'C'}
s: set = set([1, 2, 3])  # = set("123")

a: str = "1"
b: int = 1


def fn(a: int) -> bool:
    ...

강제 규약이 아니기에 동적 할당될 수 있으므로 주의 필요

>>> a: str = 1
>>> type(a)

class <'int'>

컴프리헨션 - comprehension

한 줄로 간결하게 작성 가능하여, 가독성이 좋은 편
일반적으로 표현식(for, if)이 2개를 넘어가면 가독성이 안좋아진다.

>>> [n * 2 for n in range(1, 10 + 1) if n % 2 == 1]
[2, 6, 10, 14, 18]

다음과 같이 처리

a = {key: value for key, value in original.items()}

제너레이터 - generator

루프의 반복 동작을 제어할 수 있는 루틴 형태

def get_natural_number():
    n = 0


while True:
    n += 1
    yield  # return이 아닌 yield를 사용하면 제너레이터가 반환된다.

>>> g = get_natural_number()
>>> for _ in range(0, 100):
    print(next(g))  # next를 통해 다음 결과를 반환
>>>

def generator():
    yield 1
    yield 'string'
    yield True

>>> g = generator
>>> next(g)
1
>>> next(g)
'string'
>>> next(g)
True

Range

제너레이터 중 하나,
제너레이터의 용량 면에서 장점을 알 수 있음.

>>> a = [n for n in range(1000000)]
>>> b = range(1000000)
>>> len(a) == len(b)
True
>>> sys.getsizeof(a)
8697464
>>> sys.getsizeof(b)
48

사용법

range(A, B, C)

A부터 B-1까지, C만큼씩
A는 기본값 0, C는 기본값 1, B는 필수
인수가 2개인 경우는 range(A, B)

enumerate

열거하다 라는 뜻의 함수
인덱스를 포함한 enumerate 객체 반환
a = [’a1’, ‘a2’, ‘a3’]를 인덱스와 함께 출력해야 할 때

for i, v in enumerate(a):
    print(i, v)

나눗셈 연산자 - division operator

/ : 실수형 몫
- 5 / 3 = 1.666666667
// : 정수형 몫 (int(5 / 3))
- 5 // 3 = 1
%: 나머지 (modulo, 모듈로 연산)
- 5 % 3 = 2
divmod(): 몫과 나머지 한번에
- divmod(5, 3) = (1, 2)

print

코테에서 디버깅 할 때 자주 쓰인다. (당연하지만 실제 서비스에서는 디버깅용으로 안 씀.)

>>> print('aa', end=' ')
>>> print('bb')
aa
bb

>>> a = ['A', 'B']
>>> print(' '.join(a))
A
B

>>> print(f'{idx + 1}: {fruit}')
2: Apple

locals

클래스 메서드 내부의 모든 로컬 변수를 가져오기 때문에, 디버깅에 사용함

print(locals())

"""
{'_': 99,
...
 '__doc__': None,
 '__file__': '/Users/sijunyang/PycharmProjects/code_test/syntax.py',
...
 'arr': ['A', 'C', 'B'],
 'dictionary': {0: 'A', 1: 'B', 2: 'C'},
 'g': <generator object get_natural_number at 0x104f320b0>,
 'generator': <function generator at 0x104f25ee0>,
...
 'v': 'B'}
 """

컨벤션 - convention

공식(PEP8), 구글 컨벤션 일부 정리

들여쓰기: 4개 공백 들여쓰기
줄 길이: 한 줄의 코드는 가능한 80자 이내
네이밍 컨벤션: 모듈 이름, 패키지 이름, 클래스 이름, 메소드 이름, 함수 이름, 전역 상수 이름 등에 대한 명확한 네이밍 컨벤션을 따릅니다.
- 함수명, 변수명, 메소드명: 소문자로 작성하고, 단어 간에는 언더스코어(_)를 사용합니다.
- 클래스명: CapWords 방식을 사용합니다. 이는 각 단어의 첫 글자를 대문자로 하고, 단어 사이에 공백이나 언더스코어를 넣지 않는 방식입니다.
- 모듈명, 패키지명: 짧은 소문자로 구성하며, 필요하다면 언더스코어를 사용합니다.
- 상수명: 모두 대문자로 작성하고, 단어 간에는 언더스코어를 사용합니다.
주석: 코드에 주석을 달 때는 세 개의 큰따옴표(""")를 사용하여 작성합니다.
타입 어노테이션: 가능한 한 타입 어노테이션을 사용하여 코드의 명확성을 높입니다.
함수의 기본값으로 빈 collection 사용하지 않기 : 빈 컬렉션을 기본 인자로 사용하고 그것을 변경하면, 그 변경사항이 함수의 모든 후속 호출에 영향을 미칩니다.
- ```
def my_function(arg=None):
if arg is None:
    arg = []
# 나머지 코드 
```

시간복잡도 - Time Complexity

점근적 실행 시간(Asymptotic Running Time)

입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행 시간의 추이를 의미한다.

시간복잡도(Time Complexity)

어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)

빅오(Big-O) 별 특징

O(1): 상수 시간. 입력값이 아무리 커도 실행 시간이 일정하다. 해시테이블의 조회 및 삽입이 이에 해당한다.
O(logN): 로그 시간. 매우 큰 입력값에도 크게 영향을 받지 않는다. 이진 검색이 이에 해당한다.
O(N): 선형 시간. 수행 시간이 입력값에 비례한다. 정렬되지 않은 리스트에서 최대값 또는 최솟값 경우가 이에 해당한다.
O(NlogN): 선형 로그 시간. 대부분의 효율적인 알고리즘이 이에 해당한다. 병합 정렬 등.
O(N^2): 제곱 시간. 비효율적인 정렬 알고리즘이 이에 해당한다.
O(2^N): 지수 시간. 피보나치를 재귀로 계산하는 알고리즘이 이에 해당한다.
O(N!): 팩토리얼 시간. 외판원 문제(Traveling Salesman Problem)를 Brute Force로 풀이할 때가 이에 해당한다.

빅오(O), 빅오메가(Ω), 빅세타(Θ)

빅오: 상한(Upper Bound)을 의미한다. 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.
빅오메가: 하한(Lower Bound)을 의미한다.
빅세타: 평균을 의미한다.
학계와 달리 업계에서는 빅세타와 빅오를 하나로 합쳐서 단순화해 표현한다.
상한은 최악의 경우와 다르다. 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 적당히 정확하게 표현하는 것이다.

자료형 - types

타입 계층 구조 - data types tree

클래스	불변 객체
bool	O
int	O
float	O
list	X
tuple	O
str	O
set	X
dict	X

객체 특성 - object attributes

파이썬에서 객체는 값(value), 유형(type), 정체성(identity) 3가지 특성을 가진다.

값: 객체의 실제 정보
유형: 객체의 분류
정체성: 객체의 고유번호(메모리 주소)

불변 객체를 가지는 변수의 값을 변경하면, 기존 객체를 수정하는 것이 아니라 새로운 객체로 대체한다.

a: str = "ABC"
print(id(a))  # 출력: 4338831984 - 메모리 주소 1
a = "XYZ"
print(id(a))  # 출력: 4340295152 - 메모리 주소 2

파이썬 정수형 - integer type

파이썬은 int의 범위를 넘어서는 정수형 데이터가 들어오면 오버플로우가 발생하는 것이 아니라 자동으로 long 타입으로 변경된다.
파이썬은 원시 타입 숫자 자료형을 제공하지 않는다. 임의 정밀도 정수형 int 하나로 모든 숫자 자료형을 처리한다.

bool 타입

bool은 내부적으로 1과 0으로 처리되는 int의 서브 클래스이다.

임의 정밀도 - arbitrary precision

임의 정밀도 정수형이란 무제한 자릿수를 제공하는 정수형을 말한다.

원시 타입 - raw type

메모리에 정확하게 타입 크기만큼의 공간을 할당하고 그 공간을 오로지 값으로 채워넣는다.
파이썬은 애초에 편리한 기능 제공이 우선순위이므로 느린 속도와 더 많은 메모리를 차지하더라도 다양한 기능을 제공하는 객체만 제공하고 원시 타입은 지원하지 않는다.

슬라이싱 - slicing

파이썬에서 문자열 슬라이싱은 (내부적으로) 매우 빠르게 동작하며, 문자열을 조작할 때 속도 개선에 유리하다.
별도 자료형과 문자열 사이의 매핑이 필요한 경우 전체적인 속도에서 손해를 볼 수 있으니 주의, 대부분의 문자열 작업은 슬라이싱이 가장 뻐르다.

사용 예시

S[1:4] = 녕하세: 인덱스 1에서(0부터 시작) 4이전까지(4는 포함하지 않는다) 표현한다. 4개를 의미하는 게 아니므로 유의해야 한다.
S[1:-2] = 녕하: 인덱스 1에서 -2이전까지(-2는 포함하지 않는다) 표현한다. 뒤에서부터는 음수로 접근이 가능하다.
S[1:] = 녕하세요: 문자열의 시작 또는 끝은 생략 가능하다.
S[:] = 안녕하세요: 둘 다 생략하면 사본을 반환한다.
- 파이썬은 a=b와 같은 형태로 할당하면 변수의 값이 할당되는 것이 아니라 a 변수가 b 변수를 참조하는 형태가 된다.
- 참조가 아닌 값 복사를 위해 [:]를 사용할 수 있으며, 문자열이나 리스트를 복사하는 파이썬다운 방식(Pythonic Way)이기도 하다.
S[1:100] = 녕하세요: 인덱스가 지나치게 클 경우 문자열의 최대 길이만큼만 표현된다. S[1:]과 동일하다.
S[-1] = 요: 마지막 문자(뒤에서 첫 번째)
S[-4] = 녕: 뒤에서 4번째
S[:-3] = 안녕: 뒤에서 3개 글자 앞까지
S[-3:] = 하세요: 뒤에서 3번째 문자에서 마지막까지
S[::1] = 안녕하세요: 1은 기본값으로 동일하다.
S[::-1] = 요세하녕안: 뒤집는다.
S[::2] = 안하요: 2칸씩 앞으로 이동한다.

DFS, depth-first search

이진 트리를 DFS(depth-first search) 방식으로 순회하는 코드

def dfs(node):
    if node is None:
        return
    # preorder
    dfs(node.left)
    # inorder
    dfs(node.right)
    # postorder

그래프를 BFS로 순회하는 코드

graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B']
}

visited = []

def dfs(cur_v):
    visited.append(cur_v)
    # pre order
    for v in graph[cur_v]:
        if v not in visited:
            dfs(v)
    # post order

반복문+Stack을 사용해 구현한 예시

def iterative_dfs(start):
    visited = [start]
    stack = []
    stack.append(start)
    while stack:
        cur_v = stack.pop()
        if cur_v not in visited:
            visited.append(cur_v)
            for v in graph[cur_v]:
                stack.append(v)
    return visited

BFS, breadth-first search

이진 트리를 BFS(depth-first search) 방식으로 순회하는 코드

def bfs(node):
    visited = []
    if node is None:
        return 0
    q = collections.deque()
    q.append(node)
    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    return visited

그래프를 BFS로 순회하는 코드

graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B']
}

def bfs(start):
    visited = [start]
    q = collections.deque()
    q.append(start)
    while q:
        cur_v = q.popleft()
        # do something
        for v in graph[cur_v]:
            if v not in visited:
                visited.append(v)
                q.append(v)
    return visited

DFS/BFS 특징

DFS, BFS 반복문으로 구현 시, 특징

둘 다 자료구조에 든 요소가 빌 때까지 반복하여 수행되는 것은 동일하다.

BFS는 인접한 요소들 중, 읽지 않은 요소를 queue에 담는다.
DFS는 현재 요소가 읽히지 않은 상태라면, 인접한 요소를 stack에 담는다.

Dijkstra & Heap

그리디 알고리즘 패턴 중 하나로, 가장 작은 Cost를 가지는 Vertax에 순차적으로 접근하는 방식으로 구현한다.

코드 구현 시, 접근 가능한 Vertax 중 가장 Cost가 작은 값을 구하기 위해 주로 Primary Queue(Heap)를 사용한다.

가장 기본적인 Dijkstra 구현 예시

import heapq

def dijkstra(graph, start, final, n):
    costs = {}
    pq = []
    heapq.heappush(pq, (0, start)) # cost, start

    while pq:
        cur_cost, cur_v = heapq.heappop(pq)
        if cur_v not in costs:
            costs[cur_v] = cur_cost
            for cost, next_v in graph[cur_v]:
                next_cost = cost + cur_cost
                heapq.heappush(pq, (next_cost, next_v))
    return costs[final]

재귀 - Recursion

재귀의 정의

💡 자신을 정의할때, 자기 자신을 재참조하는 것

예시

팩토리얼(factorial)

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

피보나치(fibonacci)

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

재귀의 수학적 접근

재귀는 아래 조건을 만족해야 한다.

base case: 더 이상 자기 자신을 재참조 하지 않는 상황
recurrence relation(점화식): 자기 자신을 호출(참조)하는 식

재귀의 시간복잡도

Note

재귀의 시간복잡도 = 재귀 함수 호출 수 x (재귀 함수 하나당) 시간복잡도

factorial의 경우

재귀 함수 호출 수 ⇒ $n$
재귀 함수 하나 당 시간복잡도 ⇒ $O(1)$
재귀의 시간 복잡도 ⇒ $O(n \times 1)$

fibo의 경우

재귀 함수 호출 수 ⇒ $2^n$
재귀 함수 하나 당 시간복잡도 ⇒ $O(1)$
재귀의 시간 복잡도 ⇒ $O(2^n \times 1)$

동적 프로그래밍 - Dynamic Progamming

Note

주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다.

각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.
이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다.
특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

주로 이전에 했던 계산을 반복하여 풀이하는 최적 부분 구조(Optimal Substructure)의 성능을 향상시키기 위해 사용한다.

최적 부분 구조(Optimal Substructure)인 fibo의 예시

fibo에서 DP를 사용(반복되는 함수의 결과를 memory에 저장하고 재사용)하여 시간복잡도 $O(2^n)$ 에서 $O(n)$으로 감소시킬 수 있다.

DP 구현 방법

코드로 구현할 때, 2가지 방법을 사용하여 구현할 수 있다.

Memoization (top down)
Tabulation (bottom up)

LeetCode의 746. Min Cost Climbing Stairs의 풀이

Memoization 예시

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        len_cost = len(cost)
        mem = {0:cost[0], 1:cost[1]}
        def recurs(idx):
            if idx not in mem:
                mem[idx] = cost[idx] + min(recurs(idx-1), recurs(idx-2))
            return mem[idx]
        return min(recurs(len(cost)-1), recurs(len(cost)-2))

Tabulation 예시

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        len_cost = len(cost)
        mem = {0:cost[0], 1:cost[1]}
        for idx in range(2, len_cost):
            if idx not in mem:
                mem[idx] = cost[idx] + min(mem[idx-1], mem[idx-2])
        return min(mem[len_cost-1], mem[len_cost-2])

백트레킹 - Backtracking

💡 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

글마다 정의가 다른데, 다른 의미로는
탐색 도중 유효하지 않은 해라면, 계산을 이어가지 않고 즉시 다음 해로 넘어가는 기법이라고 하기도 한다.
= 가지치기(Bounded(Promising) function)

상태공간을 트리 구조로 나타낼 수 있을 때 적절하다.

코드 구현 예시

순열

def permutation(nums):
    answer = []

    def backtracking(cur):
        if len(cur) == len(nums):  # base case
            answer.append(cur[:])
            return

        for num in nums:
            if num not in cur:
                cur.append(num)
                backtracking(cur)
                cur.pop()

    backtracking([])
    return answer


print(permutation(nums=[1, 2, 3, 4]))

결과

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

중복순열

def product(nums):
    answer = []

    def backtracking(cur):
        if len(nums) < len(cur): # base case
            return
        else:
            if len(cur) != 0: # 결과로 빈 배열을 제외하고 싶은 경우 해당 조건 추가
                answer.append(cur[:])

        for num in nums:
            cur.append(num)
            backtracking(cur)
            cur.pop()

    backtracking([])
    return answer


print(product(nums=[1, 2, 3, 4]))

결과

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 1, 4], [1, 1, 2], [1, 1, 2, 1], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 2, 4], ... [4, 4, 4, 4]]

조합

def combination(nums, k):
    answer = []

    def backtracking(start, cur):
        if len(cur) == k:  # base case
            answer.append(cur[:])
            return

        for i in range(start, len(nums)):
            cur.append(nums[i])
            backtracking(i + 1, cur)
            cur.pop()

    backtracking(start=0, cur=[])
    return answer


print(combination(nums=[1, 2, 3, 4], k=2))

결과

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

부분집합

def subset(nums):
    answer = []

    def backtracking(start, cur):
        if len(cur) == k:  # base case
            answer.append(cur[:])
            return

        for i in range(start, len(nums)):
            cur.append(nums[i])
            backtracking(i + 1, cur)
            cur.pop()

    for k in range(len(nums)+1):
        backtracking(start=0, cur=[])

    return answer


print(subset(nums=[1, 2, 3, 4]))

결과

[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

설명

cur[:] 사용이유: 값 복사를 위해서 사용, 그냥 cur를 append하면 배열을 참조하기 때문

자세한 설명은 https://blog.encrypted.gg/945 참고

def permutation(nums):
    answer = []

    def backtracking(cur):
        if len(cur) == len(nums):  # base case
            answer.append(cur[:]) # answer에 현재 배열 복사
            return

        for num in nums: # 현재 for문에서 탐색 가능한 노드
            if num not in cur: # 조건에 해당 안되면 가지치기 
                cur.append(num)
                backtracking(cur)
                cur.pop()

    backtracking([])
    return answer

문자열 입력받기

입출력은 input 대신, sys.stdin.readline()를 사용해야 한다. 왜?: [Python] input()과 sys.stdin 참고.

import sys # 라이브러리 임포트

# 문저열 한 줄 입력 받기: 입력으로 받은 문자열에는 개행 문자(`\n`, `\t` 등)가 포함되므로 필요에 따라 제거
line = sys.stdin.readline().strip()

# 정확한게 좋다면 아래처럼 사용
line = sys.stdin.readline().rstrip('\n')


# 정수로 한 줄 받기: 형 변환을 수행하면서 개행 문자는 제거되므로 strip() 사용할 필요 없음
line = int(sys.stdin.readline())

# 문자열 여러 값 입력 받기
values = sys.stdin.readline().split()

# 정수 여러 값 입력 받기
values = list(map(int, sys.stdin.readline().split()))

# 여러 줄 여러 값 입력 받기 1
cnt = int(sys.stdin.readline())
values = [list(sys.stdin.readline().split() for _ in range(cnt))]

# 여러 줄 여러 값 입력 받기 2 - 정수로 받기
cnt = int(sys.stdin.readline())
values = [list(map(int, sys.stdin.readline().split(','))) for _ in range(cnt)]

기타 정보들

10^8을 넘지 않는 N^M 정리

왜 필요한가?

프로그래머스 삼총사 같이 조합(Combination) 문제에서 모든 수를 개산해서 풀 수 있는지 파악하는데 사용할 수 있다. (에시로 든 삼총사는 3^13으로 풀 수 있으므로 모든 경우의 수를 for 구문으로 풀 수 있다.)

2^26
3^16
4^13
5^11
6^10
7^9
8^8
9^8
10^8

YangSiJun528/python_syntax.md

목차