Python-Algorithm 기본 스킬

김상윤·2022년 8월 17일

Algorithm

목록 보기

16/19

핵심 정리 1

arr = [[0]*5 for _ in range(5)]
a, b = [int(x) for x in input().split()]
graph = [[int(x) for x in input()] for _ in range(n)]

s.split()
"".join(l)

a = set()
a = set([1, 2, 3, 3])
a = set()
a.add(1)
a.discard(x)
a.remove(x) # 없으면 error

d = {}
d["c"] = 3              # 추가
d["c"] = 10             # 갱신
d["a"]
d.get("a")
d.pop("a")
del d["b"]
for k, v in d.items():
sorted(d.items(), key=lambda x: x[1], reverse=True) # list 리턴 [(k, v), ...]

# from itertools import permutations, combinations
# l = ['a', 'b', 'c']
# nCr = list(combinations(l,2))
# print(nCr)

import heapq
seq = [7, 2, 9, 4, 1, 5, 6, 8, 3]
pq = []
for x in seq:
    heapq.heappush(pq, x)
pq = seq[:]
heapq.heapify(pq)
# 최대힙 내림차순
pq = []
for num in nums:
  heapq.heappush(pq, (-num, num))
while heap:
  print(heapq.heappop(pq)[1])

from collections import deque
que = deque()
que2 = deque([1, 2, 3])
que2.popleft()

from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
n, m, start = [int(x) for x in input().split()]
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)            # 무방향일 때
for i in range(1, n + 1):
    graph[i].sort()               # 방문 순서 고정(필요 시)
def dfs(start: int):
    visited = [False] * (n + 1)
    order = []
    def rec(u):
        visited[u] = True
        order.append(u)
        for w in graph[u]:
            if not visited[w]:
                rec(w)
    rec(start)
    return order
def bfs(start: int):
    visited = [False] * (n + 1)
    q = deque([start])
    visited[start] = True
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for w in graph[u]:
            if not visited[w]:
                visited[w] = True
                q.append(w)
    return order
print(*dfs(start))
print(*bfs(start))

def binary_search(target, arr):
    arr.sort()
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] > target:
            right = mid -1
        else:
            left = mid + 1
    return -1

입출력

정수 입력 받기

#list로 받기
a = [int(x) for x in input().split()]
# 정수 세 개 입력 시, 각각 int type으로 입력 받기
a, b, c = [int(x) for x in input().split()]

2차원 배열 입력 받기 (graph, map)

공백없는 정수 (2차원 배열) 여러개 입력 받기 (int)

5
01010
11100
11010
00001
10110

n = int(input())
graph = [[int(x) for x in input()] for _ in range(n)]

input() → '01010'
for x in input() → '0', '1', '0', '1', '0'
결과: [0, 1, 0, 1, 0]

공백 있는 정수 (2차원 배열) 여러개 입력 받기 (int)

5
0 1 0 1 0
1 1 1 0 0
1 1 0 1 0
0 0 0 0 1
1 0 1 1 0

n = int(input())
graph = [[int(x) for x in input().split()] for _ in range(n)]

input() → '0 1 0 1 0'
.split() → ['0', '1', '0', '1', '0']
결과: [0, 1, 0, 1, 0]

공백없이 문자열 입력받아서 모든 글자 하나하나 element로 (char)

map = []
for i in range(n):
  l = list(input())
  map.append(l)

개행 없이 출력

print(i, end=' ') 
//출력 후 개행하지 않고 띄어쓰기

list 모든 elements 공백과 함께 출력

l = [1, 3, 5]
print(*l) 
# 1 3 5

print(f"k : {k}")

f"...{}..."
: {}중괄호 안에 변수 넣어서 문자열 중간중간에 변수 값 넣을 수 있다.

2차원 list 생성

배열 내 elements 복제 생성은 '*' 연산으로
배열 낸 배열 복제 2차원 배열 생성은 for in range()로

arr1 = [[] for i in range(5)]
# [[], [], [], [], []]
arr2 = [0]*5
# [0, 0, 0, 0, 0]
arr3 = [0 for _ in range(5)]
# [0, 0, 0, 0, 0]
arr4 = [[0] for _ in range(5)]
# [[0], [0], [0], [0], [0]]
arr5 = [[0]*5 for _ in range(5)]
# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
arr6 = [[0 for _ in range(5)] for _ in range(5)]
# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

'*' 연산으로 배열 복사 시 얕은 복사로 인해 값 변동이 공유된다.

l = [[]] * 5
print(l)
l[2].append(1)
print(l)
# [[], [], [], [], []]
# [[1], [1], [1], [1], [1]]

문자열

정리 : https://velog.io/@sangyun/%EB%AC%B8%EC%9E%90%EC%97%B4

set

list에 비해, in / remove() 등 탐색 연산에서 연산의 효율이 좋다. 시간복잡도를 줄일 수 있다.

삽입, 삭제

set.add(a)
: element a 추가
: O(1)
set.update([a,b,c])
: 여러개의 elemenents(a,b,c) 추가
set.remove(a)
: element a 삭제 (a 없을 시 error 발생)
: O(1)
set.discard(a)
: element a 삭제 (a 없어도 error 발생X)
: O(1)

포함관계

a in set
: element a가 set에 존재한다면 True 리턴
: O(1)
set1 <= set2
: set1이 set2의 부분집합이라면 True 리턴
: set1.issubset(set2)

연산

교집합
: set1 & set2
합집합
: set1 | set2
차집합
: set1 - set2

heapq (priority queue)

정리 : https://velog.io/@sangyun/Priority-Queue

import heapq
pq = []
heapq.heappush(pq, (a,b))
heapq.heappop(pq)

deque - BFS

deque에는 popleft() 함수가 있기 때문에, FIFO 진행에 유리하다.

from collections import deque
que = deque()
que2 = deque([1, 2, 3])
que2.popleft()
print(que2) # deque([2, 3])

수행시간 비교
https://velog.io/@gyhan/Python-Deque.popleft%EB%8A%94-%EC%99%9C-%EB%B9%A0%EB%A5%B8%EA%B0%80

비트 마스킹

표현

bin(a)
10진수 -> 2진수
0bxxxx
: 2진수로 값 할당
int("s", 2)
: 2진수 표현 문자열을 정수로 변환

a = bin(13)
# '0b1101'
a = 0b11010
# 13
a = int('1101', 2)
# 13

연산

& : AND
둘 다 1일때 1 반환 (교집합)
| : OR
하나만 1이어도 1 반환 (합집합)
^ : XOR
서로 다를 때 1 반환
~ : NOT
뒤집기

연산 활용 - 비트마스크

A & X
: X의 1인 bit만 A에서 뽑아내기
: X의 0인 bit를 A에서 제거
- A & B == A
  : A가 B의 부분집합
n번째 bit 1로 설정 (2^n 자리_0번째부터 시작)
: bit 추가

b |= (1 << n)

n번째 bit 0으로 설정
: bit 삭제

S &= ~(1 << n)

최대값, 최소값

변수 초기화를 위해 최대값, 최소값을 사용해야 하는 경우가 있다.
ex. 최소값을 구하기 위해 초기값 정수의 최대값으로 설정

# 10억 이내 범위에서 최대값, 최소값
INF = int(1e9)
INF = int(-1e9)
# int범위 내 최대값
INF = int(2e9)

comination, permutation

permutaion
: 순열
- nPr
- 순서를 고려하여 r개 줄 세우기

from itertools import permutations

arr = ['A', 'B', 'C']
nPr = permutations(arr, 2)
print(list(nPr))

# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

combination
: 조합
- nCr
- 순서 상관 없이 n개 중 r개 뽑기

from itertools import combinations

arr = ['A', 'B', 'C']
nCr = combinations(arr, 2)
print(list(nCr))

# [('A', 'B'), ('A', 'C'), ('B', 'C')]

재귀 제한 해제

sys.setrecursionlimit( )

python은 기본적으로 재귀의 최대깊이가 낮게 제한되어 있다.
sys.setrecursionlimit( ) 를 통해 재귀 최대 깊이를 설정 할 수 있다.
재귀 문제에서는 필수적으로 선언해준다고 생각하면 된다.
pypy에서는 sys.setrecursionlimit( ) 사용 시 메모리 초과가 발생한다.

import sys
sys.setrecursionlimit(10 ** 6)

referenced

김상윤

이전 포스트

[BOJ-2293] 동전1

다음 포스트

Python-Algorithm 기본 스킬

Algorithm

핵심 정리 1

입출력

정수 입력 받기

2차원 배열 입력 받기 (graph, map)

개행 없이 출력

list 모든 elements 공백과 함께 출력

print(f"k : {k}")

2차원 list 생성

문자열

set

삽입, 삭제

포함관계

연산

heapq (priority queue)

deque - BFS

비트 마스킹

표현

연산

연산 활용 - 비트마스크

최대값, 최소값

comination, permutation

재귀 제한 해제

sys.setrecursionlimit( )

referenced

[BOJ-2293] 동전1

BFS, DFS

0개의 댓글