목록코딩 문제/백준 (51)

늘 겸손하게

백준 1991 - 트리 순회

문제 풀이 각 노드의 root 값을 인덱스로 삼아 ArrayList에 저장하고 읽고 쓰는 방식을 이용하여 풀었습니다. 전위 순회 ( PreOrder)는 root, left, right 순, 중위 순회 ( InOrder )는 left, root, right 순 후위 순회 (PostOrder )는 left, right, root 순으로 탐색을 하는 방법입니다. 이를 코드로 구현하면 전휘 순회 ( PreOrder ) : 출력이 1, left 탐색 2, right 탐색 3 1 2 3 4 5 6 7 8 // root - left - right public static void preOrder(char node) throws IOException { if (node == '.') return; bw.write(no..
코딩 문제/백준 2022. 2. 20. 16:37
백준 1929 - 소수 구하기 - 에라토스테네스의 체 ( Java )

besforyou 문제 풀이 M, N을 입력받고 M과 N 사이 소수를 모두 출력하는 문제입니다. 이 문제는 에라토스테너스의 체를 적용하면 매우 빠르게 풀어낼 수 있습니다. 에라토스테네스의 체 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2를 제외한 모든 2의 배수를 지운다. 남아있는 수 가운데 3을 제외한 모든 3의 배수를 지운다. 위 과정을 반복한다. N까지의 소수를 구한다고 치면 M * M > N 을 만족하는 M의 배수들 까지만 지워도 정답을 구할 수 있다. 예로, 120까지의 소수를 구한다고 치면, 11 * 11 > 120 이므로 11의 배수들 까지만 지워도 소수들만 구할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..
코딩 문제/백준 2022. 2. 18. 14:12
백준 10815번 - 숫자 카드 ( Java )

안녕하세요 besforyou 입니다 이번 그은 백준 10815번 - 숫자 카드 문제 풀이입니다. 문제 풀이 상근이가 가지고 있는 숫자 카드의 개수(N)와 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수의 크기가 매우 크므로 원하는 데이터를 빠르게 찾아낼 수 있는 자료구조가 필요합니다. 그래서 제가 선택한 자료구조는 HashSet입니다. 일반적인 배열이나 ArrayList의 contains() 메소드는 원하는 원소를 찾는데 걸리는 시간복잡도는 O(N)이지만 HashSet은 O(1)의 시간복잡도를 가져 원하는 데이터를 더 빠르게 찾을 수 있습니다. 다만, 원소를 정렬시키지 못하고 배열의 원소를 수정하기 어려운 단점이 있습니다. 풀이 과정 1. N값을 입력받고 N개의 숫자카드 값을 Hash..
코딩 문제/백준 2022. 2. 17. 15:16
자바로 힙 사용하는 방법 - 백준 1927,11279 ( 최소힙, 최대힙)

안녕하세요 besforyou 입니다. 이번 글은 자바로 heap 자료구조를 사용하는 방법에 대해 소개하겠습니다. PriorityQueue를 사용하면 됩니다. 1. 최소 힙 1 PriorityQueue minHeap = new PriorityQueue(); cs 2. 최대 힙 최대힙에는 Comparator를 넣어줍니다. 람다 식 1 2 PriorityQueue minHeap = new PriorityQueue ((Integer o1, Integer o2) -> ( -Integer.compare(o1,o2))); cs 오버라이드 버전 1 2 3 4 5 6 7 PriorityQueue minHeap = new PriorityQueue (new Comparator() { @Override public int c..
코딩 문제/백준 2022. 2. 14. 13:50
이전 Prev 1 2 3 4 5 6 7 ··· 13 Next 다음