기본 알고리즘

▶ 트리

- 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조

- 트리의 크기가 N일 때, 간선의 크기는 N-1

- 이진 탐색 트리: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

▶ 이진 탐색 

- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

- 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

int binarySearch(int target, int start, int end)
{
	while (start <= end) {
		int mid = (start + end) / 2;
		if (t[mid] == target) return mid;
		else if (t[mid] > target) end = mid - 1;
		else start = mid + 1;
	}
	return -1;
}

- 직접 구현하지 않고 upper_bound / lower_bound 함수 사용 가능

int countByRange(int left, int right)
{
	vector<int>::iterator rIndex = upper_bound(v.begin(), v.end(), right);
	vector<int>::iterator lIndex = lower_bound(v.begin(), v.end(), left);
	return rIndex - lIndex;
}

- 예: LIS (최장증가수열) 에서 사용

dp[1] = a[1];
int index = 1;
for (int i = 2; i <= N; i++) {
	if (dp[index] < a[i]) {
		dp[++index] = a[i];
	}
	else {
		int search_idx = lower_bound(&dp[1], &dp[index], a[i]) - &dp[0];
		dp[search_idx] = a[i];
	}
}

- 탐색 범위가 10억 정도로 큰 경우, 이진 탐색을 떠올려야 함

 

▶ 소수

- 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어 떨어지지 않는 자연수

- 에라토스테네스의 체 

  - 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때

  - 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요

 

▶ 서로소 집합

- 공통 원소가 없는 두 집합

- 두 종류의 연산 필요: Union(합집합) - Find(찾기)

- 무방향 그래프에서 사이클 판별 시 사용

  - 참고) 방향 그래프에서는 DFS 를 이용해 사이클 여부 판별 가능

 

▶ 신장 트리

- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

- 예: N 개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 

      전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우

- 알고리즘: 크루스칼 알고리즘

- 모든 노드를 방문하지 못하는 경우, 간선의 개수가 N-1 이 아니다

 

▶ 위상 정렬

- 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열

- 진입차수(Indegree) 이용

- 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있다

 

▶ 최단 경로 문제

- 가장 짧은 경로를 찾는 알고리즘

- 종류:

  - 한 지점에서 다른 한 지점까지의 최단 경로

  - 한 지점에서 다른 모든 지점까지의 최단 경로

  - 모든 지점에서 다른 모든 지점까지의 최단 경로

1) 다익스트라

   - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로

   - 음의 간선이 없을 때 동작

   - 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

2) 플로이드 워셜

  - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

  - 각 단계마다 특정한 노드 k 를 거쳐 가는 경우를 확인

    . 2차원 배열 이용: D[a][b] = min(D[a][b], D[a][k] + D[k][b])

  - O(N^3) 이므로 문제에서 노드의 개수가 500을 넘지 않는다

 

▶ 투 포인터

- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리

- O(N^2) 이 아닌 O(N) 이내에서 처리해야 할 때

- 예: 특정한 합을 가지는 연속 수열 찾기

  1, 2, 3, 2, 5 => (합이 5인 경우) => 2,3 or 3,2 or 5

- 예: 구간 합 문제

  10, 20, 30, 40, 50 => (2~4번째 수의 합) 

  => 접두사 합(Prefix Sum): 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것

  0, 10, 30, 60, 100, 150 => Left=3, Right=4 => P[4]-P[3-1] = 70 

                                => Left=2, Right=5 => P[5]-P[2-1] = 140