안녕하세요! 이번 편에서는 자바 프로그래밍 언어를 이용한 코딩 테스트에서 자주 출제되는 알고리즘 중 하나인 ‘삽입 정렬(Insertion Sort)’에 대해 다루어보겠습니다. 삽입 정렬은 비교 기반의 정렬 알고리즘으로, 효율성과 간결함 덕분에 초급 프로그래머들 사이에서 널리 사용됩니다. 이 글에서는 삽입 정렬의 이론적 배경, 문제를 통해 정렬 알고리즘을 구현하고 그 과정을 자세히 설명할 것입니다.
삽입 정렬(Insertion Sort)란?
삽입 정렬은 정렬되지 않은 데이터를 하나씩 정렬된 부분으로 삽입해가는 방식의 정렬 알고리즘입니다. 이 알고리즘은 카드 게임에서 카드를 정리하는 방식과 유사하다고 생각할 수 있습니다. 즉, 여러분은 카드를 하나씩 꺼내어 이미 정렬된 카드 뭉치에 적절한 위치에 삽입하는 것입니다.
삽입 정렬의 알고리즘 동작 과정
- 정렬된 부분과 정렬되지 않은 부분으로 나누어져 있는 배열을 생각합니다.
- 정렬되지 않은 부분에서 첫 번째 원소를 선택합니다.
- 정렬된 부분에서 선택된 원소의 위치를 찾아 삽입합니다.
- 위 과정을 정렬되지 않은 원소가 없을 때까지 반복합니다.
이 알고리즘의 시간 복잡도는 최악의 경우 O(n^2), 최선의 경우 O(n) 및 평균적으로 O(n^2)입니다. 그러나 적은 양의 데이터에 대해 느린 성능을 가지므로, 대규모 데이터셋에는 다른 정렬 알고리즘(예: 퀵 정렬, 힙 정렬 등)이 더 적합할 수 있습니다.
알고리즘 문제: 삽입 정렬 구현하기
다음은 삽입 정렬 알고리즘을 구현하는 문제입니다.
문제 설명
주어진 정수 배열을 오름차순으로 정렬하는 함수를 작성하시오.
입력
배열의 길이 n (1 ≤ n ≤ 1000)
정수 배열 a (1 ≤ a[i] ≤ 10^6)출력
오름차순으로 정렬된 배열입력 예시
5
5 2 9 1 5출력 예시
1 2 5 5 9문제 풀이 과정
이 문제를 해결하기 위해, 다음의 단계를 따라 삽입 정렬 알고리즘을 자바로 구현해보겠습니다.
1. 배열 입력 받기
우선 배열의 길이와 배열 요소를 입력 받는 작업이 필요합니다. 이 작업은 자바의 Scanner 클래스를 사용하여 쉽게 수행할 수 있습니다.
import java.util.Scanner;
public class InsertionSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 배열의 길이 입력 받기
int n = scanner.nextInt();
int[] arr = new int[n];
// 배열 요소 입력 받기
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
}
}2. 삽입 정렬 알고리즘 구현
다음으로, 삽입 정렬 알고리즘을 구현합니다. 주요 아이디어는 현재 요소를 이전 요소들과 비교하여 적절한 위치에 삽입하는 것입니다. 이를 구현하기 위해 내포된 반복문을 사용할 것입니다.
public static 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--;
}
// key를 적절한 위치에 삽입
arr[j + 1] = key;
}
}3. 배열 출력하기
정렬이 완료된 배열을 출력하기 위해 간단한 출력 함수를 작성합니다.
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}4. 전체 프로그램 통합
마지막으로, 위의 모든 기능을 메인 메서드에 통합하여 전체 프로그램을 작성합니다.
public class InsertionSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
insertionSort(arr);
printArray(arr);
}
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}결론
이번 강좌에서는 자바를 사용하여 삽입 정렬 알고리즘을 구현하는 방법을 배웠습니다. 삽입 정렬은 알고리즘의 기초를 이해하는 데 도움을 주며, 실력 향상에 큰 기여를 할 수 있습니다. 알고리즘 문제풀이에서 자주 출제되는 주제이므로, 충분히 연습하시길 바랍니다. 삽입 정렬의 장단점을 이해하고, 더 나아가 다른 정렬 알고리즘과 비교하는 것도 좋은 학습 방법입니다.
마지막으로, 알고리즘 문제풀이와 코딩 테스트 준비를 위해, 더욱 다양한 문제를 풀고, 알고리즘을 체계적으로 공부할 것을 추천드립니다. 감사합니다!