뚝딱 뚝딱 개발일기

https://www.acmicpc.net/problem/3190문제'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다..

https://www.acmicpc.net/problem/1427 간단하지만 중요한 기본문제 해당 문제는 int 배열을 만들어 오름차순 정렬을 하면된다.물론 int 배열을 내림차순정렬하여 거꾸로 출력하는 방법도 있지만  오름차순 정렬를 하는 법을 활용해보겠다. 방법 1. 오름차순 직접 구현import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;class Main{ // 소트인사이드 백준 - 1427 public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new ..

0-1 KnapSack Problem대표적인 DP 문제 알고리즘 중 하나로 알려져 있다. DP 란, 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다.최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.처음에는 Brute Force 로 접근하였지만 시간 복잡도가 2 ^n 으로  시간 초과가 날것이 분명했다.DP 문제를 풀기 위해서는 '최적의 원리' (Principle of Optimality) 가 성립하는지를 확인해야 하는데,최적의 원리는 다음과 같다. "어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면.그 문제는 대하여 최적의 원리가 성립한다" 평범한 배낭 문제도 적용해 보자집합 A 를 n 개의 물..