분류 전체보기

동적 계획법 DP란❓  동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다.  주로 줄여서 DP라고 많이 말하며, 주어진 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 동일한 문제가 나왔을 시 저장해둔 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 기법입니다. 위 말을 기준으로 핵심을 뽑아보자면 다음과 같습니다.하나의 큰 문제를 여러 개의 작은 문제로 나누어 결과 저장동일 결과 재사용 DP 문제 성립 조건동적 계획법(DP)는 두 가지 주요 원리인 "최적 구분 구조"와 "중복되는 하위 문제"를 기반으로 합니다. 최적 부분 구조(Optimal Substructure)문제의 최적 해가 하위 문제의 최적 해로 구성되는 ..

▶ BufferedReader, StringTokenizer을 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 문제 자체는 어렵지 않지만 로직을 구성하는 과정이 쉽지 않았습니다. 입력이 주어질 때 해당 날짜에 대한 요일을 구하는 문제입니다. 먼저 빠른 입력을 위해 BufferedReader 클래스를 사용하여 입력을 받아주고, 입력된 날짜를 공백을 기준으로 분리할 수 있도록 StringTokenizer 클래스를 사용하여 분리를 해주었습니다. 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. 문제에서 나왔듯이 위 조건에 따라서 날짜와 요일을 배열로 초기화를 해줍니다. 24번째 줄에서 입력된 "월"..

▶ BufferedReader, StringTokenizer을 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 문제 자체는 간단한데 풀이를 하다가 실수한 부분이 있어 정리할 겸 포스팅을 하게 되었습니다. 입력이 주어질 때 입력이 asending 오름차순, desecending 내림차순으로 입력되었는지 판별하는 문제입니다. 빠른 입력을 위해 BufferedReader 클래스를 사용하여 입력을 받아주고, 오름차순과 내림차순을 판단할 길이 8의 배열 arr을 만들어줍니다. 13,14번째 줄에서 asending과 desecending을 true로 초기화해줘야 합니다. 그 이유는 밑에서 설명하겠습니다. 16번째 줄에서 각 요소를 정수형으로 캐스팅하여 저장해 주고, 이후에 arr 배열..

▶ BufferedReader, StringTokenizer, 유클리드 호제법을 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 이번 문제는 간단하게 최대공약수와 최소공배수를 구현할 수 있는지 알아보는 문제입니다. 최소 공배수를 구하기 위해선 최대 공약수를 먼저 구해야 합니다. 최대 공약수를 구하기 위하여 gcd() 함수를 선언해주고, 유클리드 호제법으로 구현했습니다. 먼저 유클리드 호제법을 사용하기 위해선 큰 값과 작은 값을 구해줘야 합니다. Math클래스의 min()과 max() 메소드를 사용하여 구해줍니다. 유클리드 호제법은 나머지가 0이기 전 값을 반환해야 하기 때문에 일 때 큰 값을 반환해 주도록 if문으로 분기처리 해줬습니다. 만약에 0을 구하지 못했으면 다시 제..