1. 정렬 알고리즘 (Sorting Algorithms)
버블 정렬 (Bubble Sort)
- 기본 개념 : 인접한 두 요소를 비교하여 큰 값을 뒤로 보냄. 이 과정을 반복하여 정렬
- 장점 : 구현이 매우 간단함
- 단점 : 매우 비효율적. 시간 복잡도가 높아 큰 데이터셋에는 적합하지 않음
- 시간 복잡도 : O(n^2)
- 사용 예시 : 단순한 교육용 예제, 데이터가 매우 적을 때
public void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}삽입 정렬 (Insertion Sort)
- 기본 개념 : 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 요소를 하나씩 꺼내어 정렬된 부분에 삽입
- 장점 : 구현이 간단하고, 대부분의 요소가 이미 정렬된 경우 효율적
- 단점 : 시간 복잡도가 높아 큰 데이터셋에는 적합하지 않음
- 시간 복잡도 : O(n^2)
- 사용 예시 : 작은 데이터셋, 대부분 정렬된 데이터
public void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}선택 정렬 (Selection Sort)
- 기본 개념 : 가장 작은 요소를 찾아 정렬되지 않은 부분의 맨 앞에 놓음. 이 과정을 반복
- 장점 : 구현이 간단함
- 단점 : 시간 복잡도가 높아 큰 데이터셋에는 적합하지 않음
- 시간 복잡도 : O(n^2)
- 사용 예시 : 단순한 교육용 예제, 데이터가 매우 적을 때
public void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}병합 정렬 (Merge Sort)
- 기본 개념 : 배열을 반으로 나누어 각각을 정렬한 후 병합. 분할 정복 기법을 사용
- 장점 : 안정 정렬, 시간 복잡도가 항상 일정함
- 단점 : 추가적인 메모리 공간이 필요
- 시간 복잡도 : O(n log n)
- 사용 예시 : 안정 정렬이 필요할 때, 대용량 데이터
public void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
public void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[middle + 1 + j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}퀵 정렬 (Quick Sort)
- 기본 개념 : 피벗을 선택해 배열을 분활하고, 각 부분을 재귀적으로 정렬
- 장점 : 평균적으로 매우 빠름
- 단점 : 최악의 경우 시간 복잡도가 높음(하지만 최악의 경우는 거의 발생X)
- 시간 복잡도 : O(n log n), 최악 O(n^2)
- 사용 예시 : 대용량 데이터, 일반적인 정렬 작업
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}힙 정렬 (Heap Sort)
- 기본 개념 : 힙 자료구조를 이용해 정렬. 이진 힙을 사용해 최대 힙이나 최소 힙을 구성
- 장점 : 추가 메모리 사용이 적음
- 단점 : 비교적 느릴 수 있음
- 시간 복잡도 : O(n log n)
- 사용 예시 : 메모리 사용이 중요한 경우
public void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}2. 탐색 알고리즘 (Searching Algorithms)
선형 탐색 (Linear Search)
- 기본 개념 : 배열의 첫 요소부터 순차적으로 탐색
- 장점 : 구현이 간단하고, 데이터가 정렬될 필요가 없음
- 단점 : 시간 복잡도가 높음
- 시간 복잡도 : O(n)
- 사용 예시 : 데이터가 적거나, 정렬되지 않은 배열
public int linearSearch(int[] arr, int x) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}이진 탐색 (Binary Search)
- 기본 개념 : 정렬된 배열에서 중간 요소를 기준으로 반씩 나누어 탐색
- 장점 : 매우 빠름
- 단점 : 배열이 정렬되어 있어야 함
- 시간 복잡도 : O(log n)
- 사용 예시 : 정렬된 배열에서의 탐색
public int binarySearch(int[] arr, int x) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}3. 그래프 알고리즘 (Graph Algorithms)
깊이 우선 탐색 (DFS, Depth - First Search)
- 기본 개념 : 한 정점에서 시작해 갈 수 있는 한 깊이 들어가며 탐색
- 장점 : 구현이 간단하고, 경로를 쉽게 찾을 수 있음
- 단점 : 스택 오버플로우의 위험이 있음
- 시간 복잡도 : O(V + E) (V : 정점의 수, E : 간선의 수)
- 사용 예시 : 경로 찾기, 미로탐색
public void DFS(int v, boolean[] visited, List<List<Integer>> adjList) {
visited[v] = true;
System.out.print(v + " ");
for (int i : adjList.get(v)) {
if (!visited[i]) {
DFS(i, visited, adjList);
}
}
}너비 우선 탐색 (BFS, Breadth - First Search)
- 기본 개념 : 한 정점에서 시작해 인접한 모든 정점을 탐색한 후, 다음 레벨로 넘어감
- 장점 : 최단 경로를 찾을수 있음
- 단점 : 큐가 필요하며, 메모리 사용이 많을 수 있음
- 시간 복잡도 : O(V + E) (V : 정점의 수, E : 간선의 수)
- 사용 예시 : 최단 경로 찾기
public void BFS(int start, int V, List<List<Integer>> adjList) {
boolean[] visited = new boolean[V];
LinkedList<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (queue.size() != 0) {
start = queue.poll();
System.out.print(start + " ");
for (int i : adjList.get(start)) {
if (!visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}다익스트라 알고리즘 (Dijkstra`s Algorithm)
- 기본 개념 : 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾음
- 장점 : 음의 가중치가 없는 그래프에서 최적
- 단점 : 음의 가중치를 처리할 수 없음
- 시간 복잡도 : O(V^2) 또는 O(E log V) (우선순의 큐 사용시)
- 사용 예시 : 네트워크 라우팅
public int[] dijkstra(int V, List<List<Node>> adjList, int start) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(V, new Node());
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
int u = pq.poll().node;
for (Node neighbor : adjList.get(u)) {
int v = neighbor.node;
int weight = neighbor.cost;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new Node(v, dist[v]));
}
}
}
return dist;
}
class Node implements Comparator<Node> {
public int node, cost;
public Node() {}
public Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compare(Node n1, Node n2) {
return Integer.compare(n1.cost, n2.cost);
}
}벨만 - 포드 알고리즘 (Bellman - Ford Algorithm)
- 기본 개념 : 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾음
- 장점 : 음의 가중치를 처리할 수 있음
- 단점 : 시간 복잡도가 높음
- 시간 복잡도 : O(VE)
- 사용 예시 : 음의 가중치가 있는 그래프에서의 최단 경로
public void bellmanFord(int V, int E, int[][] edges, int start) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int i = 0; i < V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = edges[j][0];
int v = edges[j][1];
int weight = edges[j][2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
for (int j = 0; j < E; j++) {
int u = edges[j][0];
int v = edges[j][1];
int weight = edges[j][2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
}
}
}플로이드 - 워셜 알고리즘 (Floyd - Warshall Algorithm)
- 기본 개념 : 모든 정점 간의 최단 경로를 찾음
- 장점 : 음의 가중치도 처리할 수 있음
- 단점 : 시간 복잡도가 높음
- 시간 복잡도 : O(V^3)
- 사용 예시 : 모든 정점 간의 최단 경로 필요 시
public void floydWarshall(int V, int[][] graph) {
int[][] dist = new int[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}4. 분할 정복 (Divide and Conquer)
병합 정렬 (Merge Sort)
- 기본 개념 : 배열을 반으로 나누어 각각을 정렬한 후 병합
- 장점 : 안정 정렬, 시간 복잡도가 일정
- 단점 : 추가 메모리가 필요
- 시간 복잡도 : O(n log n)
- 사용 예시 : 안정 정렬이 필요할 때
ex) 코드는 <1. 정렬 알고리즘> 참조
퀵 정렬 (Quick Sort)
- 기본 개념 : 피벗을 선택해 배열을 분활하고, 각 부분을 재귀적으로 정렬
- 장점 : 평균적으로 매우 빠름
- 단점 : 최악의 경우 시간 복잡도가 높음(하지만 최악의 경우는 거의 발생X)
- 시간 복잡도 : O(n log n), 최악 O(n^2)
- 사용 예시 : 대용량 데이터, 일반적인 정렬 작업
ex) 코드는 <1. 정렬 알고리즘> 참조
최대 부분 배열 문제 (Maximum Subarray Problem)
- 기본 개념 : 분할 정복 기법을 사용하여 배열 내 최대 합을 갖는 부분 배열을 찾음
- 장점 : 효율적임
- 단점 : 구현이 복잡할 수 있음
- 시간 복잡도 : O(n log n)
- 사용 예시 : 주식 가격 변동 분석
public int maxSubArraySum(int[] arr, int left, int right) {
if (left == right) {
return arr[left];
}
int mid = (left + right) / 2;
return Math.max(Math.max(maxSubArraySum(arr, left, mid),
maxSubArraySum(arr, mid + 1, right)),
maxCrossingSum(arr, left, mid, right));
}
public int maxCrossingSum(int[] arr, int left, int mid, int right) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
for (int i = mid; i >= left; i--) {
sum += arr[i];
if (sum > leftSum) {
leftSum = sum;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
for (int i = mid + 1; i <= right; i++) {
sum += arr[i];
if (sum > rightSum) {
rightSum = sum;
}
}
return leftSum + rightSum;
}분할 정복 알고리즘의 장단점
- 장점
- 문제를 작은 부분으로 나누어 해결하기 때문에 복잡한 문제를 쉽게 해결할 수 있음.
- 재귀적 접근으로 코드가 간결해짐
- 특정 문제에 대해 시간 복잡도가 감소
- 단점
- 재귀 호출이 많아 스택 오버플로우가 발생할 수 있음
- 추가적인 메모리 공간이 필요할 수 있음
5. 그리디 알고리즘 (Greedy Algorithms)
그리디 알고리즘 개념
- 기본 개념 : 현재 상황에서 가장 좋아 보이는 선택을 함
- 장점 : 구현이 간단하고, 특정 문제에 대해 빠르게 최적해를 찾을 수 있음
- 단점 : 항상 최적해를 보장하지 않음
- 사용 예시 : 최소 스패닝 트리, 최단 경로 문제 (특정 경우), 활동 선택 문제
활동 선택 문제 (Activity Selection Problem)
- 기본 개념 : 시작 시간과 종료 시간이 주어진 활동 중 가장 많은 활동을 선택
- 시간 복잡도 : O(n log n) (정렬 포함)
- 사용 예시 : 스케줄링 문제
public void activitySelection(int[] start, int[] finish, int n) {
Arrays.sort(finish);
int i = 0;
System.out.print("Selected activities: " + i + " ");
for (int j = 1; j < n; j++) {
if (start[j] >= finish[i]) {
System.out.print(j + " ");
i = j;
}
}
}최소 스패닝 트리 (Minimum Spanning Tree)
크루스칼 알고리즘 (Kruskal`s Algorithm)
- 기본 개념 : 간선을 오름차순으로 정렬한 후, 최소 비용으로 연결
- 시간 복잡도 : O(E log E)
- 사용 예시 : 네트워크 연결 문제
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}
class Graph {
int V, E;
Edge[] edge;
Graph(int V, int E) {
this.V = V;
this.E = E;
edge = new Edge[E];
for (int i = 0; i < E; i++) {
edge[i] = new Edge();
}
}
int find(int[] parent, int i) {
if (parent[i] == i) {
return i;
}
return find(parent, parent[i]);
}
void union(int[] parent, int[] rank, int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot]) {
parent[xroot] = yroot;
} else if (rank[xroot] > rank[yroot]) {
parent[yroot] = xroot;
} else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
void KruskalMST() {
Edge[] result = new Edge[V];
int e = 0;
int i = 0;
for (i = 0; i < V; i++) {
result[i] = new Edge();
}
Arrays.sort(edge);
int[] parent = new int[V];
int[] rank = new int[V];
for (int v = 0; v < V; v++) {
parent[v] = v;
rank[v] = 0;
}
i = 0;
while (e < V - 1) {
Edge next_edge = edge[i++];
int x = find(parent, next_edge.src);
int y = find(parent, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
union(parent, rank, x, y);
}
}
for (i = 0; i < e; i++) {
System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
}
}
}6. 동적 계획법 (Dynamic Programming)
동적 계획법 개념
- 기본 개념 : 문제를 작은 부분 문제로 나누어, 그 결과를 저장하고 재활용
- 장점 : 중복 계산을 피할 수 있음.
- 단점 : 추가적인 메모리 공간이 필요
- 사용 예시 : 피보나치 수열, 배낭 문제, 최장 공통 부분 수열 (LCS)
피보나치 수열 (Fibonacci Sequence)
- 시간 복잡도 : O(n)
- 사용 예시 : 중복 계산을 피하기 위해
public int fibonacci(int n) {
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}배낭 문제 (Knapsack Priblem)
- 기본 개념 : 주어진 무게 제한 내에서 최대 가치를 갖는 물건을 선택
- 시간 복잡도 : O(nW) (n : 물건의 수, W : 무게 한도)
- 사용 예시 : 자원 할당 문제
public int knapSack(int W, int[] wt, int[] val, int n) {
int[][] K = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (wt[i - 1] <= w) {
K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
} else {
K[i][w] = K[i - 1][w];
}
}
}
return K[n][W];
}
Hello World