개발일지
자바 알고리즘 공부를 꾸준히 하고 있습니다.
난이도가 높아질수록 문제를 푸는 데 걸리는 시간이 길어지고 있지만, 다양한 유형의 문제를 접하며 실력이 점차 향상되고 있음을 느낍니다. 많은 문제를 풀어보면서 깨달은 것은, 문제를 신속하게 파악하고 해결 방법을 찾아내는 것이 중요하다는 것입니다.
앞으로도 알고리즘 문제 풀이를 블로그에 지속적으로 게시할 예정입니다. 문제를 풀어본 후, 그 경험을 글로 작성하는 과정을 통해 복습을 하고, 동시에 다른 사람들과 공유할 수 있는 기회가 될 것입니다.
이번 글에서는 자바 알고리즘에서 자주 사용되는 정렬, 검색, 재귀 함수, 리스트(List)에 대해 간략하게 정리해보려 합니다.
정렬(Sorting)
정렬은 데이터를 특정한 순서대로 나열하는 과정입니다. 자바에서 자주 사용되는 정렬 알고리즘에는 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 등이 있습니다.
버블 정렬 (Bubble Sort)
버블 정렬은 인접한 두 원소를 비교하여 정렬하는 방식입니다. 이 알고리즘은 각 반복마다 가장 큰 원소가 배열의 끝으로 이동하므로 “버블” 정렬이라고 불립니다.
void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
// 원소들의 위치를 교환
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}선택 정렬 (Selection Sort)
선택 정렬은 배열에서 가장 작은 원소를 찾아 첫 번째 위치로 이동시키고, 이후 두 번째 작은 원소를 찾아 두 번째 위치로 이동시키는 방식으로 진행됩니다.
void selectionSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// 가장 작은 원소를 맨 앞으로 이동
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}삽입 정렬 (Insertion Sort)
삽입 정렬은 각 원소를 이미 정렬된 배열 부분에 적절한 위치에 삽입하는 방식으로 정렬합니다.
void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// key보다 큰 원소들을 한 칸씩 뒤로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}병합 정렬 (Merge Sort)
병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 두 부분을 병합하여 정렬하는 방식입니다.
void merge(int arr[], int l, int m, int r) {
// 병합할 두 부분 배열의 크기 계산
int n1 = m - l + 1;
int n2 = r - m;
// 임시 배열 생성
int L[] = new int [n1];
int R[] = new int [n2];
// 데이터를 임시 배열에 복사
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
// 임시 배열들을 병합하여 원래 배열에 저장
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// 남아있는 원소들을 원래 배열에 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void sort(int arr[], int l, int r) {
if (l < r) {
// 중간 지점 찾기
int m = (l+r)/2;
// 분할 정복
sort(arr, l, m);
sort(arr , m+1, r);
// 병합
merge(arr, l, m, r);
}
}퀵 정렬 (Quick Sort)
퀵 정렬은 피벗을 사용하여 배열을 두 부분으로 나누고, 각 부분을 재귀적으로 정렬하는 방식입니다.
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low-1); // 피벗보다 작은 원소의 인덱스
for (int j=low; j<high; j++) {
if (arr[j] < pivot) {
i++;
// i와 j의 원소 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 피벗 원소를 올바른 위치에 교환
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
// 피벗 위치를 파티셔닝
int pi = partition(arr, low, high);
// 분할 정복
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}✔️각 알고리즘은 특정 상황에 따라 그 효율성이 달라질 수 있습니다. 예를 들어, 작은 데이터 세트 또는 거의 정렬된 데이터에는 삽입 정렬이 적합할 수 있으며, 큰 데이터 세트에는 병합 정렬이나 퀵 정렬이 좋은 선택이 될 수 있습니다.
검색(Searching)
검색은 데이터 집합에서 특정한 값을 찾는 과정입니다. 자바에서 자주 사용되는 검색 알고리즘에는 선형 검색(Linear Search)과 이진 검색(Binary Search)이 있습니다.
선형 검색 (Linear Search)
선형 검색은 가장 기본적인 검색 방법입니다. 배열의 각 원소를 차례대로 검사하여 원하는 값을 찾습니다.
int linearSearch(int arr[], int x) {
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == x)
return i; // 원하는 값 x를 찾으면 그 위치를 반환
}
return -1; // 찾지 못한 경우 -1 반환
}이진 검색 (Binary Search)
이진 검색은 정렬된 배열에서 사용할 수 있는 효율적인 검색 방법입니다. 배열의 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 반으로 줄여나갑니다.
int binarySearch(int arr[], int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r-l) / 2;
if (arr[m] == x)
return m; // 원하는 값 x를 찾으면 그 위치를 반환
if (arr[m] < x)
l = m + 1; // 중간값보다 큰 경우 오른쪽 탐색
else
r = m - 1; // 중간값보다 작은 경우 왼쪽 탐색
}
return -1; // 찾지 못한 경우 -1 반환
}✔️이진 검색을 사용하기 위해서는 배열이 미리 정렬되어 있어야 합니다. 배열이 정렬되어 있지 않은 경우, 먼저 정렬한 후 이진 검색을 수행해야 합니다. 선형 검색은 정렬되지 않은 데이터에서도 사용할 수 있는 장점이 있습니다.
재귀 함수(Recursive Function)
자바에서 재귀 함수는 메소드가 자신을 다시 호출하는 방식으로 작동하는 함수입니다. 이러한 재귀적 접근은 문제를 해결하기 위해 동일한 문제의 더 작은 하위 문제로 나누는 분할 정복 전략에 자주 사용됩니다.
💡재귀 함수의 기본 구조
- 기저 조건(Base Case): 재귀 호출의 종료 조건입니다. 이 조건이 충족되면 함수는 더 이상 자기 자신을 호출하지 않고 종료됩니다. 이 조건이 없으면 무한 재귀 호출로 인해 스택 오버플로우 오류가 발생할 수 있습니다.
- 재귀 단계(Recursive Step): 문제를 더 작은 하위 문제로 나누고, 이를 해결하기 위해 함수가 자기 자신을 호출합니다.
재귀 함수 예제: 팩토리얼 계산
팩토리얼 계산은 재귀 함수의 전형적인 예제입니다. 팩토리얼 n!은 1부터 n까지의 정수를 모두 곱한 값입니다. 예를 들어, 5! = 5 * 4 * 3 * 2 * 1입니다. 팩토리얼을 재귀적으로 계산하기 위해서는 n! = n * (n-1)!이라는 관계를 사용합니다.
public class Factorial {
public static void main(String[] args) {
int number = 5;
int result = factorial(number);
System.out.println("The factorial of " + number + " is: " + result);
}
public static int factorial(int n) {
// 기저 조건
if (n <= 1) {
return 1;
}
// 재귀 단계
return n * factorial(n - 1);
}
}이 코드에서 factorial 함수는 팩토리얼을 계산하기 위해 자기 자신을 재귀적으로 호출합니다. n이 1 이하가 되면 기저 조건에 도달하고, 함수는 1을 반환하여 재귀 호출을 종료합니다. 그렇지 않으면 함수는 n에 n-1의 팩토리얼을 곱하여 반환합니다.
✔️재귀 함수를 사용할 때는 기저 조건을 적절히 설정해야 하며, 재귀 호출이 너무 깊어지지 않도록 주의해야 합니다. 너무 깊은 재귀 호출은 스택 오버플로우를 일으킬 수 있기 때문입니다.
리스트(List)
자바에서 리스트(List)는 순서가 있는 데이터의 컬렉션을 나타내는 자료구조입니다. 리스트는 중복된 요소를 저장할 수 있으며, 각 요소는 특정 인덱스에 의해 접근됩니다. 자바의 java.util.List 인터페이스는 이러한 리스트의 동작을 정의하며, 가장 일반적으로 사용되는 구현체로는 ArrayList, LinkedList 등이 있습니다.
List 인터페이스의 주요 메소드
- add(element): 리스트의 끝에 요소를 추가합니다.
- add(index, element): 지정된 인덱스에 요소를 추가합니다.
- remove(index): 지정된 인덱스의 요소를 제거합니다.
- set(index, element): 지정된 인덱스에 있는 요소를 다른 요소로 대체합니다.
- get(index): 지정된 인덱스의 요소를 반환합니다.
- size(): 리스트의 길이(요소의 개수)를 반환합니다.
ArrayList와 LinkedList의 차이
- ArrayList: 내부적으로 동적 배열을 사용합니다. 인덱스를 통한 빠른 임의 접근이 가능하지만, 중간에 요소를 추가하거나 제거할 때는 시간이 더 걸립니다.
- LinkedList: 내부적으로 이중 연결 리스트를 사용합니다. 요소의 추가와 제거가 빠르지만, 임의 접근에는 더 많은 시간이 소요됩니다.
ArrayList 예제
import java.util.ArrayList;
import java.util.List;
public class ArrayListExample {
public static void main(String[] args) {
List<String> fruits = new ArrayList<>();
// 리스트에 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
// 특정 인덱스에 요소 추가
fruits.add(1, "Blueberry");
// 요소 출력
System.out.println("ArrayList of fruits: " + fruits);
// 특정 인덱스의 요소 제거
fruits.remove(2);
// 요소 변경
fruits.set(2, "Orange");
// 특정 인덱스의 요소 가져오기
String fruit = fruits.get(1);
System.out.println("Fruit at index 1 in ArrayList: " + fruit);
// 리스트의 크기 출력
System.out.println("Size of the ArrayList: " + fruits.size());
}
}LinkedList 예제
import java.util.LinkedList;
import java.util.List;
public class LinkedListExample {
public static void main(String[] args) {
List<String> vegetables = new LinkedList<>();
// 리스트에 요소 추가
vegetables.add("Carrot");
vegetables.add("Potato");
vegetables.add("Cabbage");
// 특정 인덱스에 요소 추가
vegetables.add(1, "Onion");
// 요소 출력
System.out.println("LinkedList of vegetables: " + vegetables);
// 특정 인덱스의 요소 제거
vegetables.remove(2);
// 요소 변경
vegetables.set(1, "Beetroot");
// 특정 인덱스의 요소 가져오기
String vegetable = vegetables.get(1);
System.out.println("Vegetable at index 1 in LinkedList: " + vegetable);
// 리스트의 크기 출력
System.out.println("Size of the LinkedList: " + vegetables.size());
}
}이 예제들에서는 각각 ArrayList와 LinkedList를 사용하여 문자열 요소들을 저장하는 리스트를 만듭니다. 두 예제 모두 요소를 추가, 제거, 변경하는 방법을 보여주고, 특정 인덱스의 요소를 가져오며 리스트의 크기를 출력합니다.
✔️ArrayList는 인덱스를 통한 접근이 빈번할 때, LinkedList는 데이터의 추가와 삭제가 자주 발생할 때 각각 더 적합합니다. 이러한 특성을 고려하여 상황에 맞게 적절한 리스트 타입을 선택하는 것이 중요합니다.
마무리
이번 글에서는 자바 알고리즘에서 사용되는 정렬, 검색, 재귀 함수, 리스트(List) 에 대해 간략하게 정리해보았습니다. 정렬 알고리즘에서는 상황에 맞는 방법을 선택하는 것이 중요하며, 검색 방법은 데이터의 정렬 여부에 따라 선형 검색과 이진 검색 중 선택할 수 있습니다. 재귀 함수는 분할 정복 전략에 유용하며, 리스트는 ArrayList와 LinkedList로 데이터를 효율적으로 관리할 수 있습니다.
이러한 알고리즘들을 실제 문제 해결에 적용하며 저의 코딩 능력이 향상되고 있음을 느낍니다. 앞으로도 이러한 경험들을 블로그를 통해 지속적으로 공유하도록 하겠습니다.👍