https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 문제 설명 바닥 장식을 위한 타일 개수를 카운팅하는 문제이다. 단, -- 과 같이 이어져 있다면 하나의 타일로 간주한다. 풀이 방법 DFS를 활용하여 문제를 해결했다. 이어져 있는 타일의 끝까지 간 후에 카운팅하면 되기 때문이다. 고려해야 할 점은 바닥면의 끝부분에 닿은 상황이다. 이 경우에는 타일을 더 놓을 수 없으므로 해당 칸에서 DFS를 종료시킨다. private static void dfs(int..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 설명 상근이가 가지고 있는 카드 더미와 비교 카드 더미를 받아서 상근이가 가지고 있는 카드들을 체크하는 문제이다. 풀이 방법: Set, List - 통과 비교 카드 더미 중 상근이의 카드 더미만 확인하면 되므로 상근이의 카드는 Set으로 저장한다. HashSet의 contains()의 사간 복잡도는 O(1)이므로 매우 빠르다. Set sangeunCards = ..

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..