알고리즘 정리

📚 정렬 알고리즘

📙 버블 정렬

• 서로 인접한 두 원소의 대소 비교
• 시간 복잡도 n^2 공간 복잡도 n

📙 선택 정렬

• 원소를 넣을 위치는 정해져 있고 어떤 원소를 넣을지 선택
• 시간 복잡도 n^2 공간 복잡도 n

📙 삽입 정렬

• 2번째 원소부터 시작해 그 앞 원소들과 비교하여 삽입할 위치 정함
• 시간 복잡도 n^2 공간 복잡도 n

📙 퀵 정렬

• 분할 정복 방법을 이용해 주어진 배열 정렬
• 배열 가운데서 하나의 pivot 정하고 pivot기준으로 분할하여 정렬한다
• 시간복잡도 n log n, 공간복잡도 n

📙 병합 정렬

• 퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
• 합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)
  *LinkedList 정렬이 필요할 때 사용하면 효율적임

📙 힙 정렬

• 완전 이진트리를 기본으로 하는 힙 자료구조 기반 정렬 방식
• 우선순위 큐 같은 경우가 힙 정렬을 사용함
• 시간복잡도 n log n

📙 DFS, BFS

• DFS : 스택 또는 재귀함수 -> 모든 경로를 방문해야 할 경우에 적합하다.
• BFS : 큐를 통해 구현한다 -> 최소비용에 적합하다.

📙 최장 증가 수열

• DP를 이용해 구현 -> 시간 복잡도가 n^2

int arr[] = {7, 2, 3, 8, 4, 5};
int dp[] = new int[arr.length]; // LIS 저장 배열

for(int i = 1; i < dp.length; i++) {
    for(int j = i-1; j>=0; j--) {
        if(arr[i] > arr[j]) {
            dp[i] = (dp[i] < dp[j]+1) ? dp[j]+1 : dp[i];
        }
    }
}

for (int i = 0; i < dp.length; i++) {
	if(max < dp[i]) max = dp[i];
}

• n^2로 해결할 수 없는 경우 LIS 구현

📙 최소 공통 조상 알고리즘

• 두 정점이 만나는 최초 부모 정점을 찾는 것
• 해당 점점의 depth와 Parent를 저장하는 방식

while(true){
	if(depth가 일치)
		if(두 정점의 parent 일치?) LCA 찾음(종료)
        else 두 정점을 자신의 parent 정점 값으로 변경
    else // depth 불일치
        더 depth가 깊은 정점을 해당 정점의 parent 정점으로 변경(depth가 감소됨)
}

📙 동적 계획법(DP)

• Optimal Substructure : 답을 구하기 위해 이미 했던 똑같은 계산을 반복하는 경우
• 피보나치 수열의 경우 생각해보면 쉽다
• 보통 작은 문제부터 해결해나가는 것이 좋다.
• DP를 활용한 알고리즘 : 다익스트라 알고리즘
  • 최단 거리 값을 무한대로 초기화
  • 시작 정점의 최단거리는 0 + 방문처리
  • 시작 정점과 연결된 정점의 최단 거리 값 갱신
  • 방문하지 않은 정점 중 거리가 최소인 정점을 찾는다.
  • 방문 체크 후 최단 거리 값 갱신부터 반복
  • 인접 리스트로 구현시 시간 복잡도는 n log n

📙 외판원 순회 문제

• DP + DFS 문제
• 모든 도시를 최소 비용으로 한 번씩만 방문하여 처음 도시로 돌아와야 한다.
• 항상 최적의 경로가 존재한다
• 시작 정점과 상관없이 찾을 수 있다.
• dp[현재노드][방문한 노드] -> 최소값 저장 -> 방문한 노든는 bitmask이용