억지기법과 완전 탐색

억지 기법 ( brute-foce ) 란 ? 

• 매우 광범위한 문제에 적용 가능한 알고리즘 설계 기법 중 하나
• 입력의 크기가 작은 경우 충분히 빠를 수 있고, 점근적으로 더 효율적인 알고리즘 보다 실제 빠른 경우도 존재
• 효율적인 알고리즘 설계와 분석을 위해 이론적 기반이 됨
• 정렬, 탐색, 기하학적 문제, 완전 탐색, 그래프 탐색 등에 사용 가능 

 

[1] brute-force를 사용한 선택 정렬 

: 입력 리스트에서 가장 작은 항목을 매번 루프마다 찾고, 이를 꺼내 정렬된 리스트에 순서대로 삽입한다.

▶ 이를 개선 시키면, 새로운 리스트에 저장하는 것이 아니라 정렬되지 않은 최근 포인트에 접근하여 교환하는 것도 가능 ( 제자리 정렬 ) 

 

 

선택 정렬 알고리즘 

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]
        printSet(A, i+1);

< 복잡도 >
[1] 입력의 크기 :  N ( 리스트 크기 ) 
[2] 기본 연산 : 비교 연산 or 대입 연산
[3] 입력 구성에 따른 차이 : 항상 일정한 횟수의 비교 연산 필요
==> 복잡도 :  [ n(n-1) ] / 2.   : O(n^2)

 

 

 

[2] 순차 탐색 알고리즘 

: brute-force를 사용한 순차 탐색은 key를 list를 순회하면서 찾게 된다. 

 

def seq_search(A, key):
    for i in range(len(A)):
    	if A[i] == key:
        	return i
    return -1

< 복잡도 > 
최선 : O(1)
최악 : O(n)
평균 :  (n+1) / 2 => O(n)

 

 

 

[3] 문자열 매칭 

Q. 길이가 n인 입력 문자열 T와 길이가 m인 패턴 문자열 P가 존재할 때, T에서 가장 먼저 나타나는 P의 위치를 찾아라 

def string_match(T, P):
	n = len(T)
    m = len(P)
    for i in ragne(n-m+1):
    	j = 0
        while j < m and P[j] == T[i+j]:
        	j = j+1
        if j == m :
        	return i
    return -1

<복잡도>
최선의 경우 : O(m).    : 첫 위치에서 매칭 성공 ( 패턴 수 : m )
최악의 경우 : O(mn) 

 

 

 

[4] 최근접 쌍의 거리 

 

 

brute-froce 전략 : 

가능한 모든 점의 쌍 (pi, pj)에 대해 거리를 계산하고, 가장 짧은 것을 찾는다.

 

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

<복잡도>

 

 

 

완전 탐색 

: 순열이나, 조합, 모든 붑분 집합을 찾는 과정을 포함하는 문제에 적용함 

 

 

 

[5] 그래프 탐색 

 

[1] 깊이 우선 탐색 (DFS) 

def dfs(graph, start, visited):
   if start not in visited:
    	visited.add(start)
        print(start, end=' ')
        nbr = graph[start] - visited
        for v in nbr:
        	dfs(graph, v, visited)

정점 수 n , 간선 수 e 인 CASE : 
- 인접 리스트 표현 : O(n+e) --> 회소 그래프에서 유리 
- 인접 행렬 표현 : O(n^2)

 

 

[2] 너비 우선 탐색 (BFS)

파이썬의 Queue 모듈 사용 

import queue
def bfs(graph, start):
    visited = { start } 
    que = queue.Queue()
    que.put(start)
    while not que.empty():
    	v = que.get()
        print(v, end='')
        nbr = graph[v] - visited
        for u in nbr:
            visited.add(u)
            que.put(u)

복잡도
- 인접 리스트 표현 : O(n+e)
- 인접 행렬 표현 : O(n^2)