문제 링크 1. 문제 풀이 바이러스를 노드, 연결 정보를 간선으로 간주한 그래프에서 1번 노드와 직간접적으로 연결된 다른 노드의 수를 구하는 문제로 생각할 수 있다. BFS 또는 DFS를 활용해서 방문한 노드의 수를 카운팅해주면 해결할 수 있다. 노드의 수가 크지 않아서 인접 행렬을 활용해서 구현했다. 2. 코드 1. BFS [J...

문제 링크 1. 아이디어 주어진 미로에서 이동할 수 있는 칸을 통해 $(1,\ 1)$ 에서 $(N,\ M)$ 까지 가는 최단거리를 구하는 문제로 사방탐색과 BFS를 활용하면 간단하게 해결할 수 있다. 2차원 배열로 미로가 표현됐으므로 사방탐색으로 다음에 이동할 후보지를 탐색하고, BFS는 큐의 크기만큼 탐색하면 등거리의 모든 후보를 탐색한다...

문제 링크 1. 문제 풀이 주어진 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 정점 번호가 작은 것을 먼저 방문해야 한다. 인접 리스트를 활용했는데 이때 정점 번호가 작은 것을 먼저 방문할 수 있게 정렬을 해줬다. 인접 리스트의 경우 양방향 연결을 해야함에 주의해야 한다. 2. 코드 1. 풀이 [Java...

문제 링크 1. 아이디어 필요한 최소 배추흰지렁이 마리 수는 배추밭에서 연결된 배추들을 한 묶음으로 볼 때, 각 묶음당 한 마리씩 배치하면 된다. 따라서 배추밭의 각 좌표를 순회하며 배추면 해당 배추 묶음을 전부 방문 처리하고 묶음의 수를 세주는 과정을 반복하면 된다. 방문 처리를 해주면 같은 묶음을 한번만 셀 수 있으며 구현할 때는 원본 ...

문제 링크 1. 문제 풀이 배수는 나누었을 때 나머지가 $0$ 인지 여부로 간단하게 구할 수 있다. 2. 코드 1. 풀이 [Java] class Solution { public int solution(int number, int n, int m) { if (number % n == 0 && n...

문제 링크 1. 문제 풀이 $k$ 개의 귤을 담아야 하는데 이때 귤의 종류의 수를 최소화해야 하는 문제다. 맵 자료구조를 활용해서 크기별 개수를 구한 후 개수가 많은 귤 종류부터 담으면 최소 종류로 $k$ 개를 담을 수 있다. 2. 코드 1. 풀이 [Java] import java.util.*; class Solution { ...

문제 링크 1. 문제 풀이 크기가 $10$ 인 각 배열에서 3번째로 큰 수를 출력하는 문제로 주어진 배열을 오름차순으로 정렬했을 때, 8번째에 위치한 원소를 찾으면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { public...

문제 링크 1. 문제 풀이 $3 \times N$ 크기의 벽을 두 종류의 타일로 채우는 경우의 수를 구하는 문제로 다이나믹 프로그래밍을 활용하면 해결할 수 있다. $N = 2$ 인 경우는 아래와 같은 3가지 배치가 가능하다. $N = 4$ 인 경우는 $N = 2$ 인 경우 뒤에 $N = 2$ 인 타일 종류를 다시 배치할 수도 ...

문제 링크 1. 문제 풀이 다이나믹 프로그래밍을 활용해 $1$ 부터 특정 수를 만들기 위해 필요한 최소 연산 횟수를 구하면 간단하게 해결할 수 있다. 예를 들면 $1$ 은 어떤 연산 없이도 바로 만들 수 있으므로 $dp[1] = 0$ 이 되며 주어진 연산의 역으로 $dp[1 \times 3] = 1$, $dp[1 \times 2] = 1$,...

문제 링크 1. 문제 풀이 $N$ 을 $N$ 번 출력하되 출력하는 문자열의 길이가 $M$ 자리를 넘어가면 $M$ 자리만 출력하는 문제다. $N$ 을 $N$ 번 반복한 문자열을 만들고 문자열의 길이와 $M$ 중 더 짧은 값만큼만 출력해줬다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.u...