python - PCCP 2,3일차

스타트는 Local에서 시작하게 된다. 후에 Enclose, Global, Built-in 쭉~ 내려가게 된다.

 

강사님의 다음 예시를 통해 스택의 개념으로 확인 할 수 있었다.

0~3까지 입력이 되었다가 if문이 실행되는 수간 쌓여있던 stack에서 하나씩 빠져나오게 된다.

 

재귀 함수의 예시

 

그냥 붙어있을 경우는 list로 띄어줄 수 있다.

 

memo이제이션 원리

 

 

O(N) -> 순차검색

 

log(n)시간 복잡도

이진검색

 

 

2 pointer

 

 

b = copy.deepcopy(a)
깊은 복사

 

전치

인접행렬을 전치하게 되면 유방향 그래프가 전부 반대로 바뀜

zip의 활용

 

* unpacking연산자 활용

 

회전↪️

다음과 같은 3 x 3 이차원 리스트가 있습니다.

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

알고리즘 문제에서 이차원 리스트를 회전시켜야 하는 경우가 많습니다.

먼저 인덱스를 조작하여 이차원 리스트의 회전을 구현할 수 있습니다.

90도 회전

오른쪽으로 90도를 회전시킨 이차원 리스트를 얻는 방법은 아래와 같습니다.

n = 3
rotated_matrix = [[0] * n for _ in range(n)]  # 초기화

for i in range(n):
    for j in range(n):
        rotated_matrix[i][j] = matrix[n-j-1][i]
# rotated_matrix 결과

[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3]
]

회전 시킨 이차원 리스트를 담을 rotated_matrix 변수를 선언하고 모든 원소를 0으로 초기화합니다.

이중 for문을 순회하며, matrix의 (n-j-1)행, i열에 담긴 원소를 rotated_matrix의 i행, j열에 넣습니다.

여기서 1을 빼는 이유는 마지막 행의 번호는 n이 아니라 n-1이기 때문입니다.

반대로 왼쪽으로 90도 회전시킨 이차원 리스트는 어떻게 얻을까요?

n = 3
rotated_matrix = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        rotated_matrix[i][j] = matrix[j][n-i-1]
# rotated_matrix 결과

[
    [3, 6, 9],
    [2, 5, 8],
    [1, 4, 7]
]

전체적인 코드는 거의 비슷하지만, matrix의 인덱스 조작을 어떻게 하느냐만 달라집니다.

내장 함수 zip을 이용한 90도 회전

내장 함수 zip과 리스트 슬라이싱을 활용하면 앞서 했던 90도 회전을 간단하게 구현할 수 있습니다.

기본적인 구조는 zip을 이용한 전치와 비슷합니다. 리스트 슬라이싱이 추가로 붙는 형태입니다.

먼저 오른쪽으로 90도 회전하는 것 부터 알아보겠습니다.

rotated_matrix = list(zip(*matrix[::-1]))
# rotated_matrix 결과

[
    (7, 4, 1),
    (8, 5, 2),
    (9, 6, 3)
]

다음은 왼쪽으로 90도 회전하는 것에 대해 알아보겠습니다.

rotated_matrix = list(zip(*matrix))[::-1]
# rotated_matrix 결과

[
    (3, 6, 9),
    (2, 5, 8),
    (1, 4, 7)
]

리스트 슬라이싱 [::-1]의 의미는 리스트 내부 원소의 순서를 거꾸로(reverse) 뒤집는 것입니다.

[::-1]이 matrix 옆에 있는지, 바깥에 있는지 그 위치에 따라 회전의 방향을 결정할 수 있습니다.

 

델타탐색 (중요)

위 아래 왼쪽 오른쪽 상황 시