![]()
그리디 알고리즘이란❓ 그리디 알고리즘이란 greedy라는 이름의 뜻에서 알 수 있듯이 탐욕스러운, 욕심스러운 알고리즘입니다. 탐욕이라는 뜻처럼 그리디 알고리즘(탐욕 알고리즘)은 각 단계에서 가장 최선의 선택을 하는 방법을 말합니다. 다음 그림을 보면 한눈에 알 수 있습니다. 위 그림을 보면 가장 큰 수를 탐색하는 과정을 greedy 알고리즘과 일반적으로 탐색하는 과정을 보여줍니다. 가장 큰 수를 찾기 위해 앞으로 간다면 제일 큰 수가 있는 "99"과 연결되어 있는 3 ➡️ 99 을 생각할 것입니다. 하지만 Greedy 알고리즘은 시작부터 3과 12 두 수중 가장 큰 수인 "12"을 탐색하고 그다음 큰 수인 "6"을 탐색합니다. 이 처럼 그리드는 최종결과에서의 최적의 해가 아닌 "현재상황에서 최적의 해"..
![]()
▶ BufferedReader & StringTokenizer &ArrayList를 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 이번 문제는 정말 간단한 N의 약수를 구하고 그 약수들 중에서 K번째 요소를 출력하는 문제입니다. N의 약수들을 미리 알지 못하기 때문에 보통의 배열을 사용하려면 다른 작업이 필요합니다. 따라서 Java에서는 동적 배열을 사용하려면 ArrayList를 사용해야 하기 때문에 ArrayList로 풀어봤습니다. 먼저 빠른 입력을 위하여 BufferedReader 클래스를 사용하여 입력을 받아주고, 정수형으로 캐스팅합니다. 그리고 ArrayList를 만들어주고 반복문을 사용하여 N의 약수를 구하고, 해당 약수를 ArrayList인 list에 추가해줍..
![]()
▶ BufferedReader를 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 이번 문제는 단순 구현문제입니다. 주어진 입력값 a, b에 대해서 역순으로 다시 정렬해야 합니다. 빠른 입력을 위해서 BufferedReader 클래스를 사용하고, StringTokenizer 클래스를 사용하여 입력값 a, b를 분리를 해줍니다. 그리고 배열을 각 바구니 숫자대로 초기화를 해주고, M번의 구간을 역순으로 뒤집어야 합니다. 이때 a와 b에 -1을 한 이유는 인덱스의 시작이 0이기 때문입니다. while (a 위 조건은 두 인덱스 a와 b가 교차하지 않았을 때까지 반복문을 실행하겠다는 의미입니다.배열의 구간을 뒤집기 위해서 a와 b를 인덱스로 지정하고, a를 증가, b를 감소시키면..
![]()
▶ BufferedReader, 동적 계획법 DP를 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 이번 문제는 동적 계획법의 첫번째 문제입니다. 피보나치 수 알고리즘으로 풀이하면 시간 초과가 발생합니다. 먼저 dp 배열을 long타입 전역변수로 초기화합니다. main문에서 dp를 입력된 N+1만큼의 크기를 가지도록 초기화를 해줍니다. N+1로 배열을 만드는 이유는 동적 계획법(DP)을 사용하여 피보나치 수열을 계산할 때, 0번째부터 N번째까지의 피보나치 수를 저장할 공간을 확보하기 위해서입니다. 즉, 인덱스를 0부터 N까지 사용하기 위해 배열의 크기를 N+1로 설정하는 것입니다. 그리고 속도를 빠르게 하기 위해서 메모이제이션을 할 수 있도록 상향식 dp_fibo 함수를..
