알고리즘 개요

DP

복잡한 문제를 간단한 여러 하위문제로 나누어 푸는 방법

두가지 구현방식이 존재함

top-down
- 여러개의 하위문제로 나누고, 하위문제를 푼 다음, 그것들을 결합하여 최종적으로 최적해를 구한다.
- 이때 하위문제로 나눌때 같은 하위문제를 가지고 있는 경우가 있다. 이때의 최적해를 저장해서 사용하여 같은 하위문제를 다시 풀지 않도록 하는 방법을 메모이제이션이라고 한다.
bottom-up
- 하위문제들의 해로 상위문제의 최적해를 구한다.

피보나치 예시

top-down
f (int n) {
  if n == 0 : return 0
  elif n == 1: return 1

  if dp[n] has value : return dp[n]
  else : dp[n] = f(n-2) + f(n-1)
         return dp[n]
}

bottom-up
f (int n){
  f[0] = 0
  f[1] = 1
  for (i = 2; i <= n; i++) {
   f[i] = f[i-2] + f[i-1]
  }
  return f[n]
}

접근방법

모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분문제 정의를 변경한다.
재귀 호출의 입력 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다.
입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션을 할 수 있도록 조정한다.
메모이제이션을 적용한다.

그리디

각 단계마다 지금 당장 가장 좋은 방법만을 선택해나가는 방법.

접근 방법

문제의 답을 만드는 과정을 여러 조각으로 나눈다.
각 조각마다 어떤 우선순위로 선택을 내려야할지 결정한다.
다음 두 속성이 적용되는지 확인해본다.
1. 탐욕적 선택 속성 : 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재하는가
2. 최적 부분구조 : 각 단계에서 항상 최적의 선택만을 했을 때, 전체 최적해를 구할 수 있는가

Sorting algorithm

Bubble sort

인접한 두개의 데이터를 비교해가면서 정렬을 진행하는 방식. 매 회차마다 가장 큰 값이 맨 끝으로 이동된다.

Space Complexity	Time Complexity
O(1)	O(n^2)

Selection Sort

정렬되지 않은 원소 중 가장 작은 값(혹은 가장 큰 값)을 고르고, 해당하는 위치로 교환해주는 방식

Space Complexity	Time Complexity
O(1)	O(n^2)

Insertion Sort

i 번째를 정렬할 순서라고 가정하면, 0 부터 i-1 까지의 원소들은 정렬되어있다는 가정하에, i 번째 원소와 i-1 번째 원소부터 0 번째 원소까지 비교하면서 i 번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서의 원소와 비교하면서 정렬해준다.

Space Complexity	Time Complexity
O(1)	O(n^2)

Merge Sort

더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우 반환한다. 이 때 반환한 값끼리 combine하면서, 비교가 이뤄지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다.

Space Complexity	Time Complexity
O(n)	O(nlogn)

Heap Sort

binary heap 자료구조를 이용한 정렬방법

두가지 방법

정렬의 대상인 데이터들을 힙에 넣었다가 꺼내며 정렬
기존의 배열을 힙으로 만든 다음에 꺼내어 정렬

heap에 데이터를 저장하는 시간은 O(logn)이고, 삭제 시간은 O(log n)이다.

Space Complexity	Time Complexity
O(1)	O(nlogn)

Quick sort

가장 빠르지만, 최악의 경우 O(n^2)의 시간복잡도를 가짐. 하지만 constant factor가 작아서 속도가 빠르다.

분할 정복전략을 사용.

Divide 과정에서 pivot이라는 개념이 사용된다. 오름차순으로 정렬한다고 하면, 이 pivot 을 기준으로 좌측은 pivot 보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partition된다. 이렇게 나뉜 좌, 우측 각각의 배열을 다시 재귀적으로 Quick Sort 를 시키면 또 partition 과정이 적용된다.이 때 한 가지 주의할 점은 partition 과정에서 pivot 으로 설정된 값은 다음 재귀과정에 포함시키지 않아야 한다. 이미 partition 과정에서 정렬된 자신의 위치를 찾았기 때문이다.

Worse case

pivot이 항상 가장 작은값 또는 가장 큰 값으로 선택되면, 한쪽으로 치우친 분할이 일어나게되고, O(n) 깊이를 갖게 된다.

Balanced-partitioning

배열 내의 원소 중 임의의 원소를 pivot으로 설정하면 입력에 관계없이 일정한 수준의 성능을 얻을 수 있다고 함.

partitioning

가장 마지막 원소를 pivot 으로 설정했다고 가정하자.

이 pivot 은 움직이지 말자. 첫번째 원소부터 비교하는데 만약 그 값이 pivot 보다 작다면 그대로 두고, 크다면 맨 마지막에서 그 앞의 원소와 자리를 바꿔준다. 즉 pivot value 의 index 가 k 라면 k-1 번째와 바꿔주는 것이다.

이것을 모든 원소에 대해 실행하고 마지막 과정에서 작은 값들이 채워지는 인덱스를 가리키고 있는 값에 1 을 더한 index 값과 pivot 값을 바꿔준다. 즉, 최종적으로 결정될 pivot 의 인덱스를 i 라고 했을 때, 0 부터 i-1 까지는 pivot 보다 작은 값이 될 것이고 i+1 부터 k 까지는 pivot 값보다 큰 값이 될 것이다.

Space Complexity	Time Complexity
O(log(n))	O(nlogn)

Non-comparisons Sorting algorithm

Counting sort

범위와 타입이 정해져있는 입력에서, 각 값이 몇 번 나왔는지 세어 정렬하는 방법이다.

점수와 같이 0~100 으로 구성되는 좁은 범위에 존재하는 데이터들을 정렬할 때 유용하게 사용할 수 있다.

Space Complexity	Time Complexity
O(n)	O(n)

Radix Sort

입력의 데이터의 길이가 동일할때 사용하는 방법.

하나의 기수마다 하나의 버킷을 생성하여, 분류를 한 뒤에, 버킷 안에서 또 정렬을 하는 방식이다.

두가지 방식으로 나뉨

LSD(Least Significant Digit) : 일의 자리부터 정렬. 주로 사용됨. 중간 정렬 결과를 확인할 수 없음. 끝가지 되야지만 정렬이 됨.
MSD(Most Significant Digit) : 가장 큰 자리부터 정렬. 중간 정렬결과를 확인할 수 있음.

MSD는 중간정렬를 확인할 수 있으나, 정렬이 완료됐는지 확인하는 과정이 필요하고 여기에 메모리가 더 소요된다. 따라서 일반적으로 LSD를 사용

Space Complexity	Time Complexity
O(n)	O(n)

에라토스테네스의 체

만일 100 이하의 소수를 모두 찾고 싶다면, 1 부터 100 까지의 자연수를 모두 나열한 후, 먼저 소수도 합성수도 아닌 1을 지우고, 2외의 2의 배수들을 다 지우고, 3외의 3의 배수들을 다 지우는 과정을 100제곱근인 10이하의 소수들에 대해서만 반복하면, 이때 남은 수들이 구하고자 하는 소수들이다.

Space Complexity	Time Complexity
O(n)	O(loglogn)

	int num1, num2;
	int arr[MAX] = { 0,1 };

	scanf("%d %d", &num1, &num2);

	for (int i = 2; i <= num2; i++)
	{
		for (int j = 2; i * j <= num2; j++)
			arr[i * j] = 1;
	}

	for (int i = num1; i <= num2; i++)
	{
		if (!arr[i])
			printf("%d\n", i);
	}

출처

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Algorithm