요즘 알고리즘과 프로그래밍언어 같이 공부하기 글과 같이 백준온라인의 '단계별로 풀어보기'를 통해 문제를 풀고 있습니다.

그 중 '별찍기 11 - 2448'에 대한 풀이 입니다.


주어진 라인수만큼 별을 찍는 문제인데요 라인수 N은 3, 6, 12, 24, 48, ... 와 같이 3*2^k (k <=10) 입니다.

N = 3 일 때, 아래와 같이 프린트해야하며 아래 삼각형이 기본 단위가 되겠습니다.

***
**** 
*****


N = 6 일 때,

******                        
***** *                       
********                      
*********                     
**********                    
***********


N = 12 일 때,

************                        
*********** *                       
**************                      
***************                     
****************                    
*****************
******************
***** *********** *
********************
*********************
**********************
***********************


요런 식인데요, 잘 보면 규칙성이 있습니다.

다음 단계 삼각형은 현 단계 삼각형 두 개가 아래에 위치하 것과 같은 모양이 됩니다.

그래서 저는 다음과 같이 문제를 풀었습니다.

"현 단계 삼각형 두 개를 만들어서 뒤에 붙이고 현 단계 삼각형을 오른쪽으로 민다."


N = 6 일 때,

1. 현 단계 삼각형

***
**** 
*****

2. 현 단계 삼각형 두 개를 만들어서 뒤에 붙인다

***                        
** *                       
*****                      
*********                     
**********                    
***********

3. 현 단계 삼각형을 오른쪽으로 민다.

******                        
***** *                       
********                      
*********                     
**********                    
***********


위의 3번에서 "현 단계 삼각형을 오른쪽으로 민다"고 했는데요,

그렇다면 '오른쪽으로 얼마나 밀어야하는가?'가 문제입니다.

요것도 규칙이 있습니다.

기본적으로 아래와 같이 삼각형을 갖고 있다면,

***
**** 
*****

N = 3 일 때, 0칸

N = 6 일 때, 3칸

N = 12 일 때, 6칸

...

N = 3 × 2^k 이므로, 오른쪽으로 미는 칸 수는 바로 3 × 2^(k - 1)가 되겠습니다. 아래와 같은 수식으로 k를 구할 수 있습니다.

log₂(N ÷ 3) = log₂(3 × 2^k ÷ 3) = log₂2^k = k


구현은 파이썬 언어를 사용했습니다.

저는 기본 삼각형을 아래와 같이 1차원 배열로 선언하고

s = ["  *   ", " * *  ", "***** "] #삼각형 사이에 빈 칸 하나 있음을 고려


다음 단계 삼각형을 만드는 함수를 아래와 같이 선언했습니다.

def makeStar(shift):
    c = len(s)
    for i in range(c):
        s.append(s[i] + s[i]) #현 단계 삼각형을 뒤에 붙이고
        s[i] = ("   " * shift + s[i] + "   " * shift) #현 단계 삼각형을 오른쪽으로 민다

전체 소스코드 입니다.


저작자표시 비영리 변경금지

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


P, NP-Hard, NP-Complete

저작자표시 비영리 변경금지

N-Queens Problem

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

4-Queens Problem의 상태공간트리


깊이우선검색(DFS)

  • 깊이우선검색(Depth First Search)을 사용하면 해답을 찾을 수 있다. 그러나 이 방법을 사용하면 해답이 될 가능성이 전혀 없는 노드의 후손(descendant) 노드까지 검색하기 때문에 비요율적이다. 위 그림에서 보면, 첫 번째 퀸이 (1, 1)에 놓일 경우 두 번째 퀸은 (2, 1)에  놓일 수 없으므로 (2, 1)의 후손노드는 검색할 필요가 없다.


노드의 유망성(Promising)

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


되추적(Backtracking)

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


가지치기(Pruning)

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

4-Queens Problem의 되추적 상태공간트리


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


자세한 내용은 여기로

저작자표시 비영리 변경금지

재귀 호출

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


꼬리재귀

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

자세한 내용은 여기로


저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바