Today I Learned
코테를 준비하면서 여러 알고리즘을 배우고 있다. 슬슬 여러 알고리즘들이 머리 속에서 섞이면서 헷갈리는 순간이 와서 한번 정리를 해보려 한다.
알고리즘 정리
DP (동적계획법)
어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 저장해 활용하는 방식. 답을 재활용 하는 것.
-
큰 문제를 위에서부터 작은 문제로 나누는 Top-Down / 작은 문제를 해결해가며 아래서부터 순차적으로 올라가는 Bottom-Up으로 나뉜다.
-
코드 예시(bottom-up)
public class A_DP_피보나치 {
static long fiboBottomUp(int n) {
long[] dp = new long[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
public static void main(String[] args) {
int n = 10;
System.out.println(fiboBottomUp(n)); // 55
}탐색
순차 탐색
선형 데이터 구조에서 원하는 값을 찾기위해 처음부터 순서대로 탐색하는 방법
- 시간복잡도는 O(n) / for문으로 순회한다.
이진 탐색
선형 데이터 구조에서 원하는 값을 찾기위해 탐색 범위를 절반씩 계속 나눠 탐색하는 방법
-
반드시 정렬이 되어 있어야 한다.
-
시간복잡도는 O(log n)
-
코드 예시
private static int binarySearch(int[] array, int target){
int low = 0;
int high = array.length-1;
while (low <= high){
int mid = (low + high) / 2;
if (array[mid] == target){
return mid;
} else if (array[mid] < target){
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}투 포인터
선형 자료구조에서 두 개의 포인터를 사용해 원하는 요소를 찾는 기법
-
일반적으로 정렬된 데이터에서 두개의 포인터를 시작/끝에 두고 탐색을 한다.
-
배열을 한 번만 순회하므로 시간복잡도는 O(n)
-
코드 예시
int[] arr = {15,3,11,5,7,1,4};
Arrays.sort(arr);
int target = 12;
int l = arr.length;
int left = 0;
int right = l - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
System.out.println(left + " " + right);
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}슬라이딩 윈도우
선형자료구조에서 연속된 요소의 부분집합을 효과적으로 탐색할 때 사용하는 기법
-
부분배열의 크기는 고정되어있지만 배열상에서 좌표만 움직인다.
-
정렬된 배열에서 효과적이며, 시간복잡도는 O(n)이다.
-
코드 예시
public int minSubArrayLen(int k, int[] nums) {
int minLength = Integer.MAX_VALUE; // 결과 저장
int sum = 0; // 윈도우 내부의 합
int left = 0; // 슬라이딩 윈도우의 왼쪽 포인터
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= k) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
public static void main(String[] args) {
int[] nums = {2, 3, 1, 2, 4, 3};
int k = 7;
System.out.println(new ClassName().minSubArrayLen(k, nums)); // 결과는 2 ([4,3]이 가장 짧은 부분 배열)
}백트래킹
모든 경우의 수를 고려하는 알고리즘 중 하나. 해를 찾는 도중 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 가능성을 탐색하는 방법
DFS
-
트리나 그래프에서 모든 루트를 완전 탐색하고자 할 때, 최대한 깊게 들어가서 확인한 뒤 다른 루트를 찾는 방법
-
이미 방문한 곳은 체크를 해둬 중복 순회하지 않도록 해야한다.
-
재귀, 스택으로 구현한다.
-
코드 예시
public class A_DfsR {
private static boolean[] checked;
private static int[][] graph = {{},
// ... 생략
};
public static void dfs(int v){
checked[v] = true;
System.out.println(v + "번 노드를 탐색합니다.");
for (int i : graph[v]){
if (!checked[i]) dfs(i);
}
}
public static void main(String[] args) {
int start = 1; // 시작노드
checked = new boolean[11];
dfs(start);
}
}BFS
루트노드에서 시작해 깊이가 같은 노드를 모두 방문해 한 단계씩 더 깊은 노드로 방문해가는 방식
-
모든 분기점을 다 검사하면서 진행한다. / 중복 순회하지 않도록 방문여부를 체크해야 한다.
-
큐를 이용해 구현한다.
-
코드 예시
public class A_BfsQ {
private static boolean[] checked = new boolean[11];
private static int[][] graph = {{},
// ... 생략
};
public static void bfs(int v){
checked[v] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(v);
while(!queue.isEmpty()){
int tmp = queue.poll();
System.out.println(tmp + "번 노드를 탐색합니다.");
for (int i : graph[tmp]){
if(!checked[i]){
queue.add(i);
checked[i] = true;
}
}
}
}
public static void main(String[] args) {
int start = 1; // 시작노드
bfs(start);
}
}