2020/02
[백준 - 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를 가지는 경우를 분리해서 했습니다. 두가지 인자를 한 함수에서 동시에 굴리는 방법이 ..
[백준 - 1010번] 다리 놓기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 1일차
[백준 - 1010번] 다리 놓기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 1일차
2020.02.18안녕하세요. 오늘 풀어볼문제는 백준 다리 놓기입니다. 이 문제는 다이나믹 프로그래밍 혹은 조합으로 문제를 푸는 문제입니다. https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 일단 이문제에서 결국 포인트로 잡아야하는 부분은 얼만큼 최대한 많은 여러가지의 경우의 수를 체크할 수 있냐라는 포인트입니다. 예시를 들어서 설명해보겠습니다. 한점에서 3점으로 만들 수 있는 경우의 수는 3가지입니다. 근데 저희가 문제가 되는 것은 N개의 점일때 M개의 점을 따..
1일 1DP를 시작해보겠습니다.
1일 1DP를 시작해보겠습니다.
2020.02.18최근들어서 알고리즘 공부를 좀 멀리한 경향도 있고, 다시 어느정도의 감을 잡기위해서는 DP 문제의 사고력이 필요하다고 느꼈습니다. 실제로 여러 코딩테스트를 준비하기에는 DP문제의 난이도가 적당하다고 생각했습니다. DP문제들을 빠르게 풀어가면서, 하루에 하나씩 DP문제를 풀어 보는 시간을 가지도록 하겠습니다. 물론 완벽하게 1일 1DP를 지킬 수 있을지는 조금의 의문이 드는 건 사실이지만 최대한 노력해서 많은 문제를 풀어보고 싶네요.
[Spring boot] 공공데이터 포털 service key is not registered error 해결 방안
[Spring boot] 공공데이터 포털 service key is not registered error 해결 방안
2020.02.11최근 공공데이터 포털에서 Bus앱을 만들기위해서 API키값을 불러와야하는 상황이 있었다 . 현재 개발중인 프로젝트 Spring boot로 계속적으로 API를 읽고 Parsing하기에 편한 내부 함수를 RestTemplate를 활용해서 그 Json값을 바로 파싱 받으려했었다. 문제는 service key is not registered error 가 지속적으로 발생했다는 점이다. 나는 이 오류가 도대체 왜? 발생하는지 정확한 이유를 알 수가 없어서, 분명히 String값에서 바뀔리는 없다고 문제점을 엄한 곳에서 찾기 시작했는데... 일단 문제를 재대로 파악해보자 실제로 Data.or.kr를 가서 확인해보면 대부분 Q&A 관련 사이트나 혹은 service key is not registered error라는..