억지 기법과 완전 탐색

선택 정렬

• 억지 기법에서의 전략
• 정렬이 안된 리스트에서 최솟값이 선택되면 이 값을 새로운 리스트에 저장하는 것이 아니라 첫 번째 요소와 교환한다.
• 어떤 정렬 알고리즘이 입력 리스트 이외에 추가적인 메모리를 사용하지 않으면 "제자리(In-place) 정렬"이라고 부른다.
• 선택 정렬의 장점
• 알고리즘이 간단하고, 입력자료의 구성과 상관없이 자료 이동 횟수가 결정된다는 장점
• 입력의 크기가 크지 않은 실제 문제에 충분히 사용 가능
• 선택 정렬의 단점
• 다른 정렬 알고리즘에 비해 효율적이지도 않고, 안정성을 만족하지도 않음
• Python Code

  data = [5,3,8,4,9,1,6,2,7]
  
  def printStep(arr, val):
      print(" Step %2d  = " % val, end='')
      print(arr)
  
  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);
  
  print ("Original : ", data)
  selection_sort(data)
  print("Selection : ", data)

• 복잡도 분석
• 선택 정렬의 시간 복잡도는 O(n^2)

순차 탐색

• 컴퓨터에서 탐색은 가장 많이 사용되는 작업 중 하나임
• 탐색은 주어진 항목들 중에서 "탐색키"라 불리는 원하는 값을 가진 항목을 찾는 것
• 억지 기법에서의 전략
• 입력 리스트의 첫 항목부터 순서대로 하나씩 탐색키와 비교하는 순차 탐색(Sequential Search) 또는 선형 탐색(Linear Search)
• 순차 탐색의 장점
• 리스트가 정렬되어 있지 않다면 이 방법 외에 별다른 대안이 없음
• 가장 직접적인인 탐색 알고리즘으로 간단하고 구현하기 쉬움
• 순차 탐색의 단점
• 효율적이지 않음
• Python code

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

• 복잡도 분석
• 최선의 경우
• 리스트의 첫 번째 항목이 Key인 경우, 한번의 비교만으로 탐색이 종료됨.
• O(1)
• 최악의 경우
• 찾고자 하는 숫자가 리스트에 없거나 맨 뒤에 있는 경우로 모든 항목을 검사해야 함
• O(n)

문자열 매칭

• 원하는 키워드나 문자열을 찾고 싶은 경우
• 억지 기법에서의 전략
• 텍스트의 첫 번째 문자 위치에 패턴을 놓고 비교한다. 이 과정을 패턴을 오른쪽으로 한 칸씩 옮기면서 성공한 매칭이 나타날 때까지 반복한다.
• Python code

  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 = j+1
      if j==m:
          return i
  return -1

• 복잡도 분석
• 입력의 크기는 텍스트의 길이 n과 패턴의 길이 m
• 최선의 경우
• 텍스트 T의 맨 앞의 문자열이 패턴 P와 일치하는 경우
• 패턴의 길이인 m번만 비교하면 문자열 매칭이 종료 되므로, O(m)이다
• 최악의 경우
• 텍스트의 길이 n만큼 움직이고 패턴의 길이 m만큼 모든 문자마다 비교하게 되므로 O(nm)이다

최근접 쌍의 거리(Closest-pair)

• 억지 기법에서의 전략
• 가능한 모든 점의 쌍에 대해 거리를 계산하고, 가장 짧은 것을 찾는다
• 유클리드 거리
• 두 점 사이의 거리를 계산하는 공식
  유클리드 거리
• Python code

  def closest_pair(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

• 복잡도 분석
• 입력의 크기는 전체 점의 수 n
  기본 연산은 유클리드 거리 계산 문장인 (distance(p[i], p[j]))
• 시간 복잡도는 O(n^2)

완전 탐색(Exhaustive Search)

• 완전 탐색은 가능한 모든 경우의 수를 탐색하는 것
• 모든 경우의 수를 탐색하기 때문에 오래 걸리지만, 절대 답이 틀릴 일이 없다
• 외판원 문제(Traveling Saleman Problem, TSP)
• TSP는 가중치 그래프에서 가능한 모든 해밀토니안 사이클중에서 경로의 합이 최소인 사이클의 경로의 합을 구하는 것
• 해밀토니안 사이클
• 그래프 G=(V,E)가 주어졌을 때, G의 임의의 한 정점에서 출발하여 다른 모든 정점을 한번씩만 방문하고 다시 시작 정점으로 돌아오는 경로
  해밀토니안 사이클
• 억지 기법에서의 전략
• 임의의 한점을 출발점으로 잡고 아직 가보지 않은 모든 이웃 정점으로 계속 이동하면서 검사
• 복잡도 분석
• 완전 탐색 기법은 순열(또는 조합, 부분 집합) 객체들을 생성하는 과정이 필요한 경우가 많아서 복잡도가 매우 높음
  ex)TSP에서 도시의 수가 n이라면 O(n!)가 됨
  순열과 조합
• 0-1 배낭 채우기 문제(Knapsack Problem)
• 배낭의 용량을 초과하지 않으면서 배낭에 들어있는 물건들의 가치의 합이 최대가 되도록 물건들을 선택하는 문제
• 억지 기법에서의 전략
• n개의 물건의 집합에 대한 모든 부분집합을 만들어 보고, 부분집합중에서 무게 합이 배낭 용량을 넘지 않으면서 가치가 최대인 것을 찾는 방법
• 복잡도 분석
• 원소의 개수가 n인 집합의 부분 집합의 수는 2^n이므로, O(2^n)이다

일 배정 문제(Job Assignment Problem)

• 비용을 최소화하는 방법으로 모든 근로자에게 하나씩 일을 배정하는 방법을 찾는 문제
  각각의 근로자는 모든 일을 다 처리할수 있지만 일마다의 비용을 다름
• 복잡도 분석
• 순열 문제이므로, O(n!)

그래프 탐색

• 그래프 탐색, 또는 순회는 하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하는 작업
• 그래프 순회에 완전 탐색의 개념을 적용하면 모든 정점을 체계적으로 방문 할 수 잇는 두 가지 방법을 얻을 수 있음
• 깊이 우선 탐색(Depth First Search, DFS)
• 스택을 이용한 미로 탐색과 유사
• 미로 탐색할 때 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 되돌아와서 다른 방향을 다시 탐색하는 전략
• Python code

  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인 그래프인 경우 인접리스트로 표현한다면 O(n+e)이다
• 정점의 수에 비해 간선의 수가 매우 적은 희소 그래프의 경우엔 인접행렬이 유리할 것으로 예상 할 수 있음
  인접행렬과 인접리스트
• 너비 우선 탐색(Breadth First Search, BFS)
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 가까운 거리에 있는 정점들을 차례로 저장하고 들어간 순서대로 꺼낼 수 있는 큐(Queue)구조가 적합함
• Python code

  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)

• 복잡도 분석
• 너비 우선 탐색은 거리가 0인 시작 정점으로부터 거리가 1인 모든 정점, 2인 모든 정점 등의 순서대로 모든 정점을 방문하는 것
• 인접 리스트로 표현할 경우 O(n+e)이고, 인접 행렬로 표현할 경우 O(n^2)