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 문제 설명 일련의 괄호 문자열이 주어지고 잘려진 쇠막대기 조각의 총 개수를 구하면 된다. 풀이 방법 괄호 문제의 대표적인 해결 방법인 스택을 활용하면 된다. 먼저 여는 괄호인 경우는 일단 스택에 넣는다. 그러다 닫는 괄호를 만나면 그 때 레이저인지 쇠막대인지를 판단한다. 만약 레이저라면 이때까지 넣어뒀던 쇠막대를 모두 자르게 되므로 결과값에 스택의 사이즈만큼 더해준다. 만약 쇠막대라면 그 쇠막대의 길이가 거..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 방법 1. Queue 먼저 모든 사람을 큐에 넣고 K - 1만큼 빼고 다시 큐에 넣는다. 그 후에 빼는 사람은 K 번째가 되므로 큐가 빌 때까지 이 과정을 반복하는 식으로 해결했다. 시간 복잡도는 O(N * K) 이다. while (!queue.isEmpty()) { IntStream.rangeClosed(1, K - 1).forEach(idx -> queue.add(queue.remove())); ans.add(queue.remove()); } 풀이 방법 2. ArrayList 지..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 설명 문자열 S와 T가 주어졌을 때, 주어진 규칙으로 S를 T로 만들 수 있는지 여부를 계산하는 문제이다. 풀이 방법 이 문제는 발상의 전환이 필요하다. S에서 T로 만들려면 모든 경우의 수를 따져야 한다. 하지만 T에서 S로 만드는 것은 'A와 'B' 중 한 가지만 고려하면 된다. T를 S로 만드는 방법은 다음과 같다. A로 끝나면 마지막 문자를 제거한..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 설명 듣도 못한 사람 N명과 보도 못한 사람 M명을 입력받고 두 리스트에 모두 포함되는 사람의 명수와 이름을 정렬해서 출력하며 된다. 풀이 방법 1. 이중 반복문 - 시간 초과 N과 M의 최대 크기가 500,000씩이어서 이중 반복문으로 풀면 시간 초과가 날 것 같았고 역시나 시간 초과가 발생했다. deudbojabs = Stream.of(deudjabs) .filter((deudjab) ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 설명 상담을 통한 최대 수익을 구하면 된다. 문제 이해는 크게 어렵지 않다. 풀이 방법 재귀를 활용한 완전탐색 방법을 사용할 수 있다. 이 방법은 시간 복잡도가 O(n^2)으로 문제 범위가 최대 15로 작아서 사용 가능하다. 범위가 커질 경우 DP를 활용해야 해결 가능할 것으로 보인다. private static void solution(int day, int pay) { // 퇴사하는 날이 되면 최대 급여를 계산한다. if (day == N) { max = Math.max(max, pay); return; } // 퇴사하는 날..