알고리즘

문제를 해결하기 위해 수행해야 하는 절차나 방법
  • APS(Algorithm Problem Solving): 알고리즘 문제 풀이
  • 문제를 푸는 방식에 따라 작업량이나 소요시간 등이 달라질 수 있기 때문에 알고리즘이 필요

고려 사항

  1. 정확성 : 얼마나 정확하게 동작하는가
  2. 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
  3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
  4. 단순성 : 다른 사람이 이해하기 쉬운가
  5. 최적성 : 더 이상 개선할 여지없이 최적화되었는가

 

시간 복잡도

알고리즘의 효율성을 평가하는 지표 중 하나

✅ 빅오 표기법

  • 최악의 경우 시간 복잡도
  • 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
  • 계수(Coefficient)는 생략하여 표시

 

✅ 시간 복잡도에 따른 n의 가용 범위

시간 복잡도 n의 가용 범위
O(n!) 10
O(2^n) 20 ~ 25
O(n^3) 200 ~ 300
O(n^2) 3000 ~ 5000
O(nlogN) 100만
O(n) 1000만 ~ 2000만
O(logN) 10억

 

정렬

버블 정렬

인접한 두 개의 원소를 비교한 후 교환하는 과정을 반복하여 데이터를 정렬하는 방식
  • 시간 복잡도 : O(n^2)

정렬 과정

  1. 첫 번째 원소부터 인접한 원소와 비교하여 자리를 교환해가면서 마지막 자리까지 이동한다
  2. 기준(오름차순)한 사이클이 끝나면 가장 큰 원소가 마지막 자리로 위치하게 된다
  3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다

package sort;

import java.util.Arrays;

public class 버블정렬 {

	public static void main(String[] args) {
		int[] arr = { 55, 7, 78, 12, 42 };
		int n = arr.length;
		
		for(int i = n - 1; i > 0; i--) {
			for(int j = 0; j < i; j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		System.out.println(Arrays.toString(arr));
	}

}

 

선택 정렬

저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
  • 시간 복잡도 : O(n^2)

정렬 과정

  • 주어진 자료들 중 최소값을 찾는다
  • 그 값을 리스트의 맨 앞에 위치한 값과 교환한다
  • 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다

package sort;

import java.util.Arrays;

public class 선택정렬 {

	public static void main(String[] args) {
		int[] nums = { 64, 25, 10, 22, 11 };
		int n =  nums.length;
		
		int[] sortedNums = Arrays.copyOf(nums, n); // 원본 배열의 세번째로 작은 수의 인덱스를 찾기 위해 복사 배열 생성
		
		// 선택 정렬 수행(최소값 찾아서 맨 앞으로 옮겨주며 정렬)
		for(int i = 0; i < n - 1; i++) {
			int minIdx = i;
			for(int j = i + 1; j < n; j++) {
				if(sortedNums[minIdx] > sortedNums[j]) {
					minIdx = j;
				}
			}
			if(minIdx != i) {
				int temp = sortedNums[i];
				sortedNums[i] = sortedNums[minIdx];
				sortedNums[minIdx] = temp;
			}
		}
		
		int thirdSmallest = sortedNums[2]; // 세번째로 작은 수
		int indexOfThirdSmallest = -1;
		
		for(int i = 0; i < n; i++) {
			if(nums[i] == thirdSmallest) {
				indexOfThirdSmallest = i;
				break;
			}
		}
		System.out.println(Arrays.toString(sortedNums));
		System.out.println("세 번째로 작은 수: " + thirdSmallest);
		System.out.println("세 번째로 작은 수의 원본 배열 인덱스: " + indexOfThirdSmallest);
		

	}

}

 

삽입 정렬

정렬할 요소를 뒤에 있는 요소와 비교한 뒤 스왑이 일어났다면 앞에 있는 모든 요소와도 비교를 하는 방식
  • 시간복잡도: O(n^2)

정렬 과정

  1. 배열의 첫 번째 요소는 이미 정렬된 상태라고 가정
  2. 배열의 두 번째 요소(key)부터 시작하여 앞 칸의 요소가 더 크면 스왑
  3. 2번을 맨 앞 요소까지 반복
  4. key를 오른쪽으로 옮겨가며 반복

출처: https://www.geeksforgeeks.org/insertion-sort-algorithm/

package sort;

import java.util.Arrays;

public class 삽입정렬 {

	public static void main(String[] args) {
		int[] arr = { 23, 1, 10, 5, 2 };
		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--;
			}
			arr[j + 1] = key; // key를 적절한 위치에 삽입
		}

		System.out.println(Arrays.toString(arr));

	}

}

 

카운팅 정렬

요소가 몇 번씩 등장하는지 세는 방법으로 정렬하는 알고리즘
  • 시간 복잡도: O(n)
  • 시간 복잡도가 획기적임에도 요소의 값이 커지면 counting 배열의 크기도 커지므로 메모리 낭비가 심해 많이 쓰이지 않음

정렬 과정

  1. 원본 배열에서 요소가 몇 번 등장하는지를 counting 배열이라는 새로운 배열에 저장한다. 이때 원본 배열의 요소가 카운팅 배열의 인덱스가 된다.
  2. 카운팅 배열을 가지고 누적합을 계산한다.
  3. 완성된 누적합 배열을 가지고 결과 배열을 생성한다.

package sort;

import java.util.Arrays;

public class 카운팅정렬 {

	public static void main(String[] args) {
		int[] arr = { 7, 2, 3, 5, 7, 1, 4, 6, 7, 5, 0, 1 };
		int max = 7; // 배열의 최대값을 알고 있다고 가정
		int[] count = new int[max + 1]; 
		int[] result = new int[arr.length];
		
		// 각 숫자의 개수 세기
		for(int num:arr) {
			count[num]++;
		}
		
		// 누적합 계산 및 저장
		for(int i = 1; i <= max; i++) {
			count[i] += count[i-1];
		}
		
		// 원본 배열의 뒤 쪽부터 순회
		for(int i = arr.length - 1; i >= 0; i--) {
			result[count[arr[i]] - 1] = arr[i]; // [원본 배열 값에 대한 카운팅 배열의 값 - 1]을 결과 배열의 인덱스로 하여 채움
			count[arr[i]]--; // 결과 배열에 적용됐으니 카운팅을 하나 줄여줌
		}
		
		System.out.println(Arrays.toString(result));
	}

}

 

병합 정렬

분할 정복 알고리즘으로 정렬하는 방식
  • 시간 복잡도: O(nlogN)

정렬 과정

  1. 원본 배열을 최소 단위가 될 때까지 쪼갠다.
  2. 각 요소를 합하면서 비교하고 새로운 자리를 차지한다.

출처: https://st-lab.tistory.com/233

package sort;

import java.util.Arrays;

public class 병합정렬 {

	public static void divide(int[] arr) {
		if (arr.length < 2)
			return;

		int mid = arr.length / 2;
		int[] left = Arrays.copyOfRange(arr, 0, mid);
		int[] right = Arrays.copyOfRange(arr, mid, arr.length);
		
		divide(left);
		divide(right);
		
		mergeSort(arr, left, right);

	}

	public static void mergeSort(int[] arr, int[] left, int[] right) {
		// i: left 배열 index, j: right 배열 index, k: 원본 배열 index
		int i = 0, j = 0, k = 0;
		
		// 두 배열에서 요소를 비교하여 작은 값을 원래 배열에 추가
		while(i < left.length && j < right.length) {
			if(left[i] <= right[j]) arr[k++] = left[i++];
			else arr[k++] = right[j++];
		}
		
		// 왼쪽 배열에 남은 요소(왼쪽, 오른쪽 비교 후 남은 정렬된 값들)가 있다면 추가
		while(i < left.length) arr[k++] = left[i++];
		// 오른쪽 배열에 남은 요소(왼쪽, 오른쪽 비교 후 남은 정렬된 값들)가 있다면 추가
		while(j < right.length) arr[k++] = right[j++];
  
	}

	public static void main(String[] args) {
		int[] array = { 38, 27, 43, 3, 9, 82, 10 };
		System.out.println("정렬 전: " + Arrays.toString(array)); // 정렬 전 배열 출력
		divide(array);
		System.out.println("정렬 후: " + Arrays.toString(array)); // 정렬 후 배열 출력
	}

}

 

퀵 정렬

분할 정복 알고리즘으로 정렬하는 방식
  • 시간 복잡도: 최악은 O(n^2)이지만 평균적으로 O(nlongN)

정렬 과정

  1. 피벗 선택: 배열에서 하나의 요소를 피벗(pivot)으로 선택한다. 보통 배열의 마지막 요소를 선택
  2. 파티션: 피벗을 기준으로 배열을 두 개의 부분으로 나눈다. 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 위치하도록 재배치한다.
  3. 재귀 호출: 피벗의 위치가 정해지면, 피벗을 제외한 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 수행한다.
  4. 종료 조건: 배열의 크기가 1이 되면 정렬이 완료된 것으로 간주한다.

package sort;

import java.util.Arrays;

public class 퀵정렬 {
	public static void quickSort(int[] arr, int low, int high) {
		// low가 high보다 작을 때만 정렬
		if (low < high) {
			// 파티션을 나누고 피벗의 인덱스를 반환
			int pivotIndex = partition(arr, low, high);

			// 피벗을 기준으로 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 정렬
			quickSort(arr, low, pivotIndex - 1);
			quickSort(arr, pivotIndex + 1, high);
		}
	}

	private static int partition(int[] arr, int low, int high) {
		int pivot = arr[high]; // 배열의 마지막 요소를 피벗으로 선택
		int i = low - 1; // 피벗보다 작은 요소들의 마지막 인덱스, 처음엔 없으므로 -1

		// low부터 high - 1까지 반복(high는 피벗이므로)
		for (int j = low; j < high; j++) {
			if (arr[j] < pivot) {
				i++; // 작은 요소들의 마지막 인덱스 증가
				swap(arr, i, j);
			}
		}

		// 피벗을 피벗보다 작은 요소의 다음 위치에 삽입
		swap(arr, i + 1, high);
		return i + 1; // 피벗의 최종 인덱스 반환
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main(String[] args) {
		int[] array = { 8, 4, 3, 1, 6, 7, 11, 9, 2, 10, 5 };
		System.out.println("정렬 전: " + Arrays.toString(array)); // 정렬 전 배열 출력
		quickSort(array, 0, array.length - 1); // 퀵 정렬 호출, 대상 배열, 시작 위치, 끝 위치
		System.out.println("정렬 후: " + Arrays.toString(array)); // 정렬 후 배열 출력
	}

}

 

정렬 알고리즘 비교

 

📍 자바에서 가장 효율적인 정렬 API는 Arrays.sort()와 Collections.sort()

이 두 메서드는 Timsort 알고리즘(병합 정렬과 삽입 정렬의 하이브리드)을 기반으로 하며, 평균적으로 O(n log n)

import java.util.Arrays;

public class SortExample {
    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 1, 2};
        
        // 배열 정렬
        Arrays.sort(numbers);
        
        // 정렬된 배열 출력
        System.out.println("정렬된 배열: " + Arrays.toString(numbers));
    }
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortExample {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Charlie");
        names.add("Bob");
        names.add("Alice");
        
        // 리스트 정렬
        Collections.sort(names);
        
        // 정렬된 리스트 출력
        System.out.println("정렬된 리스트: " + names);
    }
}
728x90
반응형

'LG 유플러스 유레카 SW > Algorithm' 카테고리의 다른 글

[#20] 알고리즘 - 최단 경로  (0) 2025.02.21
[#19] 비선형 자료구조 - 그래프  (0) 2025.02.20
[#18] 비선형 자료구조 - 트리  (0) 2025.02.19
[#17] 순열 & 조합 & 부분집합  (0) 2025.02.18
[#15] 자료구조(Stack & Queue) 및 Scanner  (0) 2025.02.14

티스토리툴바