반응형 전체 글123 백준 1904번 : 01타일 java 이 문제는 규칙을 찾아서 점화식을 만들어 푸는 다이나믹 프로그래밍 문제입니다. 이 문제에서는 N이 1일 때 1개, 2일 때 2개, 3일 때 3개 4일 때 5개 이런 식으로 만들 수 있습니다. 이때 찾을 수 있는 점화식은 오른쪽의 식과 같습니다. 이러한 규칙으로 늘어나는 것은 피보나치 수열의 형태와 같습니다. 따라서 저는 이러한 형태가 되도록 코드를 구현했습니다. import java.io.*; public class Main { static int[] dp; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N .. 2022. 6. 5. 백준 12851번 : 숨바꼭질 2 java 이 문제는 가장 빠른 시간으로 동생을 찾을 수 있는 시간과 이렇게 찾는 방법이 몇 가지인지를 찾는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 중복을 허용해주어야 한다는 것입니다. 5에서 17로 갈 때는 아래와 같이 중복이 없을 수도 있습니다. 하지만 1에서 4로 갈 때를 살펴보겠습니다. 다음과 같이 같은 칸으로 같이 시간이 걸려서 갈 때도 있기 때문에 중복을 허용해 주어야 합니다. 따라서 우리는 중복을 허용해주면서 더 이상 queue에 값을 넣지 않는 상황을 설정해주어야 합니다. 중복을 허용해 주지 않는 상황들을 아래에 나열하도록 하겠습니다. 1. 도착 지점의 시간값이 지금 노드의 시간 값보다 작을 때 bfs를 사용하여 위 문제를 풀 때 모든 간선의 가중치가 같기 때문에 다음 노드로 나아갈 때 .. 2022. 6. 4. 백준 15663번 : N과 M (9) java 이 문제는 dfs를 이용한 백트래킹 문제입니다. 이 문제를 풀 때 유의해야 하는 것은 중복되는 입력이 있을 수 있고 중복되는 수열을 여러 번 출력하면 안 된다는 것입니다. 코드를 보면서 설명 드리겠습니다. import java.io.*; import java.util.*; public class Main { static int[] numArr; static int[] out; static boolean[] visited; static int M; static int N; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));.. 2022. 6. 3. 백준 13549번 : 숨바꼭질 3 java 이 문에는 *2 +1 -1로 이동하면서 bfs에 노드들을 삽입하면서 문제를 해결하면 됩니다. 이때 유의하셔야 하는 점은 *로 가는 연산을 먼저 해야 연산 횟수를 줄일 수 있기 때문에 이 연산을 먼저 해야 한다는 것입니다. 또한 같은 자리에 나중에 도착하게 되더라도 *2할 때 걸리는 시간이 0이기 때문에 더 적은 시간으로 올 수도 있습니다. 따라서 min 변수를 Math.min으로 초기화하면서 저장해야 합니다. 이를 그림으로 설명드리겠습니다. 위의 그림과 같이 1 2 3 4이라는 수가 있습니다. 이를 +1연산으로만 채워보겠습니다. 그럼 각 자리까지 가는 시간은 위의 그림과 같습니다. 이제 *2연산을 더해보도록 하겠습니다. 1에서 시간한다고 할 때 2까지는 순간이동이니 시간이 들지 않고 4도 마찬가지입니다... 2022. 6. 3. 백준 11404번 : 플로이드 java 이 문제는 플로이드-워셜 알고리즘을 푸는 문제입니다. 문제를 풀 때 주의해야하는 점은 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다는 것입니다. 노선을 입력받아서 그 비용이 더 적은지를 비교한 후에 넣어야합니다. 플로이드 워셜 알고리즘은 각 정점으로부터 다른 정점까지 갈 때 거쳐가는 정점을 추가하면서 진행하는 알고리즘입니다. 코드를 보며 추가로 설명드리겠습니다. import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.i.. 2022. 6. 2. 백준 9251번 : LCS java 이 문제는 LCS(Longest Common Subsequence) 알고리즘입니다. 이 알고리즘을 위 문제의 예제 입력을 통해 설명드리겠습니다. 주어진 입력들을 받아서 다음과 같이 표로 나타냅니다. 각 셀은 이 구간까지 탐색했을 때 겹치는 subsequence가 얼마나 있느냐입니다. 예를 들어 (2, 3)에 들어가 있는 수는 CA와 ACA가 얼마나 겹치는가입니다. 이 규칙대로 위의 표를 채워보겠습니다. C 하나와 비교했을 때 2번 column의 C의 subsequence가 되니 그 이후는 전후 1입니다. CA와 비교할 때 A만 있을 때는 subsequence가 A이지만 ACA와 CA를 비교하면 CA가 겹치니 2가 됩니다. 마찬가지로 CAP가 겹치니 3까지 나옵니다. CAPC는 위의 문자열과 겹치지 않으므.. 2022. 6. 2. 백준 16953번 : A → B java 이 문제는 bfs를 이용하여 A가 조건에 맞게 바뀔 때 B로 가장 적은 연산으로 바뀌는 연산의 수를 구하는 문제입니다. 바로 코드를 보여드리겠습니다. import java.util.*; import java.io.*; public class Main{ static int B; static boolean get; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int A = Integer.parseInt(st.nextT.. 2022. 6. 1. 백준 12865번 : 평범한 배낭 java 이 문제는 knapsack problem이라는 최적화 조합을 찾는 다이나믹 프로그래밍 문제입니다. 이 문제에서는 들 수 있는 무게가 정해져 있을 때 가장 가치합이 큰 값을 찾아내는 문제입니다. 저는 이 문제를 풀 때 특정한 무게에 따라서 각각의 물건들을 들 수 있는지를 따져가며 풀었습니다. 예제 1번을 통해서 그림과 같이 제가 이 문제를 푼 방식에 대해서 설명드리겠습니다. 예제 1번에서는 무게를 7kg까지 들 수 있고 물건이 4개가 주어진다고 하였기 때문에 다음과 같이 표를 그렸습니다. 무게가 0일 때는 아무것도 들 수 없고 물품이 0일 때는 아무 물건도 챙길 수 없다는 의미입니다. 따라서 무게가 0일 때와 물품이 0일 때의 셀에는 가치합이 0이 됩니다. 이제 각각의 무게에서 그 번호의 물품을 들 수 있.. 2022. 6. 1. 이전 1 ··· 10 11 12 13 14 15 16 다음 반응형
