Java

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 사용한 알고리즘: Binary Search 풀이전략 이분탐색을 통해 특정 값과 오차가 M 이상이면서 가장 적은 오차의 수를 구하면 된다. 완전 탐색을 통해 값을 비교하게 되면 시간 복잡도가 O(n^2)으로 n이 최대 100,000 까지 가능하다 했기 때문에 최대 10,000,000,000번(10억 번)의 연산을 하게된다. 그런데 JAVA는 통상 1초당 1억번의 연산을 수행..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 풀이 사용한 알고리즘 : 이진탐색, 해쉬 맵 자료구조 풀이전략 이진탐색을 사용하지 않고, 해쉬 맵 또는 배열 카운팅 방식으로 풀이할 수도 있는 문제이다. (실제 이진 탐색은 시간 복잡도가 O(nlogn)인데 반해, 위 방법들의 시간 복잡도는 O(n)으로 더 빠르다.) 하지만 이진 탐색 기법을 사용하여 문제를 풀이해보겠다. C++과 python과 달리 JAVA에는..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 사용한 알고리즘 : 이진 탐색, 우선순위 큐 풀이전략 보통의 이진 탐색에서는 mid(=(start+end)/2)를 사용하여 중간 값 기준으로 start와 end 위치를 변경한다. 하지만 이 문제 풀이에서는 중간 값이 아닌 양 끝의 범위를 양 끝에서 점점 조이는 방법을 활용하되 이진 탐색 구현 코드를 일부 사용했다. 양 끝 값의 합을 구하고, 그 값이 기존의 합 중 가장 작은 값보다 작으..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 사용한 알고리즘 : 다이나믹 프로그래밍(DP) 풀이전략 인접한 계단 사이의 차이는 1이라고 했으므로 다음 특정 값의 계단에서 가질 수 있는 경우의 수는 이전 계단이 현재의 계단 값보다 1 작을 경우의 수 더하기 계단 값이 1 클 경우의 수이다. 단, 0과 같은 경우는 수에 음수가 들어갈 수 없으므로 이전 계단값이 현재 계단 값보다 1 더 클 경우의 수만을 가질 수 있다. 9 또한 이전 계단 값으로 10을 가질 수 없으므로 이전 계단 값이 8인 경우의 수만을 가진다. 이를 수식으로 나타내면 아래와 같다. 마..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 사용한 알고리즘 : 분할정복 풀이전략 밑이 C, 지수가 n인 수가 있을 때, C^n을 효과적으로 구하기 위해서는 분할 정복 알고리즘이 사용된다. 분할 정복 알고리즘을 사용하지 않고 C를 n번 곱하게 되면 시간 복잡도가 O(n)이 된다. 그런데 위 문제에서 지수로 쓰이는 B의 범위가 1

https://www.acmicpc.net/problem/4233 4233번: 가짜소수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p) www.acmicpc.net 풀이 사용한 알고리즘 : 분할정복, 소수 구하기 풀이전략 이 문제를 풀기위해서는 소수 구하기와 분할정복 알고리즘을 알아야한다. 1. 소수 구하기 먼저 소수 구하기를 구현한 isPrime 함수부터 설명을 하겠다. static boolean isPrime(long num){ if(num

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 사용한 알고리즘: 우선순위큐를 사용한 다익스트라 알고리즘 풀이전략 제출하는데 계속해서 42~26% 사이에서 틀렸다는 결과가 나왔다. 거의 1시간 동안 고민을 한 끝에 제출해왔던 코드가 틀린 이유를 찾아냈는데 바로 방문여부를 결정하는 visited를 잘못된 위치에서 값 변경했기 때문이었다. 이미 방문한 위치는 다시 방문하지 않도록 우선순위 큐에 새로운 노드..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 사용한 알고리즘 : 자료구조 중 Map(TreeMap) 풀이전략 해당 문제는 자료구조에 넣을 데이터들이 오름차순으로 정렬되어 저장되면서, 앞뒤로 삽입 및 삭제가 가능해야 한다. 데크를 사용하면 앞뒤로 삽입, 삭제가 가능하겠지만 오름차순으로 정렬시키기가 어렵다. 따라서 Map 중 TreeMap을 사용하여 자료구조 내 데이터를 오름차순으로 정렬하면서도키값을 통해 데이터에 접근해 앞뒤 또는 중..

Map : 키-값 쌍을 저장하는 자료구조 - 각 키는 유일해야 한다. - 키를 통해 해당 값을 검색하거나 수정할 수 있다. - 구현체로 HashMap, TreeMap, LinkedHashMap 등이 있다. Map 생성과 추가 (put 메소드) Map map = new HashMap(); // Key는 String, Value는 Integer인 HashMap 생성 map.put("BFS", 3); // 키 "BFS"에 대한 값을 3으로 추가 map.put("DFS", 2); // 키 "DFS"에 대한 값을 2로 추가 map.put("DP", 5); // 키 "DP"에 대한 값을 5로 추가 값 불러오기 (get 메소드) int appleCount = map.get("BFS"); // 키 "BFS"에 대한 값..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 사용한 알고리즘 : 다익스트라 풀이전략 우선순위큐를 이용한 다익스트라 알고리즘을 통해 문제를 해결했다. 먼저 특정 위치로 이동했을 때 이동한 횟수를 알기위해 특정 위치와 해당 위치까지의 이동횟수를 저장하는 클래스를 선언한다. 문제에서 최소 이동횟수로 목적지에 도착하는 것이 목표이기 때문에 이동횟수를 우선순위 비교대상으로 삼고, 이를 Comparable 인터페이스를 ..