본문 바로가기

Algorithm

 (41)
[Java] BOJ13410_거꾸로 구구단 www.acmicpc.net/problem/13410 13410번: 거꾸로 구구단 일반적인 구구단에서 가장 큰 수는 마지막 항의 값이 제일 크다. 거꾸로 구구단에서는, 각 항에 구구단의 계산 결과로 나온 값을 뒤집어 저장을 한다. 이렇게 하면 가장 큰 값이 항상 마지막이 www.acmicpc.net 단순 브루트 포스 문제이다. 기존 구구단 값을 구하고 문자열로 바꿔주어 뒤집어주고 다시 int로 바꿔 비교해서 최댓값을 찾아냈다. import java.io.*; import java.util.StringTokenizer; public class Bj13410 { public static void main(String[] args) throws IOException { BufferedReader br = ne..
[Java] BOJ13164_행복 유치원 www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 정렬이 되어 있는 데이터에서 최소를 뽑으려 하는 점에서 그리디를 유추했다. 구하고자 하는 값이 키 차이의 최소이기 때문에 연속된 두 학생의 키 차이를 구해 N-1 크기의 배열을 만들었다. 이 배열에서 작은 키차이를 골라야 하기 때문에 정렬을 하였다. 이제 이 키 차이 중 몇개를 골라내야 하는지 알아야 한다. 예제의 경우 이런 식으로 나누어지고 [3, 5], [6, 10]의 키 차이가 제외..
[Java] BOJ12015_가장 긴 증가하는 부분 수열 2 www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 최장 증가 부분 수열 문제이다. 하지만 N의 범위가 크기 때문에 단순 이중 반복문으로는 해결이 되지 않는다. 이 경우에는 이분 탐색을 사용해야 한다. dp 배열에는 최장 증가 부분 수열을 이루는 요소가 담긴다. 하지만 주의할 점은 이 요소들이 항상 최장 부분 수열이라는 것을 보장하지는 않는다. 그저 개수만 맞을 뿐이다. 정확한 요소를 골라내기 위해서는 다른 방법을 사용해야 한다. 하지만 이 문제는 개수만 구하면..
[Java] BOJ1197_최소 스패닝 트리 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 제목 그대로 최소 스패닝 트리(MST)를 구하는 문제이다. MST 알고리즘에는 대표적으로 Prim과 Kruskal 알고리즘이 있다. Prim 알고리즘은 V^2의 시간 복잡도, Kruskal은 ElogE의 시간 복잡도를 가진다. 하지만 Prim알고리즘을 우선순위 큐를 이용하여 구현할 시 ElogV의 시간 복잡도로 이 문제에서 가장 빠르게 해결할 수 있다. 가중치..
[Java] BOJ15961_회전초밥 www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 꽤나 시간이 빡빡한 문제이다. 초밥을 선택할 때 중복되는 부분이 많으므로, 예제 1의 경우 위와 같이 탐색을 할 것이다. 이런 방법을 슬라이딩 윈도우라고 한다. 회전초밥 테이블이 원형이기 때문에 '25' 같은 경우 앞에 있는 [7, 9, 7]과 연결되어 탐색해야 한다. 따라서 탐색을 더 쉽게 하기 위해 앞에서부터 K-1개의 값들을 배열에 더 추가해줬다. 최종적으로 배..
[Java] BOJ2239_스도쿠 www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 모든 경우를 다 따지면 최악의 경우 9^81 횟수가 나온다. 따라서 가지치기를 해줘야 하는 문제이다. 매번 반복문을 돌아서 값이 0인것을 찾기보다는 0인 애들의 index를 리스트에 담아두고 list로 반복문을 돌리는 게 유리하다. "답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다." 출력 조건에 맞추기 위해 스도쿠가 처음 완성되는 시점에 함수를 빠져나오도록 했다. 1부터 채우기 때문에 처음 ..
[Java] BOJ11497_통나무 건너뛰기 www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 두 통나무의 높이의 차가 최소가 되려면 두 번째 통나무는 첫 번째 통나무의 바로 다음번째로 큰 통나무여야 한다. 여기서 정렬을 해야 하는 것을 알 수 있고, 정렬하여 가장 차이가 조금 나게 뽑아낼 것이기 때문에 그리디 알고리즘을 유추할 수 있다. 정렬을 한 배열을 다시 재배치 해야하는데 문제의 예시에서 힌트를 얻을 수 있다. [2, 5, 9, 7, 4]. 바로 왼쪽 오른쪽 번갈아가며 수를 배치하는 것이다. 이..
[Java] BOJ11404_플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 제목부터 플로이드다. 플로이드-와샬 알고리즘을 사용하면 된다. 다만 주의할 점은 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."라는 조건 때문에 인접 행렬을 만들 시에 중복으로 들어오는 값 중 작은 값을 넣어줘야 한다. 또한 작은 값을 세팅해주기 위해 배열을 MAX_VALUE로 초기화해주었는데, "만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다."라는 조건을 잊지 말고..

티스토리툴바