본문 바로가기
반응형

알고리즘113

백준 5639번 : 이진 검색 트리 java 이 문제는 값을 입력을 받아 이진트리를 만드는 문제입니다. 전위 순회, 후위 순회에 대한 자료는 아래의 글에서 확인하실 수 있습니다. https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-java 백준 1991번 : 트리 순회 java 이 문제는 트리를 만들어서 노드를 삽입 후 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제입니다. 전위 순회와 중위 순회, 후위 순회에 대한 설명은 네이버 백과사전에 자세히 나와있 dy-coding.tistory.com 바로 소스 코드를 확인하도록 하겠습니다. import java.io.*; public class Main{ .. 2022. 5. 30.
백준 1991번 : 트리 순회 java 이 문제는 트리를 만들어서 노드를 삽입 후 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제입니다. 전위 순회와 중위 순회, 후위 순회에 대한 설명은 네이버 백과사전에 자세히 나와있습니다. 링크를 아래에 두도록 하겠습니다. https://terms.naver.com/entry.naver?docId=2270429&cid=51173&categoryId=51173 이진 트리 이진 트리(binary tree)는 모든 노드들의 자식 노드가 두 개 이하인 트리를 의미하는데, [그림 7-42]가 이진 트리의 예다. 이런 이진 트리에서는 서브 트리가 두 개 이하기 때문에 서브 트리는 왼쪽 서 terms.naver.com 이제 코드를 보여드리겠습니다. import java.io.*; public class Ma.. 2022. 5. 30.
백준 2407번 : 조합 java 이번 문제는 주어진 입력에 따른 조합의 결과를 출력하는 것입니다. 저는 보통 조합문제를 풀 때 nCm이라는 식이 주어져 있으면 n!/(n-m)!*m! 이러한 식을 이용하여 문제를 바로 해결합니다. 이 문제에서도 이러한 방식을 통해서 문제를 해결하려 하였으나 long의 범위를 넘어서기 때문에 제한이 있었습니다. 따라서 저는 이 문제의 유형이 다이나믹 프로그래밍인 것을 확인하고 파스칼의 삼각형을 사용하여 이 문제를 해결하려 하였으나 파스칼의 삼각형을 사용하더라도 long의 범위를 넘는 수가 있어 문제를 해결할 수 없었습니다. 따라서 저는 이 long의 범위를 넘어서서 수를 표기할 수 있는 방법이 자바에 있는지 찾아보았습니다. 찾아보니 java.math.BigInteger라는 class를 이용하면 long의 .. 2022. 5. 29.
백준 1916번 : 최소비용 구하기 java 이 문제는 다익스트라 알고리즘을 이용하는 문제입니다. 다익스트라 알고리즘에 대하여 설명드리겠습니다. 예제 1번을 예시로 다익스트라 알고리즘을 설명드리겠습니다. 예제 1번에서는 왼쪽 그림과 같이 도시가 존재합니다. 이제 주어진 입력값에 맞게 버스를 배치하겠습니다. 입력값들을 전부 입력하면 다음과 같은 그림이 됩니다. 다익스트라 알고리즘은 '한 점'에서 다른 모든 점까지 각각의 거리의 최솟값을 정하는 알고리즘입니다. 이 말에 대해서 이 문제를 풀어보면 더 자세히 알려드리도록 하겠습니다. 예제 1번에서는 1번에서 시작하여 5번까지 갈 때의 버스 비용의 최솟값을 찾으라고 하였습니다. 따라서 우리는 다익스트라 알고리즘이 시작하는 점을 1번으로 둘 수 있습니다. 이제 1번에서 시작하는 버스들을 제외하고는 잠시 지우.. 2022. 5. 29.
백준 15686번 : 치킨 배달 java 이 문제는 정해진 개수의 치킨집에서 가장 짧은 거리를 이동하여 지도에 있는 모든 집들에 배달을 마무리할 수 있게 하는 문제입니다. 이 문제는 소스 코드를 보면서 설명해드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main{ static int N, M; static int[][] map; static LinkedList chicken = new LinkedList(); static int min = Integer.MAX_VALUE; static int[] drow = {0, 0, 1, -1}; static int[] dcol = {1, -1, 0, 0}; public static void main(String[] args) throws I.. 2022. 5. 28.
백준 14502번 : 연구소 java 이 문제는 dfs와 bfs를 이용하여 푸는 브루트포스 문제입니다. 소스 코드를 보면서 설명하도록 하겠습니다. import java.util.*; import java.io.*; public class Main{ static int N, M; static int[][] map; static int max = Integer.MIN_VALUE; static int[] drow = {0, 0, 1, -1}; static int[] dcol = {1, -1, 0, 0}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri.. 2022. 5. 28.
백준 1149번 : RGB거리 java 이 문제는 이전의 row와 다음의 row를 비교하여 같은 column에 수들이 들어있지 않게 더하여 최솟값이 나오게 하는 문제입니다. 저는 이 문제를 아래로 내려가면서 각 항의 합이 최솟값이 되는 조건을 찾아서 더해가며 풀었습니다. 왼쪽의 그림은 예제 1번의 입력값입니다. 이 그림을 통해서 어떤 규칙으로 문제를 푸는지 보여드리겠습니다. 이미 지나간 row는 파란색으로 표시하였고 지나가지 않은 row는 검은색으로 표시하였습니다. 이제 다음 row의 항들의 중에서 합이 최솟값이 되기 위해서는 어떤 항을 더해야하는지를 알아보겠습니다. 이 그림에서 빨간 항에서의 조건에 따른 최솟값을 구하기 위해서는 빨간 항이 있는 row의 위의 row에서 column이 다를 때의 최솟값을 더해야 합니다. 더할 수 있는 항들을 .. 2022. 5. 27.
백준 1932번 : 정수 삼각형 java 이 문제는 다이나믹 프로그래밍을 이용하여 이전의 최선의 경우의 수를 배열에 저장하며 푸는 문제입니다. 코드를 보면서 이 문제를 설명해드리겠습니다. import java.util.*; import java.io.*; 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][]; for(int i = 1; i 2022. 5. 27.
반응형

티스토리툴바