분류 전체보기

지금까지 배운 탐색에는 순차 탐색, 이진 탐색이 있다. 순차 탐색 - 정렬되지 않은 대상을 기반으로 하는 탐색 이진 탐색 - 정렬된 대상을 기반으로 하는 탐색 이 중에서 이진 탐색은 중앙에 위치한 데이터를 탐색한 후 이를 기준으로 탐색 대상을 반으로 줄여나가면서 탐색을 진행하는 알고리즘이다. 찾는 대상이 맨 앞에 있던 뒤에 있던 무조건 중앙부터 반씩 줄여가면서 탐색을 진행하는데 이러한 부분에서 효율이 떨어지는 경향이 있다. 이를 개선한 알고리즘이 보간 탐색이다. 보간 탐색은 오름차순으로 정렬된 배열에서 찾고자하는 데이터가 앞에 있으면 앞쪽에서 탐색을 시작한다. 만약 다음 배열에서 key = 25 를 탐색한다고 가정하면 탐색 위치 = low + (key-array[low])/(array[high]-arra..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 이 문제는 특정 문자를 기준으로 나누는 StringTokenizer 를 통해 풀었다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamRead..

퀵 정렬은 배열에서 하나의 요소를 선택하여 기준(pivot)으로 삼는다. 그리고 배열의 왼쪽 부분과 오른쪽 부분에서 인덱스 값을 탐색하며 기준보다 크거나 작으면 그 두 수를 서로 교환하는 방식이다. ▼퀵 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void Swap(int arr[], int idx1, int idx2) { int temp = arr[idx1]; arr[idx1]=arr[idx2]; arr[idx2]=temp; } public static void QuickSort(int arr[], int left, int right) { if(left

병합 정렬이란 하나의 리스트를 두 개의 균등한 크기로 분할하는데 더 이상 분할되지 않을 때까지 한다. 그 다음 분할된 리스트 2개를 비교하여 정렬한 다음 하나의 리스트로 병합하여 정렬하는 방식이다. 예를 들어 {8, 2, 3, 7, 1, 5, 4, 6} 이라는 배열이 있을 때 다음 그림과 같은 과정을 통해 정렬된다. ▼ 병합 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void MergeSort(int arr[],int left, int right) { int mid; if(left

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 이 문제는 거스름돈을 주는데 동전의 개수가 최소가 되도록 해야한다. 그리고 예외로 거슬러 줄 수 없는 돈이면 -1을 출력해야한다. 예를 들어 7을 입력으로 받으면 5로 딱 떨어지지 않기 때문에 -2 연산을 해줘서 5를 만들어 5로 나누어 떨어지도록 만들어줘야 한다. 11을 입력으로 받으면 5로 떨어지도록 -2 연산을 반복하여 딱 나누어 떨어지도록 만든다. ( 11 → 9 → 7 → 5 → 0 ) ▼코드 import java.io.*; import java.util.*; public class Main { public..

힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 예를 들어 {2, 8, 5, 3, 9, 1} 배열은 다음과 같은 힙 정렬의 과정으로 오름차순 정렬할 수 있다. ▼ 힙 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void HeapSort(int arr[], int n) { heapify(arr, n); for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, i); } } public static void heapify(int arr[..

삽입 정렬이란 배열의 두 번째 인덱스부터 시작하여 그 앞의 인덱스가 클 경우 그 인덱스가 위치한 곳에 삽입하여 정렬하는 방식이다. 정렬 과정을 보면 다음과 같다. ▼삽입 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void InsertionSort(int arr[], int n) { int i,j; int data=0; for(i=1;i=0;j--) { if(arr[j]>data) { arr[j+1]=arr[j]; arr[j]=data; } else break; } } } public static void main(String[] args){ int arr[] = {5, 2, 6, 3, 1, 4}; Insert..

선택 정렬이란 주어진 배열에서 최솟값을 찾고 배열의 맨 앞에 위치한 값과 교체한 후 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체해 나가는 방식이다. 정렬 과정을 보면 다음과 같다. ▼선택 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void SelectionSort(int arr[], int n) { int index=0; int min=0; int j,i; for(i=0;i

버블 정렬이란 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 예를 들어 3, 2, 4, 1 이 순서대로 저장되어 있을 때 다음 배열을 오름차순으로 정렬하는 과정을 그림으로 나타내었다. 다음 그림처럼 맨 앞에서부터 맨 끝까지 정렬의 과정이 진행되었다고 해서 정렬이 완료되는 것이 아니라 다시 숫자를 비교하여 정렬을 완료될 때까지 과정을 반복해야 한다. ▼버블 정렬 코드 import java.io.*; import java.util.*; public class Main { public static void BubbleSort(int arr[], int n) { int temp; for(int i=0;i