본문 바로가기
반응형

알고리즘113

백준 15666번 : N과 M (12) java 이 문제는 입력된 값들을 저장하여 중복되는 수열이 출력되지 않게 비내림차순으로 출력하는 문제입니다. 이 문제를 풀 때 입력값이 중복된 값이 올 수 있다는 것을 유의해야 합니다. 따라서 저는 HashSet을 이용하여 중복된 값들을 저장하지 않고 중복되지 않은 값들로만 배열을 만들었습니다. 그 배열로 조건과 같이 출력하게 하여 문제를 해결하였습니다. 코드를 바로 보여드리도록하겠습니다. import java.io.*; import java.util.*; public class Main { static int M; static Integer[] intArr; static int[] answer; public static void main(String[] args) throws IOException{ Buffer.. 2022. 6. 12.
백준 1759번 : 암호 만들기 java 이 문제는 데이터를 입력받은 후 dfs를 이용하여 중복된 값이 나오지 않게 탐색하는 알고리즘입니다. 이 문제를 풀 때 조심해야하는 점은 모음이 1개 이상, 자음이 2개 이상 들어가야 한다는 조건입니다. 문자들을 입력받은 후 정렬하여 dfs를 실행하며 모음이 1개 이상, 자음이 2개 이상 들어 있는지 확인하면 되는 문제입니다. 바로 코드를 보여드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static char[] charArr; static int L, C; static char[] answer; static boolean[] visited; public static void main(String[] args) throws IO.. 2022. 6. 11.
백준 14938번 : 서강그라운드 java 이 문제는 다익스트라 알고리즘을 이용하여 탐색하는 알고리즘입니다. 저는 이 문제를 처음 봤을 때 bfs로도 풀 수 있을 것 같았습니다. 그래서 bfs로 문제를 먼저 풀어보았는데 bfs로 문제를 풀 때 탐색하지 않는 부분이 있을 수 있다는 것을 알게 되었습니다. 위의 그림과 같이 그래프가 존재할 때 bfs로 이 문제를 풀면 A -> B 경로를 탐색한 후 바로 A -> C 경로를 탐색합니다. 수색 범위가 10이라고 했을 때 A->C를 통해 C 노드에 이미 접근했기 때문에 A -> B -> C 경로가 더 짧음에도 불구하고 경로가 새로 생성되지 않습니다. 따라서 A -> B -> C -> D 경로로 가면 총 거리가 6이기 때문에 탐색할 수 있는 노드이지만 bfs를 이용하면 탐색할 수 없게 됩니다. 따라서 다익스.. 2022. 6. 11.
백준 15657번 : N과 M (8) java 이 문제는 입력을 받은 후 정렬하고 dfs를 이용하여 조건에 맞게 출력하는 문제입니다. 예제 2번을 예시로 그림을 통해 이 문제를 설명해드리도록 하겠습니다. 위의 그림은 예제 2번에 맞게 N크기의 배열과 M 크기의 배열을 만들었습니다. M 배열에 들어있는 자료들이 출력될 값입니다. 위 그림과 같이 M배열의 첫 번째에 들어갈 자료는 초록색 박스로 두 번째에 들어갈 자료는 빨간색 박스로 표시하였습니다. 이제 출력이 어떻게 되는지 계속해서 보여드리겠습니다. 초록색 박스가 N배열의 첫번째 칸을 가리킬 때는 이렇게 진행이 됩니다. 이제 초록색 박스를 N배열의 두 번째 칸으로 옮겨보겠습니다. 그럼 위의 그림과 같이 초록색 박스가 시작되는 지점부터 빨간색 박스도 시작합니다. 계속 진행시켜보도록 하겠습니다. 초록색 박.. 2022. 6. 10.
백준 11725번 : 트리의 부모 찾기 java 이 문제는 루트 노드가 정해져 있으니 루트 노드로부터 시작하여 간선들을 bfs를 이용하여 만나는 노드들을 조건에 맞게탐색하는 문제입니다. 저는 이 문제를 해결하기 위해 N개의 ArrayList를 List안에 넣어서 각각의 자리를 노드의 시작점으로 사용하였습니다. 그리고 1번 노드가 루트 노드이니 루트 노드에서 시작하여 연결된 간선들에 부모 노드를 입력하면서 진행하였습니다. 코드를 보여드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static List l; static int[] answer; public static void main(String[] args) throws IOException{ BufferedReader br.. 2022. 6. 10.
백준 17144번 : 미세먼지 안녕! java 이 문제는 조건에 따라서 미세먼지를 확산시킨 후 공기청정기를 작동시키는 문제입니다. 저는 이 문제를 확산시키는 함수와 공기청정기에 의해서 미세먼지들이 이동하는 함수로 나누어 풀었습니다. 우선 확산시키는 함수는 map배열을 검사하며 미세먼지의 농도가 5 이상일 때만 ArraList에 입력했습니다. 그 후 ArrayList에 있는 데이터들을 꺼내서 그 주변으로 확산시켰습니다. 미세먼지의 농도가 5 이상일 때 바로 확산시키지 않은 이유는 바로 확산시킨다면 확산된 미세먼지가 주변에 영향을 주어서 제대로 정답을 구하기 어렵기 때문입니다. 그 후 미세먼지들을 이동시키는 함수를 실행시켰습니다. 코드를 보면 이해하실 수 있으실 겁니다. import java.util.*; import java.io.*; public c.. 2022. 6. 9.
백준 4963번 : 섬의 개수 java 이 문제는 dfs를 이용하여 연결되어 있는 땅들을 확인하여 섬의 개수를 세는 문제입니다. 이 문제를 푸는 과정을 그림을 통해 보여드리도록 하겠습니다. 아래의 그림은 문제에 나와있는 예시입니다. 이제 이 그림에서 섬이 몇 개가 있는지를 찾아보겠습니다. 우선 초록색으로 표시된 땅 주변에 연결된 땅들을 찾아서 하나의 섬으로 묶어보겠습니다. 위의 그림과 같은 순서로 섬 하나가 만들어졌습니다. 이제 연결된 땅이 없으므로 떨어져 있는 섬들을 찾아보겠습니다. 노란색으로 표시된 땅 근처에도 연결된 땅이 없기 때문에 섬 하나가 또 완성되었습니다. 파란색으로 표시된 땅 주변의 땅들을 탐색해보도록 하겠습니다. 이제 더 이상 탐색하지 않은 땅이 없습니다. 따라서 이 지도에서 섬의 개수는 3개입니다. 이제 코드를 보여드리도록 .. 2022. 6. 9.
백준 1967번 : 트리의 지름 java 이 문제는 dfs를 이용하여 노드들을 이동할 때 이동한 가중치의 합이 가장 크게 되는 경로의 가중치의 합을 출력하는 문제입니다. 위의 그림과 같이 트리가 있을 때 빨간 선으로 되어 있는 간선들의 가중치의 합이 가장 크므로 이러한 경로를 구하는 알고리즘입니다. 저는 이 문제를 해결하기 위해서 각 경로에서 dfs를 하여 가중치의 합이 가장 클 때를 찾았습니다. 코드를 보면서 추가로 설명드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static List[] map; static boolean[] visited; static int max = Integer.MIN_VALUE; static int n; public static void.. 2022. 6. 8.
반응형