저작권상 문제를 올릴 수 없으므로 이코테 서적을 통해 확인 바람 문제 풀이 최단 거리라고 해서 바로 다익스트라, 플로이드 워셜 알고리즘을 생각하기 쉽지만 훨씬 더 효율적으로 풀 수 있는 방법이 존재한다. 바로 bfs를 이용하는 것이다. bfs를 이용할 수 있는 조건이 존재한다. 바로 모든 도로의 거리가 일정한 경우에만 사용할 수 있다. 그렇다면 왜 bfs일까? 물론 dfs를 통해서도 최단 거리를 구할 수 있다. 하지만 비효율적이다. 예시를 들어보자 A / \ B---C 다음과 같은 그래프가 존재하고 A를 시작으로 dfs를 진행해보자. 먼저 dfs 과정을 살펴보자 우선 A -> B -> C 순서로 진행이 되며 이때 B에 대해서는 비용1로 최단경로가 성립되지만 C은 2로 최단 경로가 아니다. 우리는 C의 최..

풀이 화폐의 단위의 큰 단위가 작은 단위의 배수임을 보장 받을 수 있을 경우 그리드 알고리즘을 통해 큰 단위부터 차근차근 갯수를 세면 된다. 하지만 이 문제는 입력받는 화폐의 단위가 배수임을 보장 받을 수 없어 그리디 알고리즘을 적용하지 못하고 dp를 이용해야 한다. 작은 단위부터 갯수를 적용시켜 나가며 큰 단위로 만들 수 있는 화폐의 개수를 줄여 나간다. 바로 코드를 작성해보자 코드 package 이코테.기출분석.DP; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public c..

문제 풀이 보통 이런 문제 처럼 처음부터 끝가지 참조하며 현재 참조하고 있는 부분을 포함해야 할지 말아야 할지 결정해서 원하는 조건을 충족하려면 이전 값들을 알아야 한다. 하지만 그 길이가 길면 길 수록 이전 값들을 계속 계산해야 한다. 따라서 성능상 이전 값들의 연산 결과를 저장하여 보관해두면 바로 꺼내 쓸 수 있어 효율적이다. 이 문제도 마찬가지이다. 0과 1번 인덱스에 한해서는 바로 값을 지정해두고 반복문을 통해 max(이전 값, 2번째 전 값+현재 값)을 통해 더 큰 값을 택한다 위 로직을 코드로 작성해보자. 코드 package 이코테.기출분석.DP; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr..

문제 풀이 해당 문제는 dp를 통해 쉽게 구할 수 있다. 30를 1로 만드는 경우의 수를 생각해보자 30은 주어진 a b c d 연산을 모두 수행할 수 있다. 즉, 다음 4과정에서의 최솟 값을 구하는 것과 같다. A: 30 = 29를 1로 만드는 연산 횟수 + 1 (+1을 하는 연산) B: 30 = 6을 1로 만드는 연산 횟수 + 1 (*5를 하는 연산) C: 30 = 10을 1로 만드는 연산 횟수 + 1 (*3을 하는 연산) D: 30 = 15를 1로 만드는 연산 횟수 + 1 (*2를 하는 연산) 이를 수식으로 표현하면 min(A, B, C, D)+1 과 같이 나온다. 그럼 여기서 B가 선택되었다고 가정해보자. B에서 6을 을 1로 만드는 연산 횟수는 어떻게 구할까? 똑같이 6을 +1, *5, *3, ..

문제 풀이 여러 개의 떡이 주어지고 절단기의 높이에 따라 손님이 가져가는 떡의 길이가 달라진다. 따라서 공식처럼 뚝딱 나오는 것이 아니라 하나씩 증가 (혹은 감소) 시키면서 원하는 값의 크기를 찾아야 한다. 즉 원하는 값의 크기를 찾는다 -> 검색을 이용한다는 뜻이다. 여기서 중요한 점은 입력 조건을 잘 확인해야 한다는 것이다. 정확히 계산은 어렵겠지만 딱 봐도 수가 크다. 그럼 단순한 시간 복잡도로는 나올 수 없다. 즉, 효율적인 검색을 사용해야 한다는 것이다. 바로 코드를 살펴보자. 코드 package 이코테.기출분석.이진탐색; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo..