Algorithm 7 [Algorithm] 퀵정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다. 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵정렬은 첫번째 데이터를 기준 데이터로 설정합니다. 자바의 Arrays.sort()도 quickSort를 사용합니다. static void quickSort(int[] array, int start, int end) { //배열의 길이가 1인 경우는 종료 if(start >= end) return; //pivot는 배열의 첫번째 원소 int pivot = start; //left는 pivot을 제외한 첫번째 원소 int left = start +.. Algorithm 2021. 11. 26. [Algorithm] 삽입정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 앞쪽에 있는 원소들이 이미 정렬이 되어 있다고 판단하고 어떤 위치에 들어갈 지 판단하게 됩니다. 첫 번째 위치는 이미 정렬되어 있다고 판단하고, 두 번째 위치부터 왼쪽으로 이동하면서 자신이 들어갈 위치를 찾습니다. 오름차순인 경우는 왼쪽으로 이동하면서 자신보다 큰 값들과 위치를 바꾸고 작거나 같은 값이 나올 경우 탐색을 종료합니다. 내림차순인 경우는 왼쪽으로 이동하면서 자신보다 작은 값들과 위치를 바꾸고 크거나 같은 값이 나올 경우 탐색을 종료합니다. 선택정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 선택정렬보다 빠르게 동작합니다. 최악의 경우 모든 경우의 수를 파악해야 하기 때문에 O(N^2)이 걸리지만, 최적의 경우엔 O(N)의 시.. Algorithm 2021. 11. 26. [Algorithm] 선택정렬 정렬 중 가장 쉽게 구현이 가능합니다. N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다. 처리되지 않은 모든 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. 시간복잡도는 N + (N - 1) ... + 2로 등차수열 공식에 따라서 (N^2 + N - 2)/2로 표현할 수 있습니다. 빅오 표기법에 따라 O(N^2)이 됩니다. static void selectSort(int[] array) { for (int i = 0; i array[j]) { minI.. Algorithm 2021. 11. 26. [Algorithm] Vector Vector는 ArrayList와 동일한 내부구조를 가지고 있습니다. ArrayList와 마찬가지로 Vector 내부에 값이 추가되면 자동으로 크기가 조절되며 그다음 객체들은 한 자리씩 뒤로 이동됩니다. 하지만 Vector와 Arraylist의 한가지 다른 점이 있는데 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드들이 실행할 수 있습니다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있습니다. 단점 벡터는 항상 동기화되는 장점이자 단점을 가지고 있습니다. 스레드가 1개일때도 동기화를 하기 때문에 ArrayList보다 성능이 떨어집니다. Arraylist는 기본적인 기능은 벡터와 .. Algorithm 2021. 10. 6. [Algorithm] Stack import java.util.ArrayList; import java.util.function.Function; public class Stack { private ArrayList items = new ArrayList(); public Stack() { itemsNullCheck(); } public T peek() { return getTop(this::peekLogic); } public T pop() { return getTop(this::popLogic); } public void push(T item) { this.items.add(item); } public int size() { return this.items.size(); } public boolean empty() { return .. Algorithm 2021. 9. 21. [Algorithm] BOJ 1158 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Queue queue = new LinkedList(); StringBuffer sb = new StringBuffer(); int n = sc.nextInt(); int k = sc.nextInt(); for (int i = 1; i Algorithm 2021. 7. 28. [Algorithm] BOJ 1260 import java.util.*; public class Main { public static boolean[] dfsVisited; public static boolean[] bfsVisited; public static ArrayList graph = new ArrayList(); public static void dfs(int start) { dfsVisited[start] = true; System.out.print(start + " "); for (int i = 0; i < graph.get(start).size(); i++) { int x = graph.get(start).get(i); if (!dfsVisited[x]) dfs(x); } } public static void bfs(int .. Algorithm 2021. 7. 28. 이전 1 다음
