Skip to content

Latest commit

 

History

History
284 lines (247 loc) · 9.56 KB

base.md

File metadata and controls

284 lines (247 loc) · 9.56 KB
Raw

1. 기본기

1.1 아스키 코드

최소한 A,Z,a,z정도는 기억해 둡시다

1.2 자주 사용되는 코드

1.2.1 character to integer

char c ='1';
int number = Character.getNumericValue(c);

1.2.2 숫자 역전 시키기

public static int reverse(int n) {
  int reverse = 0;
  while(n != 0) {
    reverse *= 10;
    reverse += (n % 10);
    n = n / 10;
  }
  return reverse;
}

1.2.3 문자열 역전 시키기

// 추가 공간을 사용하지 않는 방법 
public static String reverseString(String original) {
  char[] chs = original.toCharArray();
  int length = chs.length;
	    
  for(int i=0; i<length/2; i++) {
    // swap characters
    char tmp = chs[i];
    chs[i] = chs[length-1-i];
    chs[length-1-i] = tmp;
  }
  return new String(chs);
}

// 추가 공간을 사용 하는 방법
public static String reverseString(Strign original) {
  char[] chs = original.toCharArray();
  char[] result = new char[chs.length];
  
  for(int i=0; i<chs.length - 1; i++) {
    result[i] = chs[chs.length - i - 1];
  }
  return new String(result);
}

1.2.4 Swap

// 기본 스왑 
public void swap(int x, int y) {
  int tmp = x;
  x = y;
  y = tmp;
}

// XOR을 사용한 스왑 
// (피연산자의 수가 서로 다를 경우에만 1인 XOR의 성질을 이용해서 2진수로 풀어 계산 해보면 된다.)
public void swap(int x, int y) {
  x = x ^ y;
  y = x ^ y;
  x = x ^ y;
}

2. 정렬

2.1 Quick sort

  • 시간 복잡도 : 최악 O(n^2), 평균적으로 O(n log n)
  • 실행 설명
    a. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
    b. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
    c. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
    public static void quickSort(int[] arr, int low, int high) {
         if(low >= high) return;
         
         // pick the pivot
         int middle = low + (high - low) / 2;
         int pivot = arr[middle];
         
         // make left < pivot and right > pivot
         int i = low, j = high;
         while(i <= j) {
             while(arr[i] < pivot) {
                 i++;
             }
             while(arr[j] > pivot) {
                 j--;
             }
             if(i <= j) {
                 // swapping
                 int tmp = arr[i];
                 arr[i] = arr[j];
                 arr[k] = tmp;
                 i++;
                 j--;
             }
         }
         if(low < j) {
             quickSort(arr, low, j);
         }
         if(high > i) {
             quickSort(arr, i, high);
         }
     }
  • List구현체 버전 (참고)
 private List<Integer> quicksort(List<Integer> input){
		if(input.size() <= 1){
			return input;
		}
		
		int middle = (int) Math.ceil((double)input.size() / 2);
		int pivot = input.get(middle);

		List<Integer> less = new ArrayList<Integer>();
		List<Integer> greater = new ArrayList<Integer>();
		
		for (int i = 0; i < input.size(); i++) {
			if(input.get(i) <= pivot){
				if(i == middle){
					continue;
				}
				less.add(input.get(i));
			}
			else{
				greater.add(input.get(i));
			}
		}
		return concatenate(quicksort(less), pivot, quicksort(greater));
	}
	
	private List<Integer> concatenate(List<Integer> less, int pivot, List<Integer> greater){
		List<Integer> list = new ArrayList<Integer>();
		
		for (int i = 0; i < less.size(); i++) {
			list.add(less.get(i));
		}
		
		list.add(pivot);
		
		for (int i = 0; i < greater.size(); i++) {
			list.add(greater.get(i));
		}
		return list;
	}

2.2 Merge sort (병합, 합병 정렬)

  • 시간 복잡도 : O(n long n)
  • 공간 복잡도 : O(n)
  • 실행 설명
    a. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
    b. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    c. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    d. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
public class Mergesort {
        private int[] numbers;
        private int[] helper;

        private int number;

        public void sort(int[] values) {
                this.numbers = values;
                number = values.length;
                this.helper = new int[number];
                mergesort(0, number - 1);
        }

        private void mergesort(int low, int high) {
                // check if low is smaller then high, if not then the array is sorted
                if (low < high) {
                        // Get the index of the element which is in the middle
                        int middle = low + (high - low) / 2;
                        // Sort the left side of the array
                        mergesort(low, middle);
                        // Sort the right side of the array
                        mergesort(middle + 1, high);
                        // Combine them both
                        merge(low, middle, high);
                }
        }

        private void merge(int low, int middle, int high) {
                // Copy both parts into the helper array
                for (int i = low; i <= high; i++) {
                        helper[i] = numbers[i];
                }

                int i = low;
                int j = middle + 1;
                int k = low;
                // Copy the smallest values from either the left or the right side back
                // to the original array
                while (i <= middle && j <= high) {
                        if (helper[i] <= helper[j]) {
                                numbers[k] = helper[i];
                                i++;
                        } else {
                                numbers[k] = helper[j];
                                j++;
                        }
                        k++;
                }
                // Copy the rest of the left side of the array into the target array
                while (i <= middle) {
                        numbers[k] = helper[i];
                        k++;
                        i++;
                }
        }
}

3. 탐색

3.1 BFS (너비 우선 탐색)

  • 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.
  • 장점
    • 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
  • 단점
    • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
    • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
    • 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.
public static void bfs(int[][] mat, int startVertex) {
  Queue<Integer> queue = new LinkedList<>();
  boolean[] visited = new boolean[mat[startVertex].length];

  visited[startVertex] = true;
  queue.add(startVertex);

  int e = 0, i = 0;
  while(!queue.isEmpty()) {
    e = queue.remove();
    i = e;
    while(i <= mat[startVertex].length) {
      if(mat[e][i] == 1 && !visited[i]) {
        queue.add(i);
        visited[i] = true;
      }
      i++;
    }
  }
}

3.2 DFS (깊이 우선 탐색)

  • 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.
  • 장점
    • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
    • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
  • 단점
    • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
    • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
 int map[][], visit[];

void dfs(int vertexSize, int v) { 
  int i;
  visit[v] = 1; // root node
  for(i=1; i<=vertexSize; i++) {
    if(map[v][i] == 1 && !visit[i]) {
      dfs(i);
    }
  }
}