알고리즘
[백준 - 4179번] 불! - 자바(JAVA) 정리 및 해설
[백준 - 4179번] 불! - 자바(JAVA) 정리 및 해설
2020.07.301. 개요 이 문제는 BFS를 활용하여 빠르게 미로를 탈출하는 문제이다. 특히 불과 함께 사람이 미로를 동시에 탈출하는 문제로써 이것을 어떤식으로 해결하는 가에 따라서 문제가 많이 달라진다. https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리�� www.acmicpc.net 2. 설명 이런 문제에서 결국 중요한 포인트는 "같은 시점에 불과 사람을 동시에 움직이는 것"이 가장 중요하다. 결국 이문제에서 핵심으로 문제를 풀려면 불과 사람이 동시간에 움직이여야 한다는 조건이 붙는다. 그 조건을 만..
[백준 - 1309번] 동물원 - 자바(JAVA) 정리 및 해설
[백준 - 1309번] 동물원 - 자바(JAVA) 정리 및 해설
2020.05.03이번에 풀어볼 문제는 DP문제인 동물원입니다. 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이문제는 오르막수와 비슷한 문제 양상을 띄고 있어서, 비슷한 문제 풀이를 이용했습니다. 이차원배열을 통해서 총 3가지의 경우를 나타냈는데 각각의 의미는 이렇습니다 Dp[n][0] -> 두 개의 방 중에 사자를 아예 넣지 않은 경우 Dp[n][1] -> 두 개의 방 중에 사자를 왼쪽 방에 넣은 경우 Dp[n][2] -> 두 개의 방 중에 사자를 오른쪽 방에 넣은 경우 즉, 이전 방의 경우의 수를 계속 취합해서 더할 수 있는습니다. 문제는 주어져있는 조건 "사자를 넣은 방에는 오른쪽방과 아랫방에는 넣을 수 없다" 라는 조건때문에, 사자를 넣지 않은 경우..
[백준 - 11057번] 오르막 수 - 자바(JAVA) 정리 및 해설
[백준 - 11057번] 오르막 수 - 자바(JAVA) 정리 및 해설
2020.05.03이번에 풀어볼 문제는 DP문제인 오르막 수입니다. 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 이 문제에서 핵심적으로 봐야할 것은 이차원 배열을 통해서 이 문제를 이해하는 방식이라고 생각합니다. 제가 이 문제에서 사용한 방식은 DP[][] 이렇게 있을때 앞의 [] 배열은 N을 뜻하고 뒤의 배열은 [] N에 따라 붙는 한자리 숫자를 뜻합니다. 글로 표현하기가 어려워서 ..
[백준 - 16194번] 카드 구매하기 2 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 10일차
[백준 - 16194번] 카드 구매하기 2 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 10일차
2020.02.2916194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 어떤식으로 접근했는지? 이문제는 카드 구매하기 1에 이어 같은문제인데, 이번에는 최소값을 구하는 게 문제이다. 문제는 최소값을 찾으려면 각 N에 대해서 경우를 다 따져서 확인을 해봐야하는데, 이 최대값의 경우 경우의 수가 1개의 경우만 생기는데, 최소값의 경우 각 경우마다 최소값이 될 경우가 늘어난다고 생각했습니다. 그래서 N의 최소값을 구하기위해서 N-1~ 0 의 최소값을 최대로 더해주고, 부족한 카드를 실제로 남은 걸 더하는 방식으로 모든 카드를 채워 최소값을 만..
[백준 - 2225번] 합분해 - 자바(JAVA) 정리 및 해설 - 1일 1DP 9일차
[백준 - 2225번] 합분해 - 자바(JAVA) 정리 및 해설 - 1일 1DP 9일차
2020.02.272225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 어떤식으로 풀었나? 일단 이문제는 N의 정수를 K개를 가지고 만드는 경우를 찾아야합니다. 가장 쉽게 생각할 경우는 정수 1개를가지고 N을 만드는 경우와 정수 2개를 가지고 N을 만드는 경우인데요. 정수 1개를가지고 N을 만드는 경우는 무슨 정수든간에 1개 정수 2개를 가지고 N을 만드는 경우는 0~N까지 한가지 경우씩 있기때문에 N+1가지가 존재합니다. 이런 N과 K를 동시에 가지고 있어야하기때문에 DP배열을 2차원 배열로 만들어야합니다. 저의 경우 DP[K][N]식으로 배열을 만들어줬습니다. 즉 DP[1][3] 이라면, 3을 만들기위해서 정수 1개가지고 만드는 경우의 수라고 생각하면 됩..
[백준 - 2302번] 극장 좌석 - 자바(JAVA) 정리 & 1일 1DP - 8일차
[백준 - 2302번] 극장 좌석 - 자바(JAVA) 정리 & 1일 1DP - 8일차
2020.02.272302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 어떤식으로 풀었는지? 이번 문제 역시 DP문제이다. 핵심은 결국에 고정된 VIP석을 제외한 나머지 가짓수에 대해서 곱으로 전체 경우를 구한다는 것. 두번째는 Vip좌석을 통해서 남겨진 좌석을 지정된 방법으로 섞었을때 가능한 경우의 수 찾는 것. 완벽하게 이문제를 풀지를 못했고, 이분의 블로그를 많이 참고해서 풀었다 http://blog.naver.com/occidere/220854811310 [백준] 2302 - 극장 좌석 문제 링크 : https://www.acmicpc...
[백준 - 1904번] 01타일 - 자바(JAVA) 정리 및 해설 &1일 1DP- 7일차
[백준 - 1904번] 01타일 - 자바(JAVA) 정리 및 해설 &1일 1DP- 7일차
2020.02.271904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 어떤식으로 풀었는가? 01타일은 동적계획법으로 푸는 문제이다. 01타일의 특이한 점은 n에따른 증가폭이 어디서 본것 같은 모양새로 증가합니다. N = 1일때 1개 (1) N =2 일때 2개 (00, 11..
[백준 - 6359번] 만취한 상범 - 자바(JAVA) 정리 및 해설 & 1일 1DP -6일차
[백준 - 6359번] 만취한 상범 - 자바(JAVA) 정리 및 해설 & 1일 1DP -6일차
2020.02.27안녕하세요. 오늘 풀어 볼 문제는 만취한 상범입니다. 6359번: 만취한 상범 문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고 www.acmicpc.net DP라고 하기에는 애매한 부분이 있긴하지만, 그래도 처음에 풀기에 무난한 문제입니다. 어떤식으로 풀었는지? 방을 int로 만들고 (물론, int로..
[백준 - 1699번] 제곱수의 합 - 자바(JAVA) 정리 & 1일 1 DP - 5일차
[백준 - 1699번] 제곱수의 합 - 자바(JAVA) 정리 & 1일 1 DP - 5일차
2020.02.24안녕하세요 이번에 풀어볼 문제는 제곱수의 합입니다. https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 어떤식으로 풀었었나? 처음에 문제를 풀었을때는 단순하게 N-1의 값 +1 이라고 생..
[백준 - 11727번] 2*N 타일링 2 - 자바(JAVA) 정리 & 1일 1DP - 4 일차
[백준 - 11727번] 2*N 타일링 2 - 자바(JAVA) 정리 & 1일 1DP - 4 일차
2020.02.22안녕하세요. 이번에 풀어볼 문제는 2N 타일링 2입니다. 다이나믹 프로그래밍 문제입니다. 이문제는 참고해서 풀었기 때문에, 코드만 적어 놓도록 하겠습니다. 차후에 다시 한번 더 풀어보고 해설을 올리겠습니다. /** 2020. 2. 22. 오후 8:03:38 * @author ventulus95 */ package codeBaekJoon; import java.io.BufferedReader; import java.io.InputStreamReader; public class No11727_2nTitle { static int cache[] = new int [1001]; public static void main(String[] args) throws Exception { BufferedReader br..
[백준 - 11052번] 카드구매하기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 3일차
[백준 - 11052번] 카드구매하기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 3일차
2020.02.19안녕하세요 오늘 풀어볼 문제는 카드 구매하기입니다. Dynamic Programming 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 개요 이문제에서 가장 중요한 포인트는 "금액의 최대값"을 맞춰줘야하기때문에 각 N개의 카드를 샀을의 금액이 최대가 되는 경우를 찾아야합니다. 즉, 각 경우마다의 카드를 살 수 있는 최대 금액을 찾아서 그 값을 저장을 해야합니다. N 만큼의 카드를 사야한다면, N = N-1개를 샀을때..
[백준 - 1003번] 피보나치 함수 - 자바(JAVA) 정리 및 해설 & 1일 1DP 2일차
[백준 - 1003번] 피보나치 함수 - 자바(JAVA) 정리 및 해설 & 1일 1DP 2일차
2020.02.18오늘 풀어볼 문제는 피보나치 함수입니다. 역시 Dynamic Programming https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 일단 이문제는 특이하게도 알고리즘을 보여주고 시작합니다. 물론 이 알고리즘만 보고 풀수 있는 문제는 아닙니다. ㅋㅋ 어떤 식으로 접근 했는지? 일단 제가 접근했었던 방식은 DP = Top-Down 이렇게 생각하다보니까 탑다운 방식으로 골라서 풀었는데, 그렇게 썩 좋은 방법은 아닌것 같습니다. 일단 첫번째로는 0을가지는 경우와 1를 가지는 경우를 분리해서 했습니다. 두가지 인자를 한 함수에서 동시에 굴리는 방법이 ..