기술 면접 준비 (2) - Algorithm-2

작성일 | In |

모든 글은 다음 블로그를 참고하여 작성하였습니다.
https://gyoogle.dev/blog/

Binary Search

진행순서

  • 우선 정렬을 해야 함
  • left와 right로 mid값 설정
  • mid와 내가 구하고자 하는 값 비교
  • 구할 값이 mid보다 크면 -> left = mid+1
  • 구할 값이 mid보다 작으면 -> right = mid-1
  • left > right가 되면 종료

Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자

    Arrays.sort(arr); // 정렬

	int start = 0; // 시작
	int end = arr[arr.length-1]; // 끝

	while(start <= end) {

		int sum = 0;
		int mid = (start+end)/2; // 시작과 끝의 중간값

		for (int i = 0; i < arr.length; i++) {
			if(arr[i] > mid)
				sum+=mid;
			else
				sum+=arr[i];
		}

		if(sum > M)
			end = mid - 1;
		else
			start = mid + 1;

	}

	return end;
}

Hash Table

다음에 다시 공부해보기

DFS & BFS

DFS

  • 스택 or 재귀함수를 통해 구현한다.
  • 모든 경로를 방문해야 할 경우 사용에 적합 dfs
  • 시간 복잡도
    • 인접 행렬 : O(V^2)
    • 인접 리스트 : O(V+E)

      V는 접점, E는 간선을 뜻한다.

BFS

  • 큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문)
  • 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합 bfs
  • 시간 복잡도
    • 인접 행렬 : O(V^2)
    • 인접 리스트 : O(V+E)

      V는 접점, E는 간선을 뜻한다.

최장 증가 수열 (Longest Increasing Sequence, LIS)

최장 증가 수열 : 가장 긴 증가하는 부분 수열

시간복잡도

  • DP : O(N^2)
  • Lower Bound : O(NlogN)

Source Code (With DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
}

// 저장된 dp 배열 값 : [0, 0, 1, 2, 2, 3]
// LIS : dp배열에 저장된 값 중 최대 값 + 1

최소 공통 조상 (Lowest Common Ancestor) 알고리즘

최소 공통 조상 찾는 알고리즘 -> 두 정점이 만나는 최초 부모 정점을 찾는 것

  • 예시 LCA

찾는 방법

  • 해당 정점의 depth와 parent를 저장해두는 방식이다. 현재 그림에서의 depth는 아래와 같을 것이다.
1
2
3
4
[depth : 정점]
0 → 1(root 정점)
1 → 2, 3
2 → 4, 5, 6, 7
  • parent는 정점마다 가지는 부모 정점을 저장해둔다. 위의 예시에서 저장된 parent 배열은 아래와 같다.
1
2
// 1 ~ 7번 정점 (root는 부모가 없기 때문에 0)
int parent[] = {0, 1, 1, 2, 2, 3, 3}
  • 이제 두 배열을 활용해서 두 정점이 주어졌을 대 LCA를 찾을 수 있다.
1
2
3
4
5
6
7
8
// 두 정점의 depth 확인하기
while(true){
	if(depth가 일치)
		if(두 정점의 parent 일치?) LCA 찾음(종료)
        else 두 정점을 자신의 parent 정점 값으로 변경
    else // depth 불일치
        더 depth가 깊은 정점을 해당 정점의 parent 정점으로 변경(depth가 감소됨)
}