[Python] 알고리즘 - 완전탐색

억지기법

문제의 정의를 바탕으로 한 가장 직접적인 방법

예) 최대공약수 방법, a^n구하는 알고리즘 등...

 

억지기법의 중요성 : 쉬운문제 어렵게 풀필요없다, 광범위하게 문제적용가능, 실제로 더 빠를수도, 이론적인 기반이 된다

정렬, 탐색, 기하학적문제, 완전탐색, 그래프탐색

 

선택정렬

- 정렬문제에 대한 가장 직접적인 해결방법

- 입력리스트에서 가장 작은 항목을 찾고 이것을 꺼내 정렬된 리스트에 순서대로 저장한다(입력된 리스트와 같은 크기의 리스트 1개를 추가 필요로함)

 

* 제자리 정렬을 위한 알고리즘 개선

-> 정렬이 안된 리스트에서 최솟값이 선택되면 이 값을 새로운 리스트가 아닌 첫 번째 요소와 교환한다.

-> n-1번 반복(n번쨰는 자동으로 큰 값이니까!)

def selection_sort(A):
	n = len(A)
    for i in range(n-1):
    	least = i
        for j in range(i+1, n):
        	if A[j] < A[least]:
            	least = j
        A[i], A[least] = A[least], A[i]
        printStep(A, i+1)

복잡도 : O(n^)

기본연산 추가되어도 복잡도 같다 = 반복문에서는 그래서 거의 1개로 본다

 

순차탐색

- 리스트에 n개의 항목이 들어있다. 이 리스트에서 "탐색키"를 가진 항목을 찾아라, 만약 찾는 항목이 있으면 그 항목의 인덱스를 반환, 없으면 -1을 반환. 단 리스트의 항목들은 정렬되어있지않음

* 억지 기법 탐색 전략

: 순차탐색(순서대로) 또는 선형 탐색

#순차탐색
def sequential_search(A,key):
	for i in range(len(A)):
    	if A[i] == key:
        	return i
    return -1

복잡도 : 입력의 구성에 따라 다름

최선 : T(n) = 1 , O(1)

최악 : T(n) = n, O(n)

평균 : T(n) = (n+1) / 2 , O(n)

-> 리스트의 모든 숫자가 골고루 한 번씩 key로 사용되는 경우를 가정

 

문자열 매칭

- 길이가 n인 입력 문자열 T와 길이가 m인 패턴 문자열 P가 있다. T에서 가장 먼저 나타나는 P의 위치를 찾아라. 패턴 없으면 -1반환해라

* 억지기법 문자열 매칭 전략 : 텍스트의 첫 번째 문자위치에 패턴을 놓고 비교한다. 이 과정을 패턴을 오른쪽으로 한 칸씩 옮기면서 성공한 매칭이 나타날 때까지 반복한다. 

def string_matching(T,P):
	n = len(T)
   	 m = len(P)
    for i in range(n-m+1):
    	j = 0
        while j < m and P[j]==T[i+j]:  #j가 m보다 작고 패턴문자열의 문자가 텍스트랑 같을때
        	j = j + 1
        if j == m:
        	return i
    return -1

복잡도 분석

최선 : 첫번째 위치에서 매칭 성공 => O(m)

최악 : 매 위치에서 m번 비교

 

최근접 쌍의거리

def closet(p):
	n = len(p)
    mindist = float("inf")
    for i in range(n-1):
    	for j in range(i+1, n):
        dist = distance(p[i], p[j])
        if dist < mindist:
        	mindist = dist
    return mindist

유클리드 거리 사용

유클리드 거리 공식

복잡도 : O(n^2)

 

완전탐색

순열이나 조합 또는 모든 부분 집합을 찾는 과정을 포함하는 문제들이 많음

예) 틱택토 게임, 외판원 문제(해밀토니안 사이클)

*

TSP완전 탐색

(해밀토니안 사이클이란 그래프가 주어졌을 때 임의의 한 정점에서 출발하여 다른 모든 정점을 한번씩만 방문하고 다시 시작 정점으로 돌아오는 경로를 뜻한다.)

- 그래프가 N개의 정점을 갖는 완전 그래프라면 모든 해밀토니안 사이클은 (N-1)!개가 된다. 

- 완전 탐색은 상태공간 트리의 모든 단말노드를 검사하여 길이가 최소인것을 선택하는 전략

복잡도 = O(n!)

 

배낭채우기 문제

복잡도 O(2^n)

일 배정 문제

복잡도 O(n!)

그래프의 순회

-보다 직관적으로 그래프를 표현하자! : 인접리스트(집합) or 딕셔너리 사용

 

-깊이우선탐색DFS

1. 정점을 순회할 때 stack에 정점을 넣어준다.

2. 스택의 맨 위에 있는 정점의 인근 정점 중 방문하지 않은 (아무) 하나를 순회한다. 

def dfs(graph, start, visited):
	if start not in visited:    #만약 visited에 start가 없으면 = 초기
    	visited.add(start)		#visited에 start넣어주기
        print(start, end = ' ')	
        nbr = graph[start]-visited 
        for v in nbr:
        	dfs(graph,v,visited)

복잡도

-인접리스트 표현: O(n+e)

-행렬표현: O(n^2)

ex) mygraph = { "A": ["B", "C"],

                          "B": ["D", "C","E"],

                          "C": ["E", "D"],

                          "D": ["B", "E"],

                          "E": ["B", "C"] }

 

-너비우선탐색BFS

1.  Queue에서 정점을 뽑아서 정점을 순회한다

2. 해당 정점을 순회 후에 해당 정점의 인접 정점 중 방문하지 않은 정점을 모두 큐에 넣어준다(순서무관)

import queue
def bfs(graph, start):
	visited = {start}   #start들어가있는 방문한 정점 딕셔너리
    que = queue.Queue() #큐 만든다
    que.put(start) #큐에 시작정점 넣기
    whlie not que.empty(): #큐가 빈 것이 아닐동안 반복
    		v = que.get()  # 큐에서 가져오기(먼저들어간것 먼저빼내기)
            print(v,end=' ') 
            nbr = graph[v] - visited #nbr은 그래프에 있는 정점과 인접한 정점리스트에서 방문한 정점뺀 나머지
            for u in nbr:      #나머지 v의 정점들 순회할동안
            	visited.add(u)  #방문딕셔너리에 넣기 
                que.put(u)      # 큐에 넣기

정점의 수 = 리스트의 갯수

간선의 수 = 리스트의 길이

ex) mygraph = { "A": ["B", "C"],

                          "B": ["D", "C","E"],

                          "C": ["E", "D"],

                          "D": ["B", "E"],

                          "E": ["B", "C"] }

복잡도

-인접리스트 표현 : O(n+e)

- 인접행렬표현 : O(n^2)