Computer Science/Algorithm
-
[알고리즘] Scanner VS BufferedReaderComputer Science/Algorithm 2023. 3. 3. 19:21
📍 Scanner와 BufferedReader는 대표적으로 사용자(키보드) 입력을 받기 위해 사용하는 클래스 - BufferedReader가 속도 측면에서 더 우위를 가지고 있음 - 데이터 인풋의 양이 적을 경우에는 문제 없지만, 데이터 양이 많아질수록 성능 차이가 크게 발생 Scanner 사용법 import java.util.Scanner; public class Test { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input = sc.next(); // 공백 이전 문자열 반환 int inputNum = sc.nextInt(); // 공백 이전의 숫자 반환 } } BufferedReader 사..
-
[알고리즘] 카운팅 정렬 (Counting sort) - 자바 JavaComputer Science/Algorithm 2022. 8. 21. 21:38
[ 개념 ] 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적 알고리즘 - 정수나 정수로 표현할 수 있는 자료만 적용 가능 (각 항목의 발생 횟수를 기록하기 위해 정수 항목으로 인덱스가 되는 카운트들의 배열을 사용하기 때문) - 카운트를 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함 [ 과정 설명 (오름차순) ] 1) Data 배열에서의 최댓값을 최대 인덱스로 갖는 counts 배열 생성 후, data에 각 인덱스에 해당하는 숫자가 몇 번 등장하는지 누적 카운팅 2) 뒤에서 부터 탐색하며, data 배열의 값에 해당하는 count 배열 인덱스로 가서 값을 -1 해준 뒤, result 배열에 해당 값의 인덱스로 가서 dat..
-
[알고리즘] 이진 검색 (Binary search) - 자바 JavaComputer Science/Algorithm 2022. 8. 21. 20:40
📍 검색이란? - 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 - 목적하는 탐색 키(자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것 [ 이진 검색이란? ] : 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하여 검색을 진행하는 방법 - 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써, 검색 범위를 반으로 감소시켜 보다 빠르게 검색 가능 - 이진 검색을 위해서는 자료가 반드시 정렬된 상태여야 함 [ 검색 과정 ] - 자료의 중앙에 있는 원소를 고르고 찾고자 하는 목표 값을 비교 - 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행, 반대는 오른쪽 반에 대해 검색 수행 - 찾고자 하는 값을 찾을 때까지 반복 [ 코드 예시..
-
[알고리즘] 순차 검색 (Sequential search) - 자바 JavaComputer Science/Algorithm 2022. 8. 21. 20:05
📍 검색이란? - 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 - 목적하는 탐색 키(자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것 [ 순차 검색이란? ] : 원하는 키 값을 갖고 있는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 검색하는 알고리즘 (선형 검색) - 가장 간단하고 직관적이며, 배열/연결리스트 등 순차구조로 구현된 자료구조에서 검색시 유용 - 알고리즘이 단순하여 구현은 쉬우나 검색 대상수가 늘어날수록 시간이 급격히 증가하여 비효율적 [ 검색 과정 ] - 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교 - 키 값이 동일한 원소를 찾으면 해당 원소의 인덱스 반환 - 자료구조의 마지막까지 대상을 찾지 못하면 검색 실패 - 정렬되어 있는 배열의 경..
-
[알고리즘] 퀵 정렬 (Quick sort) - 자바 JavaComputer Science/Algorithm 2022. 8. 14. 12:54
[ 개념 ] - 분할 정복(divide and conquer) 방법을 통해 주어진 배열 정렬 - 불안정 정렬, 비교 정렬 📍 분할 정복 (divide and conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 결과를 모아 원래의 문제를 해결하는 방법 [ 과정 설명 (오름차순) ] - 배열 가운데 하나의 원소를 고르며, 그 원소를 pivot 이라고 함(피벗을 기준으로 비균등하게 2개의 부분 배열로 분할) - 피벗을 기준으로 피벗 앞에는 피벗보다 작은 수가, 오른쪽에는 피벗보다 큰 수가 옮겨짐 - 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬(피벗을 다시 선택해 정렬을 반복) - 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복 [초기 배열] 6 9 20 3 5 10 7 ..
-
[알고리즘] 삽입 정렬 (Insertion sort) - 자바 JavaComputer Science/Algorithm 2022. 8. 13. 17:54
[ 개념 ] 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 [ 과정 설명 (오름차순) ] - 두 번째 요소부터 시작하여, 그 앞의 요소들과 비교하여 삽입할 위치 지정 - 두 번째 요소보다 값이 클 경우 위치를 한 칸씩 뒤로 이동 시키고, 같거나 작을 경우에는 이동을 멈추고 해당 인덱스에 요소를 삽입 - 매 순서마다 특정 요소를 어디에 삽입할 수 있는지 위치를 찾아 삽입하여 정렬 [ 코드 예시 (오름차순) - 자바 Java ] public class InsertionSort { public static void main(String[] args) { int[] nums = { 9, 5, 6, 2, 4 }; insertionS..
-
[알고리즘] 선택 정렬 (Selection Sort) - 자바 JavaComputer Science/Algorithm 2022. 8. 13. 16:55
[ 개념 ] 원소를 넣을 위치는 정해져 있고, 저장된 자료로부터 어떤 원소를 넣을지를 선택하는 알고리즘 - 제자리 정렬 알고리즘의 하나로, 자리를 선택하고 그 자리에 오는 값을 찾는 알고리즘 [ 과정 설명 (오름차순) ] - 첫 번째 순서에서는 첫 번째 위치에 배열의 최소값을 찾아 넣어준다. - 두 번째 순서에서는 두 번째 위치에 배열의 남은 값 중에서의 최소값을 넣어준다. [ 코드 예시 (오름차순) - 자바 Java ] public class SelectionSort { public static void main(String[] args) { int[] nums = {9, 5, 6, 2, 4}; selectionSort(nums); } public static void selectionSort(int..
-
[알고리즘] 버블 정렬 (Bubble Sort) - 자바 JavaComputer Science/Algorithm 2022. 8. 13. 16:03
[ 개념 ] 인접한 두 개의 원소를 비교하며 자리를 계속 교환하여 정렬하는 알고리즘 - 비교 정렬, 제자리 정렬, 안정 정렬에 속함 📍 안정 정렬 VS 불안정 정렬 - 안정 정렬: 중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘(버블정렬, 삽입정렬, 병합정렬 등) - 불안정 정렬: 중복된 값이 입력 순서와 동일하지 않게 정렬되는 정렬 알고리즘(퀵정렬, 선택정렬, 계수정렬 등) [ 과정 설명 (오름차순) ] - 첫 번째 원소부터 인접한 원소끼리 값을 비교하며 오른쪽이 큰 숫자일 수 있도록 계속 자리를 교환하며 맨 마지막 자리까지 이동 - 한 단계가 끝나면 가장 큰 원소가 맨 뒤로 이동하므로, 다음 단계부터는 가장 뒤에 있는 요소는 정렬에서 제외 - 다시 첫 번째 원소부터 값을 비교하며 이동하며 정..