알고리즘||코딩테스트

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 사용한 알고리즘 : 크루스칼 알고리즘 풀이전략 문제는 최소 신장트리를 만들 것을 요구하고 있다. 최소 신장트리란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 문제에서는 마을 내부의 모든 집이 연결되면서, 비용이 최소가 되도록 길을 연결했을 경우의 비용을 요구하고있기 때문에, 최소 신장트리를 만들고, 만..

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을 사용하여 자료구조 내 데이터를 오름차순으로 정렬하면서도키값을 통해 데이터에 접근해 앞뒤 또는 중..

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