[알고리즘] 시간복잡도

<리스트에서 요소 꺼내기>

l= [3,5,2,6,1]

#제거하기
l.pop[1]

-> 리스트로 구현 시 시간이 많이 걸리고 비싼 연산임.. n번 계산 하는 알고리즘이다 ( Order n)

리스트 내 요소 개수만큼 탐색하는 시간과 연산이 걸림

 

 

 

 

<큐 활용해서 요소 꺼내기>

from collections import deque

queue= deque([1,2,3])

## 요소삽입
queue.append(5)
# > [1, 2, 3, 5]

## 요소 삭제
queue.popleft()
# > [2, 3, 5]
# > 반환값은 1

## 리스트 처럼 접근도 가능
queue[0]
# > 2
# > 0번째만 가능?

- > 리스트의 pop연산 보다 FIFO(First In First Out) 사용에 더 유용하고 연산 속도나 갯수가 적다.

(deque는 popleft 사용)

코딩테스트나 백준 문제 풀때, 시간에 대해 실행제한이 있다면 사용할 것!

 

 

큐의 자료구조

 

 

 

 

<Graph>
; 자료구조의 일종

정점 (Node, Vertex)

간선 (Edge)                              >> G= ( V, E )

 

 

Graph는 노드와 엣지로 이루어짐 (graph는 노드와 엣지의 set 임)

쉽게 말해 SNS로 표현하면

노드를 사람, 엣지를 사람간의 관계를 나타낸다. 그 관계에는 각각의 가중치가 있다.

 

 

- 단방향 간선

단방향 Graph 가중치가 있음

- 양방향 간선

<그림>

 

인접리스트 : 인접된 노드끼리 리스트화

 

<BFS : Breadth First Search>
; 너비 우선 탐색 (완전탐색 방법)

 

 

백준 1260번

from collections import deque

# 노드, 간선, 시작점
n,m,v= map(int, input().split()

# 인접리스트
graph= [[] for _ in range(n+1)] #1번부터 n번까지의 정점 사용

for i in range(m):
	v1, v2= map(int, input().split())
    graph[v1].append(v2) # 단방향
    graph[v2].append(v1) # 양방향

for i in range(1, n+1):
	graph[i].sort() # 순서 보장을 위해 오름차순 정렬 필요 (백준 1260번의 조건)

def bfs(start):
	queue= deque()
    visited= [0 for _ in range(n+1)]
    queue.append(start)
    visites[start]= 1
    
    # 1 usage
    while len(queue) > 0: # que에 남은게 없을때까지 실행
    	curr= queue[0]
        print(curr, end=' ')
        for nxt in graph[curr]:
    		if visited[nxt] == 0: # 방문안함
        		visited[nxt] = 1  # 방문했다고 표시
                queue.append(nxt)
        queue.popleft() # 선입선출

dfs_sol=0
bfs_sol=0

visit= [0 for _ in range(n+1)]
visit[v]= 1

# 2usage
def dfs(curr):
	print(curr, end=' ')
    
    for nxt in graph[curr]:
    	if visit[nxt] == 0:
        	visit[nxt]= 1
            dfs(nxt)

dfs(v)
print()
bfs(v)

< 그림 >을 보고 이해하면 좋다.

1과 인접한 visited 이 0이면 갈수 있음 >> 큐에 PUSH

인접한 노드의 visited이 0인지 1인지 확인후 방문하지 않은것만 큐에 넣음 (0: 방문안함, 1: 방문함)

모두 visited의 상태가 1이어서 방문할 곳이 없으면 큐에서 POP

 

큐에서 나오는 순서대로 순서 배열?에 저장 (여기서는 그냥 print 한건가)

큐가 EMPTY일 경우 탐색 종료한다

 

 

dfs는 도착여부를 알고 싶을때( 목적지에 도착할 수 있을지 없을지) 사람이 미로에서 이동하듯이!

bfs 최소비용탐색

dfs는 스택구조(LIFO), bfs는 큐 구조(FIFO)