파이썬

알고리즘/Python

파이썬

Hexs 2023. 4. 14. 14:50

입력

# 공백으로 입력받는법.

import sys

time = list(map(int, input().split()))
time = list(map(int, sys.stdin.readline().split()))

BPS, DFS 탐색

rom collections import deque


def dfs(start):
    visit[start] = True
    print(start, end=" ")

    for i in lst[start]:
        if not visit[i]:
            dfs(i)


def bfs(start):
    queue = deque([start])
    visit[start] = True
    while queue:

        v = queue.popleft()
        print(v, end=" ")
        for i in lst[v]:
            if not visit[i]:
                visit[i] = True
                queue.append(i)


N, M, V = map(int, input().split())
lst = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

for i in lst:
    i.sort()

visit = [False] * (N + 1)
dfs(V)
print()

visit = [False] * (N + 1)
bfs(V)

배열 초기화

lst = [0 for i in range(N)]

딕셔너리

# 딕셔너리 쌍 추가.

a = {1: 'a'}
a[2] = 'b'
a
{1: 'a', 2: 'b'}

# 딕셔너리 삭제

del a[1]
a
{2: 'b', 'name': 'pey', 3: [1, 2, 3]}

시간 복잡도

리스트

len(a)		전체 요소의 개수를 리턴한다.
a[i]		인덱스 의 요소를 가져온다.
a[i:j]		부터 까지 슬라이스의 길이만큼 개의 요소를 가져온다. 이 경우 객체 개에 대한 조회가 필요하므로 이다.
elem in a		elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 만큼 시간이 소요된다.
a.count(elem)		elem 요소의 개수를 리턴한다.
a.index(elem)		elem 요소의 인덱스를 리턴한다.
a.append(elem)		리스트 마지막에 elem 요소를 추가한다.
a.pop()		리스트 마지막 요소를 추출한다. 스택의 연산이다.
a.pop(0)		리스트 첫번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체 복사가 필요하므로 이다.
del a[i]		i에 따라 다르다. 최악의 경우 이다.
a.sort()		정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 에도 실행될 수 있다.
min(a), max(a)		최솟값/최댓값을 계산하기 위해서는 전체를 선형탐색해야 한다.
a.reverse()		뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다.

딕셔너리

len(a)		요소의 개수를 리턴한다.
a[key]		키를 조회하여 값을 리턴한다.
a[key] = value		키/값을 삽입한다.
key in a		딕셔너리에 키가 존재하는지 확인한다

저작자표시 비영리 변경금지