평범한 배낭이지만 절대 평범하지가 않다. 알고 보니 배낭 문제 (knapssack problem)로 Dynamic Programming의 대표적인 문제라고 한다. Knapsack Algorithm이라고도 불리는 배낭 문제는 두 가지 문제로 분류된다. 짐을 쪼갤 수 있는 경우와, 짐을 쪼갤 수 없는 경우이다. 전자는 Fraction Knapsack Problem이라고 하고, Greedy를 사용한다.

🔗 문제 링크

🔎 문제 풀이

평범한 배낭이지만 절대 평범하지가 않다. 

알고 보니 배낭 문제 (knapsack problem)로 Dynamic Programming의 대표적인 문제라고 한다.

Knapsack Algorithm이라고도 불리는 배낭 문제는 두 가지 문제로 분류된다.

짐을 쪼갤 수 있는 경우와, 짐을 쪼갤 수 없는 경우이다.

전자는 Fraction Knapsack Problem이라고 하고,  Greedy를 사용한다.

후자는 0/1 Knapsack Problem이라고 하고, 보통 DP를 사용한다.

나무위키와 블로그를 참고해서 배낭 문제에 대해 이해했다.

이 문제는 짐을 쪼갤 수 없는 경우이므로 DP로 푼다.

아래 블로그에 나오는 테이블 그림을 참고하면 이해하는데 도움이 된다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] dp = new int[N + 1][K + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());

            for (int j = 1; j <= K; j++) {
                if (j < W) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                dp[i][j] = Math.max(V + dp[i - 1][j - W], dp[i - 1][j]);
            }
        }

        System.out.println(dp[N][K]);
    }
}

🔗 문제 링크

N-Queen

🔎 문제 풀이

백준 'N과 M' 4문제를 통해 백트래킹 원리를 조금 이해하게 되었고 ,, 그 유명한 (?) N-Queen 문제를 도전했다.

퀸은 가로, 세로, 대각선으로 이동할 수 있다.

즉, 퀸을 서로 공격할 수 없게 놓기 위해서는 퀸 위치의 가로, 세로, 대각선에 또 다른 퀸이 존재하면 안 된다는 것이다.

퀸 위치 좌표는 배열을 통해 저장한다.

처음에는 x, y 좌표가 떠올라 2차원 배열로 놓았는데

풀다가 어려워서 찾아보니 1차원 배열로 해결하더라 ,,!

나 빼고 다 천재가 틀림이 없다 ,,

배열의 index를 열로 두고, 해당 index의 값을 행으로 두면 되는 것이다 ,,,! 

그럼 같은 행에 위치하거나 대각선에 위치하는지에 대해서만 검사하면 된다.

퀸을 놓을 수 있다면 depth에 1을 증가시켜 재귀 함수를 호출시키고,

depth == N이라면 문제 조건에 맞는 경우의 수를 찾은 것이므로 count를 1 증가한다.

그리고 count를 출력하면 된다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
        
public class Main {
	static int N;
	static int[] queenPlace;
	static int count = 0;
    
	public static void main(String[] args) throws IOException {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	N = Integer.parseInt(br.readLine());
    	queenPlace = new int[N];
    	findNQueen(0);	
    	System.out.println(count);
    }
    
	
    public static void findNQueen(int depth) {
    	if (depth == N) {
    		count++;
    		return;
    	}
    	
    	for (int i = 0; i < N; i++) {
    		queenPlace[depth] = i;
    		
    		if (getPossibillity(depth)) {
        		findNQueen(depth+1);
        	}
    	}
   
    }
    
    public static boolean getPossibillity(int column) {
    	for (int i = 0; i < column; i++) {
    		if (queenPlace[column] == queenPlace[i])
    			return false;
    		
    		if (Math.abs(column - i) == Math.abs(queenPlace[column] - queenPlace[i]))
    			return false;
    	}
    	
    	return true;
    }
}

Reference

🔗 문제 링크

하노이 탑 이동순서

🔎 문제 풀이

어릴 때 엄청 좋아했던 추억의 하노이 탑 ! ! 

하노이 탑은 재귀를 활용하여 풀 수 있는 유명한 예제 중 하나라고 한다.

출력해야 하는 값은 두 가지이다.

첫째 줄에 옮긴 횟수 K, 두 번째 줄부터 수행 과정을 출력하면 된다.

하노이 원반 수가 홀수이면 제일 작은 맨 위 원반을 맨 오른쪽 장대에 옮기면서 시작하고, 짝수이면 중간 장대에 옮기면서 시작한 기억이 있어서 그런 식으로 접근했는데, 전혀 관계없는 무의미한 접근이었다 ,,^^

위키백과에 보면 하노이 탑 알고리즘이 설명되어있다.

원판이 n개 일 때, 옮긴 횟수는 " 2의 n제곱 - 1 " 이다.

이러한 수를 메르센 수(Mersenne number)라고 부른다고도 한다.

하노이 탑을 옮기는 수행 과정은 재귀 호출을 통해 구현할 수 있다.

출력은 StringBuilder를 활용하였다.

Key Point

🔑재귀 함수를 활용한다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static StringBuilder result = new StringBuilder(); 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		// 옮긴 횟수
		
		int movingCount = (int)Math.pow(2, N) - 1;
		result.append(movingCount + "\n");
		
		// 하노이 원반을 옮기는 수행 과정
		
		moveHanoiDisk(N, 1, 2, 3);
		
		System.out.print(result);
		
	}
	
	static void moveHanoiDisk(int N, int startingPoint, int mid, int destination) {
		
		if (N == 1) {
			result.append(startingPoint + " " + destination + "\n");
			return;
		}
		
		moveHanoiDisk(N-1, startingPoint, destination, mid);
		result.append(startingPoint + " " + destination + "\n");
		moveHanoiDisk(N-1, mid, startingPoint, destination);
		
	}
}

+

뭔가 100% 이해하지 못해서 찜찜했는데, 자기 전에 우연히 이 영상을 발견했다 !

설명을 너무 잘 해주신다 ! 

최고다 !

🔗 문제 링크

별 찍기 - 10

🔎 문제 풀이

재귀 문제이다. 처음에 예제가 한 눈에 잘 들어오지 않아서 캡처해서 그림판으로 그려보니 별을 찍는 방법은 쉽게 이해가 갔다. 다음은 크기 27의 패턴이다.

크기 3의 패턴(= 분홍색 정사각형)은 가운데를 제외한 모든 칸에 별이 하나씩 있다.

크기 9의 패턴(= 보라색 정사각형)은 크기 3의 패턴이 가운데를 제외한 모든 칸에 있다.

크기 27의 패턴(= 노란색 정사각형)은 크기 9의 패턴이 가운데를 제외한 모든 칸에 있다.

2차원 배열을 활용하고, boolean 변수를 이용해 공백인지 아닌지 구분하여 별 또는 공백을 자기 자리에 넣어주면 되겠다는 생각을 했다. 뭔가 N을 N/3으로 더 이상 쪼갤 수 없을 때까지 재귀 함수를 계속 호출해서 별을 찍는 느낌은 알겠는데 막상 코드를 짜려니 막막했다 ,, 별을 찍는 재귀 함수의 파라미터를 입력값 N만 두고 생각했는데, 풀이를 찾아보니 2차원 배열의 인덱스이자 별의 위치인 x, y와 공백인지 구분하는 boolean 변수도 파라미터로 둔 것을 보고 힌트를 얻었다.

메인 함수에서 별을 찍을 때에는 StringBuilder를 활용해 한 번에 출력했다. 

찾아보니 StringBuilder 보다는 BufferedWriter가 출력이 많은 경우 성능이 더 좋은 편이라고 한다.

Key Point

🔑 재귀 함수를 활용한다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static char[][] stars;
	static int N;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		stars = new char[N][N];
		
		drawStar(0, 0, N, false);
		
		StringBuilder result = new StringBuilder();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				result.append(stars[i][j]);
			}
			result.append('\n');
		}
		
		System.out.println(result);
		
	}
	
	public static void drawStar(int x, int y, int N, boolean blank) {
		
		if (blank) { // 공백인 경우
			for (int i = x; i < x+N; i++) {
				for (int j = y; j < y+N; j++) {
					stars[i][j] = ' ';
				}
			}
			return;
		}
		
		if (N == 1) { // 더 이상 쪼갤 수 없는 경우
			stars[x][y] = '*';
			return;
		}
		
		int size = N / 3;
		int count = 0;
		
		for (int i = x; i < x+N; i += size) {
			for (int j = y; j < y+N; j += size) {
				count++;
				if (count == 5) drawStar(i, j, size, true);
				else drawStar(i, j, size, false);
			}
		}
	
	}
}