분류 전체보기

▶ BufferedReader, 동적 계획법 DP를 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 이번 문제는 동적 계획법의 첫번째 문제입니다. 피보나치 수 알고리즘으로 풀이하면 시간 초과가 발생합니다. 먼저 dp 배열을 long타입 전역변수로 초기화합니다.  main문에서 dp를  입력된 N+1만큼의 크기를 가지도록 초기화를 해줍니다. N+1로 배열을 만드는 이유는 동적 계획법(DP)을 사용하여 피보나치 수열을 계산할 때, 0번째부터 N번째까지의 피보나치 수를 저장할 공간을 확보하기 위해서입니다. 즉, 인덱스를 0부터 N까지 사용하기 위해 배열의 크기를 N+1로 설정하는 것입니다. 그리고 속도를 빠르게 하기 위해서 메모이제이션을 할 수 있도록 상향식 dp_fibo 함수를..

동적 계획법 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 배열..