Java 알고리즘 개요
알고리즘은 문제를 해결하기 위한 절차나 방식을 일련의 규칙으로 표현한 것을 의미한다. Java 알고리즘은 이러한 알고리즘을 Java 언어로 구현한 것이다.
Java 알고리즘의 특징
Java 언어로 구현된 알고리즘은 객체 지향적 특성을 가지고 있으며, 가비지 컬렉션 기능으로 인해 메모리 관리가 편리하다. 또한, 플랫폼 독립성을 가지므로 다양한 환경에서 동일한 성능을 보장한다.
Java 알고리즘 예제
간단한 Java 알고리즘 예제로 ‘Hello, World!’를 출력하는 코드를 보자.
public class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello, World!");
}
}
위의 코드는 가장 기본적인 Java 알고리즘 예제로, “Hello, World!” 라는 문자열을 콘솔에 출력한다.
2. Java에서의 Stack과 Queue 이해
2.1 Stack 개념 및 특징
Stack은 자료구조 중의 하나로, 데이터를 입출력하는 방식이 후입선출(LIFO, Last In First Out) 형태를 따르는 선형 자료구조이다. 즉, 가장 마지막에 삽입된 요소가 가장 먼저 삭제되는 구조를 가지고 있다.
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3 출력
}
}
위의 코드는 Java에서 Stack을 사용하는 예시로, push 메소드를 통해 요소를 삽입하고, pop 메소드를 통해 요소를 삭제(복귀)한다.
2.2 Queue 개념 및 특징
Queue는 Stack과는 반대로 “선입선출”(FIFO, First In First Out) 형태를 가진 선형 자료구조이다. 가장 먼저 삽입된 요소가 가장 먼저 삭제되는 구조를 가지고 있다.
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 1 출력
}
}
위의 코드는 Java에서 Queue를 사용하는 예시로, offer 메소드를 이용하여 요소를 삽입하고, poll 메소드를 이용하여 요소를 삭제(복귀)한다.
3. Java에서 Stack 사용하기
3.1 Stack 클래스 사용방법
Java에서 Stack을 사용하기 위해서는 ‘java.util.Stack’ 클래스를 이용한다. 주로 사용하는 메서드는 다음과 같다.
– push(E item): 아이템을 Stack의 맨 위에 추가한다.
– pop(): Stack의 맨 위 아이템을 반환하고 이를 Stack에서 삭제한다.
– peek(): Stack의 맨 위 아이템을 반환하되 삭제하지는 않는다.
– empty(): Stack이 비어있는지 여부를 반환한다.
import java.util.Stack;
public class StackTest {
public static void main(String[] args) {
Stack stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek()); // 3 출력
while(!stack.empty()) {
System.out.println(stack.pop());
}
}
}
3.2 Stack을 활용한 알고리즘 예제
Stack은 후입선출(LIFO)의 특성을 이용하여 코딩에서 백트래킹, 백스페이스, 이전 페이지 등에 활용된다.
아래는 Stack을 이용한 괄호 검사 알고리즘의 예제이다.
import java.util.Stack;
public class ParenthesesCheck {
public static boolean checkParentheses(String exp) {
Stack stack = new Stack<>();
for (char c : exp.toCharArray()) {
switch (c) {
case '{':
case '(':
case '[':
stack.push(c);
break;
case ']':
if (stack.empty() || stack.pop() != '[') {
return false;
}
break;
case ')':
if (stack.empty() || stack.pop() != '(') {
return false;
}
break;
case '}':
if (stack.empty() || stack.pop() != '{') {
return false;
}
break;
}
}
return stack.empty();
}
public static void main(String[] args) {
System.out.println(checkParentheses("{()[]}")); // true 출력
}
}
이 코드는 주어진 문자열 내 괄호가 올바르게 닫혀있는지 검사하는 알고리즘이다. 괄호를 열 때는 스택에 괄호를 푸시하고, 닫을 때에는 스택에서 팝하여 괄호가 올바르게 짝을 이루는지 검사한다.
4. Java에서 Queue 사용하기
4.1 Queue 인터페이스 사용방법
Java에서 Queue를 사용하기 위해서는 ‘java.util.Queue’ 인터페이스를 이용한다. Queue 인터페이스를 구현한 대표적인 클래스로는 LinkedList, PriorityQueue 등이 있다. 주로 사용하는 메서드는 다음과 같다.
– offer(E e): 아이템을 Queue의 끝에 추가한다.
– poll(): Queue의 첫 아이템을 반환하고 이를 Queue에서 삭제한다.
– peek(): Queue의 첫 아이템을 반환하되 삭제하지는 않는다.
– isEmpty(): Queue가 비어있는지 여부를 반환한다.
import java.util.LinkedList;
import java.util.Queue;
public class QueueTest {
public static void main(String[] args) {
Queue queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek()); // 1 출력
while(!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}
4.2 Queue를 활용한 알고리즘 예제
Queue는 선입선출(FIFO)의 특성을 이용하여 코딩에서 순차적인 처리, 버퍼, 인쇄대기열 등에 활용된다.
아래는 Queue를 이용한 프린트 대기열 프로그램의 예제이다.
import java.util.LinkedList;
import java.util.Queue;
public class PrinterQueue {
public static void printDocument(Queue printer, String document) {
printer.offer(document);
}
public static void runPrinter(Queue printer) {
while(!printer.isEmpty()) {
System.out.println("Printing document: " + printer.poll());
}
}
public static void main(String[] args) {
Queue printer = new LinkedList<>();
printDocument(printer, "Document 1");
printDocument(printer, "Document 2");
printDocument(printer, "Document 3");
runPrinter(printer); // Document 1, Document 2, Document 3 순서대로 출력
}
}
이 코드는 주어진 문서를 프린터 대기열에 넣고 순차적으로 인쇄하는 프로그램이다. 문서를 프린트 대기열에 넣을 때는 offer 메서드를 사용하고, 문서를 인쇄할 때에는 poll 메서드를 사용한다.
5. Stack과 Queue 비교하기
5.1 성능 비교
Stack과 Queue 모두 Java 컬렉션 중 하나로, 리스트들의 특수한 종류다. Stack과 Queue는 둘 다 데이터를 저장하고 처리하는 방식이 특이하다는 공통점이 있다. 또한 두 자료구조 모두 삽입과 삭제에 대해 O(1)의 시간 복잡도를 가지므로 성능 차이는 거의 없다.
하지만, 이들의 차이는 데이터의 추가와 제거 방식에서 나타난다. Stack은 Last-In-First-Out (LIFO) 방식을, Queue는 First-In-First-Out(FIFO) 방식을 따른다.
5.2 사용 시점의 선택기준
1) Stack은 마지막에 삽입된 요소가 최초로 선택되어야 하는 경우에 사용된다. 이런 유형의 접근은 재귀 알고리즘, 백트래킹, 깊이 우선 탐색(DFS), 이전 페이지 기능 등에 주로 사용된다.
2) Queue는 먼저 삽입된 요소가 최초로 선택되어야 하는 경우에 사용된다. 이런 접근 방식은 너비 우선 탐색(BFS), CPU 스케줄링, 캐시 구현 등에 사용된다.
따라서, Stack과 Queue 사이에서 선택해야 할 때는 주로 문제의 특성과 요구 사항에 따라 결정된다.
// Stack의 LIFO 특성 예시
Stack stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3 출력
// Queue의 FIFO 특성 예시
Queue queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 1 출력
Stack은 가장 최근에 추가된 요소가 먼저 나오는 반면, Queue는 가장 먼저 추가된 요소가 먼저 나온다는 점이 확인될 수 있다.
6. 데이터 구조 선택 팁
데이터 구조를 선택할 때는 다음과 같은 기준을 고려해 볼 수 있다.
1) 필요한 연산의 종류
자료구조를 선택할 때는 어떤 연산이 필요한지를 고려해야 한다. 예를 들어, 만약 리스트의 중간에 데이터를 자주 삽입하거나 삭제해야 한다면 LinkedList가 ArrayList보다 훨씬 효율적일 수 있다. 또한 가장 먼저 추가된 요소를 선택해야 하는 경우 Queue를, 가장 마지막에 추가된 요소를 선택해야 하는 경우 Stack을 사용할 수 있다.
2) 데이터의 크기
데이터의 개수나 크기도 자료구조 선택에 영향을 줄 수 있다. 데이터가 많을수록 메모리 사용량이 늘어나므로, 데이터의 크기에 맞는 효율적인 자료구조를 선택하는 것이 중요하다.
3) 시간 복잡도와 공간 복잡도
데이터 구조는 다양한 연산에 대한 시간 복잡도와 공간 복잡도를 가지므로, 이들을 고려해서 선택해야 한다. 예를 들어, 배열이나 연결 리스트는 데이터의 삽입 및 삭제에 대해 서로 다른 시간 복잡도를 가진다.
아래는 Java에서 다양한 데이터 구조를 사용하는 예제 코드이다.
// ArrayList: 임의 접근에 용이
List list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
System.out.println(list.get(2)); // 인덱스 2의 요소 3 출력
// LinkedList: 중간 데이터의 삽입 및 삭제에 용이
List linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.remove(1); // 인덱스 1의 요소 삭제
System.out.println(linkedList); // [1, 3] 출력
// Stack: LIFO(Last In First Out) 구조
Stack stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); //마지막에 삽입된 요소 3 출력
// Queue: FIFO(First In First Out) 구조
Queue queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); //먼저 삽입된 요소 1 출력
7. Stack과 Queue의 변형 및 확장 개념
7.1 Deque
Deque(Deck)이란, Double Ended Queue의 약자로 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐를 일컫는다. 따라서 Stack과 Queue의 기능을 모두 가지고 있다고 보면 된다.
Deque의 주요 메소드로는 addFirst, addLast, removeFirst, removeLast 등이 있다.
Deque deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque.removeFirst()); // 1 출력 : 첫 번째 요소 제거
System.out.println(deque.removeLast()); // 2 출력 : 마지막 요소 제거
7.2 Priority Queue
Priority Queue는 Queue의 일종이지만, 단순히 FIFO 방식 대신에 요소의 우선 순위에 따라 요소를 반환하는 특징을 가진다. Java에서 PriorityQueue는 자동으로 어떤 기준에 따라(디폴트는 작은 순) 정렬하며, 이 기준은 Comparator를 통해 사용자가 정의하여 바꿀 수도 있다.
PriorityQueue priorityQueue = new PriorityQueue<>();
priorityQueue.offer(3);
priorityQueue.offer(1);
priorityQueue.offer(2);
System.out.println(priorityQueue.poll()); // 1 출력 : 가장 작은 요소부터 출력
System.out.println(priorityQueue.poll()); // 2 출력
System.out.println(priorityQueue.poll()); // 3 출력
PriorityQueue는 입구와 출구가 일정하지 않기 때문에, 우선순위에 따라 필요한 요소를 빠르게 얻을 수 있다. 따라서 데이터의 우선순위를 고려해야 하는 문제에서 주로 사용된다.
8. 변형 및 확장 개념 활용 알고리즘 예제
여러 데이터 구조의 변형 혹은 확장 개념을 활용한 예제로는 ‘슬라이딩 윈도우 알고리즘’을 들 수 있다. 슬라이딩 윈도우는 Deque를 활용한 알고리즘이며, 윈도우 즉, 일정 범위 내에서의 최대값 혹은 최소값 등을 효율적으로 구하는 문제에서 사용된다.
슬라이딩 윈도우 알고리즘 예제
아래 예시는 길이 n의 배열과 ‘윈도우 길이’ k가 주어졌을 때 가능한 모든 윈도우 범위 내에서의 최대값을 출력하는 문제이다.
void maxSlidingWindow(int[] nums, int k) {
Deque dq = new ArrayDeque<>();
int[] result = new int[nums.length - k + 1]; // 결과 저장 배열
for (int i = 0; i < nums.length; i++) {
// 이전 범위 밖의 값 지우기
if (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
dq.removeFirst();
// 범위 내에서 현재 요소보다 작은 요소들 제거
while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
dq.removeLast();
dq.offer(i);
// 출력 위치 도달 시 결과 배열에 최대값(배열의 현재 요소) 추가
if (i + 1 >= k)
result[i - k + 1] = nums[dq.peekFirst()];
}
// 결과 출력
for (int num : result)
System.out.println(num);
}
위 코드에서 Deque dq는 해당 범위에서 최대값의 인덱스를 유지하며, 새로운 요소가 추가될 때마다 Deque의 뒤에서부터 현재 요소보다 작은 요소들을 제거한다. 이렇게 관리하면 Deque의 첫번째 항목은 항상 해당 범위에서 최대값의 인덱스를 가리킨다.
9. 알고리즘 문제 풀이 팁
알고리즘 문제를 풀 때에는 몇 가지 중요한 팁들이 있다. 그 중에서도 기본적인 팁 중 하나는 ‘문제를 잘 이해하는 것’이다. 문제에 주어진 정보를 충분히 이해하고, 문제가 원하는 바가 무엇인지 파악하는 것이 중요하다. 이를 위해 문제를 여러 번 읽고, 주어진 입력과 출력을 꼼꼼히 확인해보는 것이 도움이 된다.
또 다른 팁은 어떤 데이터 구조를 사용할 것인지 고민하는 것이다. 문제의 요구사항에 따라 적절한 데이터 구조를 선택하고 활용하면 문제를 효율적으로 해결할 수 있다.
예제: 문제 이해와 데이터 구조 선택
아래의 예제 코드는 배열에서 두 요소의 합이 특정한 값을 갖는 모든 쌍을 찾는 문제를 해결한 것으로, 문제 이해와 데이터 구조 선택의 중요성을 보여준다.
void findPairs(int arr[], int sum) {
Set s = new HashSet();
for (int i = 0; i < arr.length; ++i) {
int temp = sum - arr[i];
// 'temp'가 set에 있으면 {arr[i], temp}은 원하는 쌍
if (s.contains(temp)) {
System.out.println("Pair with given sum " + sum + " is (" + arr[i] + ", " + temp + ")");
}
s.add(arr[i]);
}
}
이 예제에서는 해시 세트를 사용하여 주어진 수와 배열 원소의 차이 즉, 'temp'가 해시 세트에 이미 있는지 확인한다. 빠른 탐색을 위해 해시 세트를 사용하는 것이다. 이러한 방식으로 문제에 적합한 데이터 구조를 선택하고 활용하는 것이 알고리즘 문제 해결의 핵심이다.
10. 결론 및 추가 학습 자료
알고리즘과 데이터 구조는 모든 프로그래밍 문제의 핵심이다. 적절한 데이터 구조를 선택하고, 문제를 이해하고, 풀이법을 계획하고, 이를 코드로 깔끔하게 구현하는 능력을 갖추는 것이 중요하다. 이런 실력을 기르는 데에는 끊임없이 문제를 풀고 피드백을 받는 반복적인 연습이 필요하다.
추가 학습 자료
다양한 알고리즘과 데이터 구조 문제를 연습하고 풀이 접근법을 배울 수 있는 플랫폼에는 다음과 같은 것들이 있다.
1. LeetCode (https://leetcode.com/): 다양한 난이도의 알고리즘 문제가 있으며, 사용자들이 토론을 통해 서로의 풀이를 공유하는 공간이 있다.
2. HackerRank (https://www.hackerrank.com/): 초보자부터 고급 사용자를 위한 다양한 난이도의 문제가 있으며, 특정한 주제 혹은 기술에 초점을 둔 프로그래밍 문제들도 있다.
3. GeeksforGeeks (https://www.geeksforgeeks.org/): 알고리즘과 데이터 구조에 대한 풍부한 학습 자료와 문제가 있다.
다음은 분할정복 기법의 예제 중 하나인 퀵 정렬(Quick Sort)이다.
def partition(array, low, high):
i = (low - 1)
pivot = array[high]
for j in range(low, high):
if array[j] <= pivot:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[high] = array[high], array[i + 1]
return (i + 1)
def quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi - 1)
quickSort(array, pi + 1, high)
# Using the quicksort function
array = [10, 7, 8, 9, 1, 5]
quickSort(array, 0, len(array) - 1)
print("Sorted array is:", array)
이 코드는 퀵 정렬(Quick Sort) 알고리즘을 파이썬으로 구현한 것으로, 분할정복 기법의 등장하는 분할이 이루어지는 과정을 확인하실 수 있습니다.