반응형 전체 글123 백준 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. 백준 11053번 : 가장 긴 증가하는 부분 수열 java 이 문제는 다이나믹 프로그래밍을 이용하여 증가하는 부분 수열을 만드는 문제입니다. 저는 입력받은 값들을 저장하는 intArr 배열과 메모이제이션한 값들을 넣은 dp배열을 사용하였습니다. 추가적인 설명은 코드를 보면서 드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] intArr = new int[N]; int[] .. 2022. 6. 8. 백준 1912번 : 연속합 java 이 문제는 다이나믹 프로그래밍 분야의 문제로 들어오는 값을 이전의 값들의 합이 최대 일 때와 비교해서 대입하면 됩니다. 예제 1번을 보면 처음에 10이 입력이 되는데 이때 비교할 이전 값이 없으니 intArr[0]번은 10입니다. 그 다음 -4의 값이 입력이 되는데 이전의 값이 10이고 10 + (-4) = 6으로 -4보다 6이 크니 intArr[1]번은 6이 됩니다. 3이 입력이 되면 3과 9(3+6) 중에서 9가 더 크므로 intArr[2]는 9가 됩니다. 이런 규칙으로 intArr[3] = 9+1, intArr[4] = 10 + 5, intArr[5] = 15 + 6, intArr[6] = 21 + (-35)이 대입됩니다. intArr[6]에 -14가 들어있을 때 다음 입력값은 12입니다. -14 .. 2022. 6. 7. 백준 1138번 : 한 줄로 서기 java 이 문제는 키가 1 2 3 4인 사람이 순서대로 있을 때 자신의 왼쪽에 몇 명이 있었는지를 입력받아 자신의 자리를 찾아가는 문제입니다. 이를 그림으로 설명드리겠습니다. 위의 그림은 예제 1번의 상황을 나타낸 것입니다. 이제 문제를 해결하는 과정을 보여드리겠습니다. 우선 키가 1인 사람은 왼쪽에 자신보다 키가 큰 사람의 수가 2이니 2번 자리로 들어갑니다. 키가 2인 사람은 왼쪽에 자신보다 키가 큰 사람이 1명이니 1번 자리로 들어갑니다. 다음은 키가 3인 사람의 순서입니다. 키가 3인 사람은 왼쪽에 자신보다 키가 큰 사람의 수가 1이므로 우선 1번 자리로 갑니다. 하지만 1번 자리는 이미 자른 사람이 자리를 하고 있기 때문에 그 뒷자리를 봅니다. 우선 2번 자리가 비어있나 확인하지만 2번 자리도 이미 차.. 2022. 6. 7. 백준 17070번 : 파이프 옮기기 1 java 이 문제는 파이프가 어디로 이동할 수 있는지를 확인해주면서 벽에 닿을 때만 제외해주면 되는 문제입니다. 이 문제를 풀 때 파이프가 현재 가로 방향에 있는지, 세로 방향인지, 대각선 방향인지에 따라서 경우를 나누어주면 됩니다. 파이프의 끝 점을 기준으로 문제를 푸는 과정을 그림으로 보여드리겠습니다. 위의 그림은 N이 4일 때를 나타냈습니다. 이제 이 파이프가 이동할 수 있는 경로를 찾아보겠습니다. 우선 오른쪽으로 파이프를 이동시키겠습니다. 이렇게 파이프가 위치하면 파이프가 가로 방향으로 위치해 있기 때문에 오른쪽과 오른쪽 대각선 아래 방향이 가능합니다. 이 두 방향으로 파이프를 이동시켜 보겠습니다. 파이프를 가로로 이동시켰을 때는 (4, 4)로 갈 수 없습니다. 하지만 대각선으로 파이프를 이동시켰을 때 세.. 2022. 6. 6. 백준 1182번 : 부분수열의 합 java 이 문제는 dfs를 이용한 백트래킹 문제입니다. dfs를 이용하여 입력받은 수열을 순회하면서 지금까지 입력받은 부분수열의 합이 S와 같아지면 경우의 수를 추가하면 됩니다. 코드를 보며 추가로 설명드리겠습니다. import java.io.*; import java.util.*; public class Main { static int N, S; static int[] numArr; static boolean[] visited; static int count = 0; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri.. 2022. 6. 6. 백준 1015번 : 수열 정렬 java 이 문제는 주어진 값들을 오름차순으로 정렬할 때 각각의 수가 몇 번째에 위치할지 찾는 알고리즘입니다. 간단한 문제이니 코드만 보고도 이해하실 수 있으실 겁니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] arr = new int[N]; int[] order = new int[N]; boolean[] visited = new bo.. 2022. 6. 5. 이전 1 ··· 9 10 11 12 13 14 15 16 다음 반응형
