우선순위 큐 (PriorityQueue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 우선순위 큐를 구현하는 방법은 다양하다. ① 단순히 리스트를 이용하여 구현 ② 힙(Heap)을 이용하여 구현 데이터의 개수가 N개일 때, 구현 방식에 따라 시간 복잡도가 다르다. 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이 경우 시간 복잡도는 O(NlogN) 이다. 힙(Heap)의 특징 힙(Heap)은 완전이진트리의 일종 힙(Heap)에서는 항상 루트노드를 제거한다. 최소 힙(min heap) 루트노드가 가장 작은 값을 가진다. 따라서 값이 ..
Stack은 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO, Queue는 먼저 들어간 데이터를 먼저 꺼내는 FIFO 구조이다. Stack의 메서드 메서드 설명 boolean empty() stack이 비어있는지 Object peek() Stack의 맨 위에 저장된 객체 반환 Object pop() stack의 맨 위에 저장된 객체를 꺼내 반환 Object push(Object o) stack에 객체를 저장 int search(Object o) stack에서 주어진 객체를 찾아 그 위치를 반환, 못찾으면 -1 반환 💡 위치가 1부터 시작 Queue의 메서드 메서드 설명 boolean add(Object o) Queue에 객체를 추가 boolean offer(Object o) Queue에 객체를 저장 ..
이진트리 이진트리 순회(DFS) 전위순회: 중 - 왼 - 오 중위순회: 왼 - 중 - 오 후위순회: 왼 - 오 - 중 import java.util.*; class Node { int data; Node lt, rt; // 왼쪽 주소, 오른쪽 주소 저장 public Node(int val) { data = val; lt = rt = null; } } class Main { Node root; public void DFS(Node root) { if (root == null) return; else { // System.out.print(root.data + " "); 전위순회 DFS(root.lt); // System.out.print(root.data + " "); 중위순회 DFS(root.rt); /..
메모이제이션(Memoization) 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행속도를 빠르게 하는 기법이다. 값을 기록해 놓는다는 점에서 캐싱(Caching) 이라고도 한다. 피보나치 수열 메모제이션을 추가한 방법의 시간복잡도는 O(N) 이다. static int[] fibo; // 피보나치 수열 값을 저장할 배열 선언 public int DFS(int n) { if(fibo[n] > 0 ) return fibo[n]; // 메모이제이션 ✨ if (n < 2) return fibo[n] = n; else return fibo[n] = DFS(n - 1) + DFS(n - 2); } 조합수 💡 nCr =n-1C..
이진 탐색(Binary) 알고리즘을 이용해서 해결해야 하는 문제 유형은 비슷하다. 주로 최대/최소를 물어본다. 1. lt 와 rt를 정했을 때, lt ~ rt 사이에 분명 답이 있다는 확신 2. mid = (lt+rt)/2 가 답으로써 가능한 숫자인지 검증 3. 최대/최소를 구해야 하므로 더 나은 답이 있는지 확인 몇 가지 알고리즘 문제를 통해 알아보자. 문제 1 9 3 ( 9가지의 노래를 3개의 DVD에 넣을 때 DVD의 최소용량) 1 2 3 4 5 6 7 8 9 (분) 구하고자 하는 것 : DVD의 최소 용량 lt = 9 : 최소한 9분(제일 긴 노래)을 넣을 수 있어야 한다. rt = 45 : 최대한 노래 전부는 넣을 수 있어야 한다. ➜ 답(DVD의 용량크기)은 9 ~ 45 사이에 확실하게 있다...
이진탐색 (Binary Search)은 정렬되어 있는 배열에서 데이터를 검색할 때, 탐색 범위를 절반씩 줄여가며 찾아가는 알고리즘이다. public static int binarySearch(int[] arr, int target) { int answer = 0; int lt = 0; // 왼쪽끝 lt int rt = arr.length - 1; // 오른쪽끝 rt Arrays.sort(arr); // 정렬된 배열 while (lt target) // 찾는값이 mid보다 작으면 rt값 조정 rt = mid - 1; else lt = mid + 1; // mid보다 크면 lt값 조정 } return answer; } 시간복잡도 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 시간복잡도는O(log n)이다.
버블 정렬(Bubble sort)서로 인접한 두 수를 비교하여 정렬하는 알고리즘이다. 시간복잡도 : O(n2) public void bubble_sort(int arr[], int n) { for (int i = n - 1; i > 0; i--) { for (int j = 0; j arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; }}}} 선택 정렬(Seleciton sort)① 정렬되지 않은 부분 중 최소값을 찾는다.② 그 값을 정렬되지 않은 부분의 맨 앞의 수와 교체한다.③ 정렬된 ..
유클리드 호제법 유클리드 호제법은 두 수의 최대공약수(GCD)를 찾기 위한 알고리즘이다. 두 수 중 큰 수를 작은 수로 나눈다. 나머지가 0이면 작은 수가 최대 공약수 나머지가 0이 아니면 작은 수가 큰 수가되고, 나머지를 작은 수로 대체하여 1단계로 돌아간다. 즉, 큰 수를 작은 수로 나눠 나머지가 0이 될 때까지 반복하는 방식이다. 최대공약수(GCD) 구현 // 재귀 방식 public int gcd(int a, int b) { if( b == 0 ) return a; return gcd(b, a % b); } 최소공배수(LCM) 구현 최대공약수(gcd)를 이용해 최소공배수를 구한다. 최소공배수는 두 수의 곱에 최대 공약수를 나눈 값과 같다. public int lcm(int a, int b) { re..
에라토스테네스의 체 소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위를 배열에 할당하고, 하나씩 지워나간다. 1~n 까지의 소수를 구한다면 1. n+1 크기의 배열을 생성 후 2부터 n까지의 정수를 넣는다. 2. 반복문을 돌며 배열 값이 0인 i는 건너뛴다. 3. i=2 부터 시작하여 i의 배수에 해당하는 수를 모두 0으로 바꿔준다. 💡 자연수 n이 입력되면 1부터 n까지의 소수 출력하는 프로그램 작성 import java.util.*; class Main { public static void main(String[] args) { Main T = new Main(); Scanner s = new Scanner(System..
