반응형 분류 전체보기133 백준 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. 백준 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. 이전 1 ··· 10 11 12 13 14 15 16 17 다음 반응형
