public class Main { public static void heapSort(int[] arr) { for (int i = arr.length / 2 - 1; i >= 0; i--) { // 마지막 부모부터 힙정렬하며 올리기 heapify(arr, i, arr.length); } // 모든 부모가 자식보다 큰 상태 //인덱스 0이 최대값 -> 계속 뒤로 보내며 힙정렬하기 //length 마지막에 max를 swap하며 length를 하나씩 줄인다 //마지막 0은 필요없음 (최소값 배치되있음) for (int i = arr.length - 1; i > 0; i--) { ..
자료구조 & 알고리즘
public class Main { // 버블 정렬 -> 버블정렬은 비교 시 인덱스 증가시키며 정렬.. public static void bubbleSort(int[] arr) { for (int i = 0; i arr[j + 1]) { swap(arr, j, j + 1); } } } } // 삽입 정렬 -> 삽입정렬은 비교 시 인덱스 감소시키며 정렬.. public static void insertionSort(int[] arr) { for (int i = 1; i 0; j--) { // j-1이 같거나 크면 멈춤 if (arr[..
public class Main { public static void main(String[] args) { // Test code int[] arr = {3, 5, 2, 7, 1, 4, 6}; int[] tmp = new int[arr.length]; mergeSort(arr, tmp, 0, arr.length - 1); System.out.println("합병 정렬: " + Arrays.toString(arr)); } public static void mergeSort(int[] arr, int[] tmp, int left, int right) { if (left
// 원형 연결 리스트 (Circular Linked List) 구현 class CircularLinkedList { NodeBi head; NodeBi tail; CircularLinkedList(NodeBi node) { this.head = node; this.tail = node; this.head.prev = tail; this.head.next = tail; } // 전체 조회 void showData() { if (this.head == null) { System.out.println("List is Empty !!"); return; } NodeBi cur = this.head; while (true) { System.out.print(cur.data + " "); cur = cur.nex..
/** * 직관적인 느낌과 다르게 순열보다 조합이 계산이 더 복잡 * 조합 = 순열 / 줄 세우는 방법의 수 * * 조합(줄 세우지 않는 뽑기 경우의 수) * == 먼저 줄 세워서 뽑은 후(순열) 줄세우는 것을 취소함(줄세우는 방법 경우의 수로 나눔) * * 5C3 = (5P3 == 5 * 4 * 3) / (3! == 줄세우는 방법의 수) --> 3!의 의미는 뭐지? (줄 세우는 방법의 수?) * * cf) 5C3 과 5C2의 결과는 같음. * 5개중 3개를 뽑는 것이 곧 나머지 2개를 뽑는 것. */ public class Main { public static int combination(int n, int r) { int nResult = 1; for (int i = n; i >= n - r + 1;..
/** * 순열은 뽑아서 줄 세우기 -> 곱의법칙 응용 * 5명 중 3명 줄 세우기 -> 5*4*3 */ public class Main { public static void main(String[] args) { // 1. 팩토리얼 System.out.println("== 팩토리얼 =="); // 5! int result = 1; for (int i = 1; i 5 * 4 * 3 int n = 5; int r = 3; result = 1; for (int i = n; i >= n - r + 1; i--) { result *= i; } System.out.println(result); // 3. 중복 순열 /** * * 중복 순열 이론 (중복 허용 순열) * cf) 하나의 대상이 여러번 등장하므로 사람의..
// 문자열 배열 strs 와 targets 가 주어졌을 때 // targets 내의 단어 중 한 문자만 바꾸면 strs 중의 단어가 되는지 판별하는 프로그램을 작성하세요. // 입출력 예시 // 입력 strs: "apple", "banana", "kiwi" // 입력 target: "applk", "bpple", "apple" // 출력: true, true, false public class Practice3 { public static void solution(String[] strs, String[] targets) { Practice2.Trie trie = new Practice2.Trie(); for (String s : strs) { trie.insert(s); } for (String ta..
/** * * 순열 == 뽑아서 줄 세우는 경우의 수 -> 곱의법칙 응용 * 5명 중 3명 줄 세우기 -> 5*4*3 * */ // 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오 // 방법 1 -> swap() 활용 // 방법 2 -> visited[] 활용 public class Practice1 { static int result; //결과 개수 // 방법 1 -> swap을 이용한 풀이.. public void permutationBySwap(int[] arr, int depth, int n, int r) { if (depth == r) { result++; for (int i = 0; i < r; i++) { System.out.prin..
class Node { Map child; //노드는 자식 Map과 터미널 여부를 갖고 있음.. boolean isTerminal; public Node() { this.child = new HashMap(); this.isTerminal = false; } } class Trie { Node head; public Trie() { this.head = new Node(); } public void insert(String data) { Node cur = this.head; for (int i = 0; i < data.length(); i++) { char c = data.charAt(i); cur.child.putIfAbsent(c, new Node()); cur = cur.child.get(c); ..
// nums 배열에 주어진 정수들 중에서 가장 많이 발생한 숫자들 순으로 k 번째 까지 출력하세요. // 빈도가 같은 경우에는 값이 작은 숫자가 먼저 출력되도록 구현하세요. // 입출력 예시 // 입력: 1, 1, 1, 2, 2, 3 // k: 2 // 출력: 1, 2 // 입력: 3, 1, 5, 5, 3, 3, 1, 2, 2, 1, 3 // k: 3 // 출력: 3, 1, 2 public class Practice { public static void solution1(int[] nums, int k) { // Map.Entry & Comparator로 풀기 // Map.Entry로 풀기 Map map = new HashMap(); for (int i = 0; i < nums.length; i++) ..
