[JAVA]

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 탐색의 경우 BFS 를 사용해야 한다는 것은 아는데... 어떻게 구현해야 할지 몰랐습니다. 우선 Node 클래스를 만들었습니다. 그리고 미로에 해당하는 행렬을 입력받아 maze 변수에 넣어줍니다. 처음 시작하는 노드(* 0,0) 를 생성하고 그 노드에 인접 리스트에 (0,0)에 대해 상, 하, 좌, 우에 1이 있고 방문한 적이 없다면 노드를 추가해주는 방식을 사용했습니다. (* 상, 하, 좌, 우로 움직였을 때 행렬의 in..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제를 보면 첫 번째 줄에 동전 종류의 개수와 맞춰야 하는 돈의 가치를 받을 수 있고, 두 번째 줄부터 N 개의 줄로 각 동전의 가치를 받을 수 있습니다. 이때 동전의 가치는 오름차순으로 주어집니다. 우선 동전의 개수가 가장 적으려면 맞춰야 하는 돈(* K) 에 대해 나눠서 얻을 수 있는 몫이 0보다는 크지만 다른 동전들에 비해 몫이..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이 문제를 풀기 전에 DFS 와 BFS 가 뭔지 몰랐기 때문에 이에 대해 검색먼저 했습니다. 0. 그래프 그래프는 간선과 노드로 이루어진 관계도라고 볼 수 있습니다. DFS 와 BFS 는 이 그래프에서 어떤 노드를 찾는 방법들입니다. 1. DFS DFS, 깊이 우선 탐색은 최대한 깊게 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하며 노드를 찾습니..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제를 보자 사람의 수가 주어지고 각 사람이 인출하는데 걸리는 시간을 다음 줄에 준다. 이때 사람의 순서를 잘 배치하여 각 사람이 돈을 인출하는데 걸리는 시간이 최소가 되는 시간을 계산하면 된다. 각 사람이 인출하는데에 걸리는 시간이 최소가 되려면 어떻게 해야할까? 문제에 주어진 예시를 보자 P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 일 때 최소 시간이 소요되는 순서는 [2, 5, 1, 4, 3] 이..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP 를 안다면 풀 수 있는 문제였다. DP 의 핵심은 이전에 계산했던 것을 다시 활용하는 것이다. 처음에는 DP를 생각하지 못했다. N 의 크기 때문에 N 이 주어졌을 때 가능한 모든 경우의 수를 계산 해보는 식의 방법은 안될 것 같다고 생각했고, 그러면 일종의 알고리즘을 만들어서 해결해봐야겠다고 생각했다. 문제를 보자 임의의 정수 X에 대해 X가 1이 되도록 만드는 최소 횟수를 찾는것이다. 처음에는 간단하게 생각했다. 어떤 수가 나오든 대응할 수 있는 로직을 생각해봤다. 이를 바탕으로 연산의 우선순위를 생각..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 어려웠다. 당연히 재귀함수를 이용하여 풀면 시간초과가 난다. DP 라는걸 처음 알게되었다. 동적 프로그래밍인데, 이 전의 작업을 다시 사용할 수 있을 때 생각해낼 수 있다. 예를 들어 피보나치 수열의 경우 평범한 Recursion 을 이용한다면 수가 많이 커지는 경우 스택 오버플로우가 날 수 있다. 하지만 DP 를 사용한다면 다르다. 피보나치 수열을 점화식으로 나타내면 n=0) F(x) = 0 n=1) F(x) = 1 n>1) F(x) = F(x-1) + F(x-2) 이다. 만약 아주 큰 자연..

https://www.acmicpc.net/problem/25305 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net 정렬을 하는 방법이 이 문제의 핵심이다. 내림차순으로 정렬하고, (상을 받는 사람의 수) - 1 에 해당하는 index 인 값을 출력하면 된다. 하지만 Collections.sort() 의 기본 정렬방식은 오름차순이다. 3가지 방법이 있다. Collections.reverseOrder() 사용하기 Comparator 만들어서 사용하기 람다 함수 이용하기 1. Collections.reverseOrder() 사용하기 import java.io.*; import java..

https://www.acmicpc.net/problem/2587 2587번: 대표값2 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + www.acmicpc.net 평균은 값을 받을 때마다 sum 에 넣어주고 마지막에 /5 를 하면 구해진다. 중간값은 모든 값들을 list 에 담아주고 정렬을 한 다음에 index = 2 인 값을 출력하면 된다. n=5 이니 최악의 경우 O(n^2) 인 정렬 알고리즘도 상관없이 sort 하며 된다. import java.io.*; import java.util.ArrayList; impor..