본문 바로가기
반응형

전체 글123

백준 15654번 : N과 M(5) java 이 문제는 재귀를 이용하여 원하는 조건을 출력하는 백트래킹 문제입니다. 이 문제를 풀 때 Arrays.sort를 이용하여 입력받은 배열들을 오름차순으로 정렬한 후에 푸시면 됩니다. 바로 코드를 보여드리겠습니다. import java.io.*; import java.util.*; public class Main{ static int[] intArr; static int[] dfsArr; static boolean[] visited; static int N; static int M; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System... 2022. 5. 31.
백준 1753번 : 최단경로 java 이 문제는 다익스트라 알고리즘을 푸는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 메모리 제한이 256MB라는 점입니다. 저는 이 문제를 풀 때 처음에는 들어온 자료들을 2차원 배열에 입력하였습니다. 그러나 이 방식을 이용하면 정점의 개수가 최대인 20,000개일 때 20,000 * 20,000 * 4byte = 1,600,000,000byte 즉 이 2차원 배열을 int형으로 선언하는 데만도 1.6GB라는 어마어마한 메모리를 사용한다는 것을 알게 되었습니다. 따라서 이 문제를 다른 방식으로 풀 수 있나를 찾아보니 우선순위 큐를 이용하여 문제를 푸는 방법이 있어서 이 방법을 이용하여 다익스트라 알고리즘을 구현하였습니다. 문제를 푼 방법은 코드를 보면서 추가로 설명드리겠습니다. import java.. 2022. 5. 31.
백준 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.
반응형

티스토리툴바