자료구조&알고리즘63 트리 (소스코드) 기본 틀 public class NodeMgmt { Node root = null; public class Node { Node left; Node right; int value; // 노드가 갖고 있는 값 Node(int data) { this.left = null; this.right = null; this.value = data; } } // TODO public boolean insertNode(int data) { return true; } // TODO public node search(int data) { } } 이진 탐색 트리에 데이터 넣기 public boolean insertNode(int data) { // CASE 1 : Node가 하나도 없을 때 if (this.root == nu.. 2022. 7. 25. 순서 트리 탐색 전위 순회(Preorder) 노드 방문 ➡ 왼쪽 자식 ➡ 오른쪽 자식 11 ➡ 5 ➡ 4 ➡ 1 ➡ 7 ➡ 6 ➡ 9 ➡ 15 ➡ 13 ➡ 12 ➡ 14 ➡ 18 중위 순회(Inorder) 왼쪽 자식 ➡ 노드 방문 ➡ 오른쪽 자식 1 ➡ 4 ➡ 5 ➡ 6 ➡ 7 ➡ 9 ➡ 11 ➡ 12 ➡ 13 ➡ 14 ➡ 15 ➡ 18 후위 순회(Postorder) 왼쪽 자식 ➡ 오른쪽 자식 ➡ (돌아와) 노드 방문 1 ➡ 4 ➡ 6 ➡ 9 ➡ 7 ➡ 5 ➡ 12 ➡ 14 ➡ 13 ➡ 18 ➡ 15 ➡ 11 소스코드 class Node{ int data; Node left; Node right; Node(int data) { this.data = data; } } // 전위순회 : 루트 -> 왼쪽 -> 오른쪽 publ.. 2022. 7. 9. [백준] 해시를 사용한 집합과 맵 - 2910번 빈도 정렬 (Java) 문제링크 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 풀이방법 ( 순서를 유지하면서 중복은 허용하지 않으며 값을 갖고있는 자료구조가 필요해 ! ) LinkedHashMap을 활용한다. LinkedHashMap을 정렬하는 메소드도 새로 추가한다. 소스코드 작성방법 숫자를 입력받으면서 이미 맵에 포함되어있으면, 그 값에 1을 더하여 맵의 값을 변경한다. 그렇지 않으면, 맵에 숫자를 추가한다. LinkedHashMap을 정렬하는 메소드를 선언한다. LinkedHashMap을 입력받아 map을 list로 변환한 후 Collections.sort를 활용하여.. 2022. 6. 29. [백준] 해시를 사용한 집합과 맵 - 13414번 수강신청 (Java) 문제링크 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 풀이방법 ( 순서를 유지하면서 중복은 허용하지 않는 자료구조가 필요해 !) - LinkedHashSet을 활용한다. 소스코드 작성 방법 학생을 입력받으면서 set에 이미 포함되어있으면 set에 해당 문자열을 제거한다. set에는 항상 입력받은 학생을 추가한다. set을 배열로 변환한다. 만약, 배열의 크기가 k(수강 가능 인원)보다 작으면 k를 배열의 크기로 변경한다. k만큼 출력한다. 소스코드 package baekjoon.array_map.. 2022. 6. 28. [백준] 해시를 사용한 집합과 맵 - 7785번 회사에 있는 사람 (Java) 문제링크 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 접근한 방법 해시맵 풀이방법 "enter"일 때는 hashmap에 값을 true로 넣어주고 "leave"일 때는 hashmap에 값을 false로 대체한다. hashmap을 배열로 변환하여 정렬을 수행한다. 소스코드 작성 방법 hashmap을 키는 String, 값은 Boolean으로 선언한다. StringTokenizer로 입력을 받아 "enter"일 때 key는 이름으로 값은 true로 put한다. "leave.. 2022. 6. 17. 해시맵 아..주 기본적인것만 다뤄본다.. 선언방법 HashMap hashmap = new HashMap(); 삽입 hashmap.put(key, value) 조회 hashmap.get(key) 키 포함여부 hashmap.containsKey(key) 해시맵 정렬 1. 키가 문자열일 때 키 기준으로 오름차순 정렬 key를 배열에 저장하여 정렬 Object[] key = hashMap.keySet().toArray(); Arrays.sort(key); for(Object s : key) { if(hashMap.get(s)) bw.write(s+"\n"); } 2. 키가 문자열, 값이 정수형일 때 먼저 값을 기준으로 내림차순으로 정렬하고 값이 같을 때는 키를 오름차순으로 정렬 map을 list에 저장하여 정렬 Lis.. 2022. 6. 17. [백준] 문자열, 스택 - 4949번 균형잡힌 세상(Java) 혹시 ! 다음 문제를 공부하지 않으셨다면, 이 문제를 먼저 풀고 오시는 것을 추천드립니다 👍 2022.05.20 - [자료구조&알고리즘/스택] - [백준] 문자열, 스택 - 9012번 괄호 (Java) 문제링크 링크 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 접근한 방법 문자열, 스택 풀이방법 9012번 문제를 풀었다면, 대괄호처리하는 것만 추가해주면 된다. 여는 소괄호, 대괄호를 만나면 stack에 push 닫는 소괄호를 만났을 때 stack이 비어있거나 peek한 값이 여는 소괄.. 2022. 5. 20. [백준] 문자열, 스택 - 9012번 괄호 (Java) 문제링크 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 접근한 방법 문자열과 스택을 사용 풀이방법 여는 괄호를 만나면 stack에 push 닫는 괄호를 만났을 때 stack에 여는 괄호가 존재한다면 stack의 값을 pop 여는 괄호가 없다면 실패처리 마지막으로 모든 탐색을 끝냈는데 stack에 남아있다면 실패처리 소스코드 작성 방법 스택과 성공 여부를 판단하는 변수 선언 charAt으로 차례로 각 문자를 탐색 .. 2022. 5. 20. [백준] 조합 - 2309번 일곱 난쟁이 (Java) 문제링크 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 접근한 방법 - 조합 풀이방법 https://doongjeol.tistory.com/137?category=815887 참조 실수한점 다른 언어도 함께 공부하다보니, result = arr 이렇게 선언해버리는 실수를 하였다. 소스코드 import java.io.*; import java.util.Arrays; public class Q_2309_SevenDwarf { public static int[] result; public static int[] dwarf.. 2022. 2. 21. [백준] 순열 - 10819번 차이를 최대로 (Java) 문제링크 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 접근한 방법 순열 풀이방법 https://doongjeol.tistory.com/136 참조 소스코드 import java.io.*; import java.util.StringTokenizer; public class Q_10819_MaxDiff { public static int[] data; public static int result; public static void permutation(int[] arr, int n, int r, boolean[] select.. 2022. 2. 21. 부분 집합 (Sub Set) 부분 집합 (Sub Set) $2^n$ 의 경우의 수를 갖는다. 소스 코드 import java.io.*; import java.util.ArrayList; import java.util.List; public class SubSet { public static void subSet(List list, int n, int depth) { if (depth == n) { System.out.println(list); return; } list.add(depth); subSet(list, n, depth + 1); list.remove(list.size() - 1); subSet(list, n, depth + 1); } public static void main(String[] args) throws IOE.. 2022. 2. 21. 조합 (Combination) 조합 (Combination) 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 서로 다른 n개 중 r개를 택하는 조합의 경우의 수는 아래와 같다. 소스코드 import java.util.Arrays; public class Combination { public static void combination(int[] arr, int n, int r, int depth, int idx) { if (depth == r) { System.out.println(Arrays.toString(arr)); return; } for (int i = idx; i < n; i++) { arr[depth] = i; combination(arr, n, r, depth + 1, i + 1); } } public static.. 2022. 2. 20. 이전 1 2 3 4 ··· 6 다음 반응형
