https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 설명 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하면 된다. DFS와 BFS를 조합해야 할 거 같다는 생각은 들었는데 구현이 되지 않아 다른 풀이글을 참고했다. 핵심은 방문 기록을 매 반복마다 새로 사용하는 것이었다. 지금까지 풀어온 문제들은 한 번의 순회로 모두 해결되었었는데 이번 문제는 방문 기록을 매번 새로 사용..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 설명 A, B, C가 주어지면 A를 B번 곱한 후 C로 나눈 나머지를 출력해야 한다. 풀이 방법 1. 단순 계산 - 실패 문제를 보자마자 이 방법을 시도했고 바로 실패했다. Math.pow(A, B) % C 카테고리가 분할 정복에 들어있는 것을 보았다. 일반적인 거듭제곱은 O(n)이지만 이를 분할 정복으로 바꾸면 O(n log n)이 된다. 거듭제곱을 분할 정복으로 해결하는 방법은 다음과 같다. 예를 들어 2^4 % 3을 한다고 하자. 2^4는 ( 2^2 ..

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 문제 설명 주어진 문자열의 모든 부분 문자열 중 중복을 제거한 개수를 구하면 된다. 풀이 방법 - HashSet 이중 반복문을 돌면서 HashSet에 substring한 문자열을 추가하고 나면 마지막엔 중복없는 문자열의 개수만 남게 된다. for (int i = 0; i < S.length(); i++) for (int j = i; j < S.length(); j++) set.add(S.substring(i, j + 1); 전체 코드는 다음과 같다. package ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램이다. 풀이 방법 1: 반복문 - 시간 초과 처음 문제를 보고 단순히 i부터 j까지 더하는 식으로 구하도록 프로그램을 작성했으나 시간 초과가 발생했다. for (int line = 0; line < M; line++) { int[] range = Arrays.stream(br.readLine..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 벽 3개를 모두 사용하여 안전 구역을 최대한 많이 만드는 문제이다. 풀이 방법 DFS와 BFS를 혼합하여 사용한다. 먼저 DFS로 벽을 세우고, BFS로는 바이러스를 전파한다. 그렇게 만들어진 안전 구역을 구해가면서 최댓값을 구한다. 먼저 DFS 코드부터 확인하자. private static void buildWall(int count) { if (count == 3) { processMainLog..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 설명 일련의 괄호 문자열이 주어지고 잘려진 쇠막대기 조각의 총 개수를 구하면 된다. 풀이 방법 괄호 문제의 대표적인 해결 방법인 스택을 활용하면 된다. 먼저 여는 괄호인 경우는 일단 스택에 넣는다. 그러다 닫는 괄호를 만나면 그 때 레이저인지 쇠막대인지를 판단한다. 만약 레이저라면 이때까지 넣어뒀던 쇠막대를 모두 자르게 되므로 결과값에 스택의 사이즈만큼 더해준다. 만약 쇠막대라면 그 쇠막대의 길이가 거..