본문 바로가기

Problem Solving

 (11)
[BOJ 17626] Four Squares - Java 풀이 해설 자연수 N이 주어지고, N을 구성할 수 있는 제곱수들의 수를 구하는 문제이다. 모든 자연수는 최대 자연수 4개의 제곱수의 합으로 표현할 수 있다고 라그랑주에 의해 증명이 되었다. 나의 경우 문제의 자연수를 제곱수가 2이상인 자연수로 착각해서 오래걸렸다. 풀이 과정은 다음과 같다. 배열에 1부터 N까지의 값을 저장한다. (i-j^2)+1 값을 사용해 값을 구해나간다. i는 1부터 N까지 순회하는 자연수를 의미한다. 1번의 의미를 1*1의 값의 개수라고 생각해보자. 그리고 배열을 돌면서 (i-j^2)+1를 적용시킨다. 이것을 다음과 같은 코드로 적용시킬 수 있다. for (int i = 1; i
[백준 11727] 2×n 타일링 2 풀이 해설 n이 1일 때, 2x1타일 하나가 들어갈 수 있고, n이 2일 때 (1x2, 1x2), (2x1, 2x1), (2x2) 3가지 경우의 수로 타일을 채울 수 있다. 그리고 n이 3일 때를 보면, 2x1타일을 왼쪽이 위치시켰을 경우 n이 2일 때 경우의 수만큼 채우고, n이 1일 때 경우의 수인 2x1타일이 2번 채워지는 것을 볼 수 있다. n이 4일 경우에도 마찬가지이다. 이것을 이용해 점화식을 짜본다면, n = n-1 + (n-2) * 2가 나온다. 시간복잡도 N만큼 순회하므로, O(N)이다. 코드 package _2xn타일링2_11727; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..
[프로그래머스] 기지국 설치 풀이 해설 이 문제는 전파가 닿지 않는 기지국의 범위 안에 모든 아파트에 전파를 전달하기 위해선, 몇개의 기지국이 설치되어야 하는가에 대한 값을 찾는 문제이다. 값을 찾기 위해 필요한 것은 다음과 같다. 전파가 닿지 않는 아파트의 범위 해당 범위들에 필요한 기지국의 수를 구하는 방법 전파가 닿지 않는 아파트의 범위 문제에선 stations 배열로 이미 설치된 기지국의 위치가 주어진다. 따라서 해당 위치를 기준으로 기지국의 전파 범위인 w를 빼거나 더해 범위를 구할 수 있다. 1(첫번째 아파트)부터 station - w까지 기지국이 설치되지 않았다고 가정한다면, 첫번째 범위는 station - w - 1이라고 볼 수 있다. 이제 해당 범위의 필요한 기지국의 수를 구하면 된다. 이후엔 기준을 station ..
[백준 1504] 특정한 최단 경로 특이사항 반드시 거쳐야 하는 정점 2개가 존재 풀이 그래프에 대한 최단경로 값을 구하는 문제이다. 다익스트라 알고리즘을 통해 풀이할 수 있고, 특이사항에 대한 처리를 해주면 된다. 거쳐야 하는 정점 int result1 = 0, result2 = 0; result1 += dijkstra(1, v1); result1 += dijkstra(v1, v2); result1 += dijkstra(v2, N); result2 += dijkstra(1, v2); result2 += dijkstra(v2, v1); result2 += dijkstra(v1, N); if (result1 >= INF && result2 >= INF) { System.out.println(-1); } else { System.out.pri..
[백준 1676] 팩토리얼 0의 개수 특이사항 팩토리얼은 n의 값이 커질수록 기하급수적으로 수가 커진다. 이렇게 수가 커진다면, 컴퓨터가 저장할 수 있는 변수의 크기를 넘어버리기 때문에, 답을 도출하기 힘들다. 풀이 n의 크기에 따라 소인수분해를 통해 2, 5의 수를 구한다. 2와 5를 곱하면 10이 되기 때문에, 10의 배수가 된다. 10의 배수는 또한, 2 * 5로 볼 수 있다. 즉, 2와 5의 개수를 구하고 2 * 5를 통해 0이 몇개를 포함하고 있는지 구할 수 있다. 하지만 2의 배수는 항상 5의 배수보다 많기 때문에, 5의 배수의 개수만으로 10의 배수의 개수를 추론할 수 있다. (5의 배수 개수 = 10의 배수 개수) 25와, 125를 나누어 더해준 이유는 25=5^2이고, 125=5^3이기 때문이다. 5로만 나누게 된다면 위와 ..
[백준 1629] 곱셈 문제 1629번: 곱셈 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 해결 시간초과 간단하게 for문으로 A를 B만큼 곱한다음 C로 나누어 값을 구할 수 있다. 하지만 이 문제의 입력값은 최대 2,147,483,647이고, 시간제한은 0.5초이다. 널널하게 2억번의 연산당 1초로 잡아도 10초 이상의 시간이 걸리게 되는 것을 알 수 있다. 따라서 B만큼 곱하는 방법은 사용할 수 없다. 오버플로우 최대 입력값이 2,147,483,647가 들어온다고 명시되어 있다. 이 값은 꽤 큰 값이기 때문에 큰 값이 들어온다면 연산시 오버플로우가 발생할 것이다. 지수 계산 이 문제는 오버..
[백준 1167] 트리의 지름 문제 1167번: 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 해결 트리가 주어질 때 간선의 길이가 최대로 길어질 때 그 값을 출력하는 문제이다. 접근 최대의 길이를 구하기 위해선 노드의 끝과 끝을 이은 값들 중 가장 큰 값을 출력하면 될 것이다. 시작하는 노드의 값이 끝 지점에 있는 노드임을 알 수 있다면, dfs를 사용해 각 끝노드까지의 길이를 계산해 가장 큰 값을 출력할 수 있다. 위 이미지를 예로 설명해보자면, 노드 1이 가장 끝 지점에 있으므로 dfs로 해당 노드로 d..
[백준 12015] 가장 긴 증가하는 부분 수열 2 문제 12015번: 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 해설 LIS LIS의 구현 문제로 문제의 이름과 같이 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이다. DP로 구현한 LIS로도 문제에 대한 결과 값은 출력이 가능하지만, 이 문제의 입력의 크기는 0~1,000,000이다. DP로 LIS를 구현했을 때 시간 복잡도는 O(N^2)이기 때문에 시간초과로 통과할 수 없다. 따라서 이 문제는 이분 탐색을 통해 구현한 LIS를 사용해야 한다. 이분 탐색을 사용..

티스토리툴바