게으른 엔지니어

NP-Hard와 NP-Complete의 차이가 무엇인지 잘 이해가 가지 않았으나 포함관계를 보니까 알겠다.

P, NP-Hard, NP-Complete

N-Queens Problem

• N×N의 체스판에 N개의 퀸이 서로 위협하지 않도록(Path가 겹치지 않도록) 위치시키는 문제

노드의 유망성(Promising)

• 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다(non-promising)고 하고, 그렇지 않으면 유망하다(promising)고 한다.
• 위의 DFS에서 (2, 1)의 후손 노드는 non-promising하다.

되추적(Backtracking)

• 어떤 노드의 유망성을 검사하여 유망하지 않다고 판정되면 후손 노드(서브트리)들에 대한 검색을 중지하고(Pruning), 그 노드의 부모노드로 돌아가서 다른 후손 노드에 대해 검색을 수행한다.

가지치기(Pruning)

• 유망하지 않은 노드에 대에 진행을 하지 않는 것을 말한다.

DFS VS Backtracking

• 검색하는 노드 개수
• DFS = 155 개 (전체 (1+4+16+64+256)개 중 155번째에서 솔루션을 찾게 됨)
• Backtracking = 27 개

되추적 알고리즘의 개선

• 유망성 여부에 대한 확인을 노드 방문 전에 실시

Java 소스코드

분석은 나중에...

public class NQueens {
  private static final int N = 4;
  private static int[] b = new int[N];
  private static int s = 0;
 
  static boolean unsafe(int y) {
    int x = b[y];
    for (int i = 1; i <= y; i++) {
      int t = b[y - i];
      if (t == x ||
          t == x - i ||
          t == x + i) {
        return true;
      }
    }
 
    return false;
  }
 
  public static void putboard() {
    System.out.println("\n\nSolution " + (++s));
    for (int y = 0; y < N; y++) {
      for (int x = 0; x < N; x++) {
        System.out.print((b[y] == x) ? "|Q" : "|_");
      }
      System.out.println("|");
    }
  }
 
  public static void main(String[] args) {
    int y = 0;
    b[0] = -1;
    while (y >= 0) {
      do {
        b[y]++;
      } while ((b[y] < N) && unsafe(y));
      if (b[y] < N) {
        if (y < N - 1) {
          b[++y] = -1;
        } else {
          putboard();
        }
      } else {
        y--;
      }
    }
  }
}

삽입 정렬이란?

• 순차적으로 값을 읽어서 현재 값 이전에 위치한 정렬되어 있는 값들의 적절한 곳으로 삽입하는 정렬이다.
• 현재 값 이전에 위치한 값들은 이미 정렬되어 있으므로, 현재 값이 직전 값보다 크다면 삽입이 일어나지 않는다.
• 성능
• O(n²)
• 정렬되어 있을 수록 성능이 좋다.
• 이미 정렬 되어 있을 경우(최선의 경우) 비교 횟수 : N - 1
• 역순일 경우(최악의 경우) 비교 횟수 : N(N – 1)/2

자세한 내용은 여기로

재귀 호출

• 함수가 호출되면 함수가 호출된 장소를 가리키는 주소값이 시스템 내부의 스택에 저장됨
  (호출된 함수의 작업을 끝마치고 리턴될 때 되돌아갈 위치를 기억)
• 재귀적으로 호출된 함수가 리턴될 때 함수를 호출했던 원래 자리로 되돌아와야 하는 이유
• 원래 함수에서 재귀적으로 함수를 호출한 부분 다음에 다른 내용이 포함되어 있으면 그 내용을 계속해서 처리해야 하기 때문 
• 내부 스택을 이용해서 함수가 호출된 지점을 정확하게 기억해야 하기 때문에 메모리의 사용이나 프로그램의 처리 속도 면에서 추가적인 부하가 있음

꼬리재귀

• 성능과 간결함, 이 두가지 방법의 장점을 모두 취함
• 원래 위치로 돌아갔을 때 할일이 남아있지 않기 때문에 함수가 호출된 위치를 기억해 둘 필요가 없음
• 똑똑한 컴파일러는 꼬리재귀를 인식하여 최적화를 해줌