Development Palette

1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net 1. 이전좌표와 현재좌표의 길이의 차이로 판단하여 nightTour 하는 방법 package com.구현.b1331_나이트투어; import java.util.Scanner; public class Main2 { static int[][] map = new int[6][6]; static int beforeR = 0; static int beforeC = 0; public static void main(String[] args) { Scanner sc = new S..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net package com.BFS.b2206_벽부수고이동하기; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenize..

11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제의 범위는 1

를 구하는 방법은 nCk이다. nCk를 구하기 위해 파스칼의 삼각형을 이용할 수 있다. 파스칼의 삼각형(Pascal's triangle)은 수학에서 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것이다. 파스칼의 삼각형 파스칼의 삼각형 파스칼의 삼각형이란 자연수를 삼각형 모양으로 배열한 것을 말해.이는 원래 중국인에 의해 만들어졌으나 프랑스의 수학자 파스칼(1623~1662)이 체계적인 이론을 만들고 그 속에 terms.naver.com 파스칼의 삼각형의 규칙을 이용하면 nCk = (n-1Ck-1) + (n-1Ck) 주의할점 : k=0, n = k 일 때 경우의 수는 항상 1이다 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 경우의 수 식 구하기 지문 개수 : 사용되는 문자 종류의 수인 M, 비밀번호의 수 : N 찍힌 지문은 비밀번호에 전부 사용해야한다. 그렇기 때문에 중복순열 M^N (M가지수를 N개 뽑는 경우의 수)에서 전부 다 사용 하지 않는 경우는 빼줘야한다. 예를 들어 M=3, N=4일 때 찍힌 지문을 전부 사용하는 경우 (3^4)에서 두가지를 사용하는 경우를 먼저 뺀다고 생각했을 때 3C2 * 2^4인데 이 식은 한가지만 사용하는 경우도 포함 되어 있다. 다시 말하자면 전부 사용하는 경우 (3^4)에서 2가지만 사용하는 경우 (3C2 * 2^4)를 빼는데,,, 이..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 0/1 Knapsack 문제를 그대로 적용할 수 있는 조합 문제! 저번에 그냥 조합으로 풀었을 때 1개의 케이스만 맞고 실패했었는데 드디어 풀었다,, package com.DP.s5215_햄버거다이어트; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; // 0/1Knapsack 으로 풀 수 있는 문제 //민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때..

담을 수 있는 무게가 정해져 있는 가방(Knapsack)에 쪼갤 수 없는 짐을 담지 않거나 담았을 때 (0/1) 최적의 가치를 찾는 알고리즘 배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다. 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부르고, 동적계획법(Dynamic Programming)으로 풀 수 있다. 참고로, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem)라 부르고, 그리디 알고리즘으로 풀 수 있다. 배낭 문제 - 위키백과, 우리 모두의 백과사전 배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단하..

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지 퍼져나가는 부분을 인접한 4방향으로만 퍼져나가게만 하면 되는데 공기청정기 조건을 생각하다가 잘못접근해서 시간이 오래걸렸다 나는 공기청정기 바람 방향에 따라 일일이 for문 돌려줬지만 공기청정기 위,아래를 중심으로 map을 두개로 나눠서 푸는 방법도 있다 package b17144_미세먼지안녕; //공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. //공기청정기의 바람에 의해 미세먼지가 모두 한 칸씩 이동한다. //공기청정기로 들어간..