카테고리 없음

알고리즘

박수연_01 2023. 10. 2. 19:56

거품정렬

 서로 인접한 두 원소의 알고리즘을 대소 비교를 해서 자리를 교환하며 정렬

 

void bubbleSort(int [] arr){
int temp=0;
for(int i=0; i< arr.length; i++){
for(int j=1; j<arr.length-i; j++){
if(arr[j-1]>arr[j]){
temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
}
System.out.println(Arrays.toString(arr));

 

특징
시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 입니다
공간복잡도는 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
안정 정렬(Stable Sort) 입니다.
시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다.

----------------------------------------------------------------------------------------------------------------------------------------------------------

선택정렬

Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

 

선택한 원소 뒤에 있는 원소들중 가장 작은 값을 찾아 위치를 교환한다.

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

선택정렬

 

데이터의 개수가 n개라고 했을 때,

  • 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
  • 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
  • ...
  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸립니다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일합니다.

  • 불안정 정렬(Unstable Sort) 입니다.

삽입 정렬 (Insertion Sort)

 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘

 

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도

안정 정렬(Stable Sort)

 

 

퀵정렬

  1. 피벗 선택
  2. 오른쪽(j)에서 왼쪽으로 가면서 피벗보다 작은 수 찾음
  3. 왼쪽(i)에서 오른쪽으로 가면서 피벗보다 큰 수 찾음
  4. 각 인덱스 i, j에 대한 요소를 교환
  5. 2,3,4번 과정 반복
  6. 더이상 2,3번 진행이 불가능하면, 현재 피벗과 교환
  7. 이제 교환된 피벗 기준으로 왼쪽엔 피벗보다 작은 값, 오른쪽엔 큰 값들만 존재함

 

최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도

안정 정렬(Stable Sort)

 

 

private void solve() {
    int[] array = { 80, 70, 60, 50, 40, 30, 20 };
    quicksort(array, 0, array.length - 1);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static int partition(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    swap(array, left, mid);
 
    int pivot = array[left];
    int i = left, j = right;
 
    while (i < j) {
        while (pivot < array[j]) {
            j--;
        }
 
        while (i < j && pivot >= array[i]) {
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;
    return i;
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[b];
    array[b] = array[a];
    array[a] = temp;
}
 
public static void quicksort(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
 
    int pi = partition(array, left, right);
 
    quicksort(array, left, pi - 1);
    quicksort(array, pi + 1, right);
}

불안정 정렬이다.

 

 

합병정렬

시간복잡도 평균 nlogn, 최선nlogn 최악 nlogn

 

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유

public void mergeSort(int[] array, int left, int right) {
    
    if(left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }
    
}
public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
    
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
    
    while(i < ll && j < rl) {
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }
    
    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

힙정렬

 

시간복잡도 평균 nlogn, 최선nlogn 최악 nlogn

완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식

 

힙 소트가 유용할 때

  • 가장 크거나 가장 작은 값을 구할 때
  • 최소 힙 or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능
  • 최대 k 만큼 떨어진 요소들을 정렬할 때
  • 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있음

private void solve() {
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };
 
    heapSort(array);
 
    for (int v : array) {
        System.out.println(v);
    }
}
 
public static void heapify(int array[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
 
    if (l < n && array[p] < array[l]) {
        p = l;
    }
 
    if (r < n && array[p] < array[r]) {
        p = r;
    }
 
    if (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
 
public static void heapSort(int[] array) {
    int n = array.length;
 
    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }
 
    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}
 
public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

DFS & BFS

DFS
루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법

  • 모든 경로를 방문해야 할 경우 사용에 적합

시간 복잡도

  • 인접 행렬 : O(V^2)
  • 인접 리스트 : O(V+E)
  •  
  • // 시적 정점 v
	static boolean[] visit;
    //연결 리스트, 행렬 그래프 중 선택
	static LinkedList<Integer>[] graph;
	static int[][] graph;
    
	public static void dfs(int v) {
		visit[v] = true;
		System.out.println(v);
		for(int nextV : graph[v]) {
			if(!visit[nextV]) dfs(nextV);
		}
	}

 

BFS

루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법

큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문)

	static boolean[] visit;
    //연결 리스트, 행렬 그래프 중 선택
	static LinkedList<Integer>[] graph;
	static int[][] graph;
    
// 시작 정점 v
	public static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(v); //시작 정점 큐에 넣기
		visit[v] = true; //시작 정점 방문
		
		while(!queue.isEmpty()) {
			int temp = queue.poll(); 
			System.out.println(temp);

			for(int nextV : graph[temp]) {
				if(!visit[nextV]) { 
					queue.add(nextV);
					visit[nextV] = true;
				}
			}
		}		
	}

동적 계획법 (Dynamic Programming)

똑같은 연산을 반복하지 않도록 만들어준다.

 

  • 작은 문제에서 반복이 일어남
  • 같은 문제는 항상 정답이 같음

 ex)

피보나치 구현에 재귀를 활용했다면 시간복잡도는 O(2^n)이지만, 동적 계획법을 활용하면 O(N)으로 해결할 수 있다.

 

https://www.acmicpc.net/problem/2579 계단오르기

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
 
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
int N = Integer.parseInt(br.readLine());
 
int[] DP = new int[N + 1];
int[] arr = new int[N + 1];
 
 
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
 

DP[1] = arr[1];


if (N >= 2) {
DP[2] = arr[1] + arr[2];
}
 
for (int i = 3; i <= N; i++) {
DP[i] = Math.max(DP[i - 2] , DP[i - 3] + arr[i - 1]) + arr[i];
}
 
System.out.println(DP[N]);
 
}
 
}

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다

  • 해당 정점까지의 최단 거리를 저장
  • 정점을 방문했는 지 저장

최단 거리 값은 무한대 값으로 초기화한다.

시작 정점의 최단 거리는 0이다. 그리고 시작 정점을 방문 처리한다.

시작 정점과 연결된 정점들의 최단 거리 값을 갱신한다.

방문하지 않은 정점 중 최단 거리가 최소인 정점을 찾는다.

찾은 정점을 방문 체크로 변경 후, 해당 정점과 연결된 방문하지 않은 정점의 최단 거리 값을 갱신한다. 모든 정점을 방문할 때까지 4~5번을 반복한다.

 

참고 : https://github.com/gyoogle/tech-interview-for-developer

'카테고리 없음'의 다른글

  • 현재글알고리즘

티스토리툴바