Java(160)
-
[Baekjoon] 16236번: 아기 상어 - Java
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 설명 BFS를 활용한 구현 문제이다. 조건이 많아 문제를 잘 이해해야 한다. 문제에서 주어진 물고기를 먹는 조건은 다음과 같다. 아기 상어는 자신보다 큰 물고기는 먹을 수 없으며 공간 또한 지나갈 수 없다. 자신과 같은 크기의 물고기는 먹을 순 없지만 지나갈 수 있다. 자신보다 작은 물고기는 먹을 수 있다. 아기 상어의 이동 조건은 다음과 같다. 더 이상 먹을 수 있는 물고기가 없다면..
2023.03.06 -
[Baekjoon] 14425번: 문자열 집합 - Java
https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 설명 N개의 문자열 집합 S가 주어진다. 그 다음 M개의 문자열이 입력되는데 이 중 집합 S에 포함된 문자열의 개수를 출력하면 된다. 풀이 방법 이렇게 중복체크하는 문제는 Set 자료구조를 활용하면 쉽게 해결할 수 있다. Set의 특징은 요소의 순서가 없으며 중복이 없다. 자바에서 제공하는 Set 중 가장 많이 사용되는 HashSet은 요소 접근에 대해 O(1..
2023.03.04 -
[Baekjoon] 1388번: 바닥 장식 - Java
https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 문제 설명 바닥 장식을 위한 타일 개수를 카운팅하는 문제이다. 단, -- 과 같이 이어져 있다면 하나의 타일로 간주한다. 풀이 방법 DFS를 활용하여 문제를 해결했다. 이어져 있는 타일의 끝까지 간 후에 카운팅하면 되기 때문이다. 고려해야 할 점은 바닥면의 끝부분에 닿은 상황이다. 이 경우에는 타일을 더 놓을 수 없으므로 해당 칸에서 DFS를 종료시킨다. private static void dfs(int..
2023.03.02 -
[Baekjoon] 10815번: 숫자 카드 - Java
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 = ..
2023.03.01 -
[Baekjoon] 2573번: 빙산 - Java
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 설명 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하면 된다. DFS와 BFS를 조합해야 할 거 같다는 생각은 들었는데 구현이 되지 않아 다른 풀이글을 참고했다. 핵심은 방문 기록을 매 반복마다 새로 사용하는 것이었다. 지금까지 풀어온 문제들은 한 번의 순회로 모두 해결되었었는데 이번 문제는 방문 기록을 매번 새로 사용..
2023.02.28 -
[Baekjoon] 1629번: 곱셈 - Java
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 ..
2023.02.27