스택
1. 스택이란?
-
스택(Stack)은 컴퓨터 과학에서 자주 사용되는 기본적인 데이터 구조 중 하나로, 마지막에 추가된 요소가 가장 먼저 제거되는 후입선출(Last In First Out, LIFO) 방식을 따른다.
-
스택 구현의 중요 키워드
- push : 값을 넣음(스택의 가장 위에 새로운 요소를 추가한다.)
- pop : 값을 꺼냄(스택의 가장 위에 있는 요소를 제거하고 그 값을 반환한다.)
- peek : 빼지는 않고 값만 알려줌
- top : 현재 가리키고 있는 인덱스
- isEmpty : 배열이 비어있는지 확인
- isFull : 배열이 꽉 차있는지 확인
-
웹 브라우저의 뒤로 가기 기능 / 함수 호출 시의 반환 주소 저장 / 괄호의 짝 맞춤 검사 등 다양한 알고리즘과 프로그램에서 사용된다.
2. 스택 만들기
public class MyStack {
private int maxSize; // 스택을 저장할 배열
private int[] stackArray; // 스택의 최대 크기
private int top; // 스택 포인터, 초기값은 -1
// 스택의 크기를 받아들이는 생성자
public MyStack(int maxSize) {
this.maxSize = maxSize;
this.stackArray = new int[maxSize];
this.top = -1;
}
// 스택에 데이터 추가
public void push(int num) {
if (top < maxSize - 1) {
System.out.println(num);
stackArray[++top] = num;
} else {
System.out.println("스택이 가득 찼습니다.");
}
}
// 스택에서 데이터 제거
public int pop() {
if (isEmpty()) {
System.out.println("스택이 비었습니다.");
return -1;
} else {
return stackArray[top--];
}
}
// 스택의 최상단 데이터 확인
public int peek() {
if(isEmpty()){
System.out.println("스택이 비었습니다.");
return -1;
} else {
return stackArray[top];
}
}
// 스택이 비어 있는지 확인
public boolean isEmpty() {
return top == -1;
}
// 스택이 가득 찼는지 확인
public boolean isFull(){
return top == maxSize - 1;
}
public static void main(String[] args) {
MyStack stack = new MyStack(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}예외처리가 추가된 스택
public class FixedLengthStack {
private int[] stackArray; // 스택을 저장할 배열
private int stackCapacity; // 스택의 최대 크기
private int stackPointer; // 스택 포인터
// 스택이 비었을 때 발생하는 예외
public static class StackEmptyException extends RuntimeException {
public StackEmptyException() {
}
}
// 스택이 가득 찼을 때 발생하는 예외
public static class StackFullException extends RuntimeException {
public StackFullException() {
}
}
// 생성자
public FixedLengthStack(int maxSize) {
stackPointer = 0;
stackCapacity = maxSize;
stackArray = new int[stackCapacity];
}
// 스택에 데이터 추가
public int push(int item) {
if (stackPointer >= stackCapacity)
throw new StackFullException();
return stackArray[stackPointer++] = item;
}
// 스택에서 데이터 제거
public int pop() {
if (stackPointer <= 0)
throw new StackEmptyException();
return stackArray[--stackPointer];
}
// 스택의 최상단 데이터 확인
public int peek() {
if (stackPointer <= 0)
throw new StackEmptyException();
return stackArray[stackPointer - 1];
}
// 스택 초기화
public void clear() {
stackPointer = 0;
}
// 스택에서 특정 데이터 찾기
public int indexOf(int item) {
for (int i = stackPointer - 1; i >= 0; i--) {
if (stackArray[i] == item)
return i;
}
return -1;
}
// 스택 최대 크기 반환
public int getCapacity() {
return stackCapacity;
}
// 스택에 저장된 데이터 개수 반환
public int size() {
return stackPointer;
}
// 스택이 비어 있는지 확인
public boolean isEmpty() {
return stackPointer == 0;
}
// 스택이 가득 찼는지 확인
public boolean isFull() {
return stackPointer == stackCapacity;
}
// 스택 내용 출력
public void dump() {
if (stackPointer <= 0)
System.out.println("스택이 비어 있습니다.");
else {
for (int i = 0; i < stackPointer; i++)
System.out.print(stackArray[i] + " ");
System.out.println();
}
}
public static void main(String[] args) {
FixedLengthStack stack = new FixedLengthStack(5); // 크기가 5인 스택 생성
// 스택에 데이터를 푸시합니다.
try {
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
// 스택이 가득 찼으므로, 다음 줄에서 예외가 발생합니다.
stack.push(6);
} catch (FixedLengthStack.StackFullException e) {
System.out.println("스택이 가득 찼습니다.");
}
// 스택의 내용을 출력합니다.
stack.dump();
// 스택에서 데이터를 팝합니다.
try {
System.out.println("팝한 데이터: " + stack.pop());
System.out.println("팝한 데이터: " + stack.pop());
System.out.println("팝한 데이터: " + stack.pop());
// 스택이 비었으므로, 다음 줄에서 예외가 발생합니다.
System.out.println("팝한 데이터: " + stack.pop());
System.out.println("팝한 데이터: " + stack.pop());
System.out.println("팝한 데이터: " + stack.pop());
} catch (FixedLengthStack.StackEmptyException e) {
System.out.println("스택이 비어 있습니다.");
}
}
}
큐
1. 큐란?
-
큐(Queue)는 컴퓨터 과학에서 사용되는 중요한 추상 데이터 타입 중 하나로, 선입선출(First In First Out, FIFO)의 원칙을 따른다.
-
큐의 중요 키워드
- enQueue : 큐의 뒷쪽에 새로운 요소 추가
- deQueue : 큐의 앞쪽에서 요소를 제거하고 반환
- peek : 큐의 앞쪽에서 요소를 제거하지 않고 반환
- front : 현재 반환해야되는 요소을 가르키는 배열의 인덱스
- rear : 마지막 요소의 다음 위치를 가리키는 인덱스
- count : 현재 큐에 저장된 요소의 개수
- IsEmpty : 큐가 비어 있는지 확인한다.
-
큐는 데이터를 일시적으로 보관해야 할 때 유용하게 사용된다.
-
프린터의 인쇄 작업 관리 / 운영 체제에서의 작업 스케줄링 / 네트워크 요청의 처리 순서 관리 등
2. 큐 만들기
- enqueue 와 dequeue 메소드에서 rear와 front를 하나씩 늘려주기만 하면 선형 큐
- capacity 로 나눠주면 원형 큐가 된다.
- 선형 큐는 인덱스가 증가만 하므로 배열의 끝에 도달하면 포화된 큐가 아니더라도 앞의 빈 공간을 사용하지 못하는 문제점이 있다.
public class MyQueue {
private int[] queueArray; // 큐
private int front; // 큐의 맨 앞 값의 인덱스
private int rear; // 큐 맨 뒤 값의 다음 인덱스
private int capacity; // 큐 쵀대 용량
private int count; // 큐의 저장된 데이터 수
// 큐의 크기를 받아들이는 생성자
public MyQueue(int maxSize) {
capacity = maxSize;
queueArray = new int[capacity];
front = rear = count = 0;
}
public void enqueue(int item) {
if (isFull()) {
System.out.println("큐가 가득 차서 데이터를 넣을 수 없어요.");
} else {
queueArray[rear] = item;
rear = (rear + 1) % capacity;
count++;
System.out.println(item);
}
}
public void dequeue() {
if (isEmpty()) {
System.out.println("큐가 비어서 뺄 데이터가 없어요.");
} else {
int item = queueArray[front];
front = (front + 1) % capacity;
count--;
System.out.println(item);
}
}
public void peek() {
if (isEmpty()) {
System.out.println("큐가 비어 있어요.");
} else {
int item = queueArray[front];
System.out.println(item);
}
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == capacity;
}
public static void main(String[] args) {
MyQueue q = new MyQueue(3);
q.enqueue(1);
q.enqueue(3);
q.enqueue(5);
System.out.println("q.isFull() : " + q.isFull());
q.enqueue(7);
q.dequeue();
q.peek();
q.dequeue();
q.dequeue();
System.out.println("q.isEmpty() : " + q.isEmpty());
q.dequeue();
}
}예외처리가 추가된 큐
public class FixedLengthQueue {
private int[] queueArray; // 큐를 저장할 배열
private int queueCapacity; // 큐의 최대 크기
private int front; // 첫 번째 요소를 가리키는 인덱스
private int rear; // 마지막 요소의 다음 위치를 가리키는 인덱스
private int currentSize; // 현재 큐에 저장된 요소의 개수
public class QueueEmptyException extends RuntimeException {
public QueueEmptyException() {
}
}
public class QueueFullException extends RuntimeException {
public QueueFullException() {
}
}
public FixedLengthQueue(int maxSize) {
currentSize = front = rear = 0;
queueCapacity = maxSize;
queueArray = new int[queueCapacity];
}
public int enqueue(int item) {
if (currentSize >= queueCapacity)
throw new QueueFullException();
queueArray[rear] = item;
rear = (rear + 1) % queueCapacity;
currentSize++;
return item;
}
public int dequeue() {
if (currentSize <= 0)
throw new QueueEmptyException();
int item = queueArray[front];
front = (front + 1) % queueCapacity;
currentSize--;
return item;
}
public int peek() {
if (currentSize <= 0)
throw new QueueEmptyException();
return queueArray[front];
}
public void clear() {
currentSize = front = rear = 0;
}
public int indexOf(int item) {
for (int i = 0; i < currentSize; i++) {
int index = (front + i) % queueCapacity;
if (queueArray[index] == item)
return index;
}
return -1;
}
public int getCapacity() {
return queueCapacity;
}
public int size() {
return currentSize;
}
public boolean isEmpty() {
return currentSize == 0;
}
public boolean isFull() {
return currentSize == queueCapacity;
}
public void dump() {
if (currentSize <= 0) {
System.out.println("큐가 비어 있습니다.");
} else {
for (int i = 0; i < currentSize; i++) {
System.out.print(queueArray[(front + i) % queueCapacity] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
FixedLengthQueue queue = new FixedLengthQueue(5); // 크기가 5인 큐 생성
// 큐에 데이터를 인큐(추가)합니다.
try {
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
// 큐가 가득 찼으므로, 다음 줄에서 OverflowIntQueueException 예외가 발생할 수 있습니다.
// queue.enqueue(60); // 이 줄의 주석을 해제하면 예외가 발생합니다.
} catch (FixedLengthQueue.QueueFullException e) {
System.out.println("큐가 가득 찼습니다. 더 이상 데이터를 추가할 수 없습니다.");
}
// 큐의 내용을 출력합니다.
queue.dump();
// 큐에서 데이터를 디큐(제거)합니다.
try {
while (!queue.isEmpty()) {
System.out.println("디큐한 데이터: " + queue.dequeue());
}
// 큐가 비었으므로, 다음 줄에서 EmptyIntQueueException 예외가 발생할 수 있습니다.
// System.out.println(queue.dequeue()); // 이 줄의 주석을 해제하면 예외가 발생합니다.
} catch (FixedLengthQueue.QueueEmptyException e) {
System.out.println("큐가 비어 있습니다. 더 이상 데이터를 제거할 수 없습니다.");
}
}
}재귀의 기본
1. 재귀란?
- 재귀(Recursion)는 자신을 정의할 때 자기 자신을 호출하는 방식을 의미한다.
- 종료조건이 필수적으로 필요하다
- 재귀 함수는 기본적으로 두 부분으로 구성된다.
a. 기저 조건(Base Case)
재귀 호출을 멈추고 함수가 자기 자신을 더 이상 호출하지 않는 조건이다.
기저 조건은 재귀가 무한 루프에 빠지지 않도록 하는 중요한 역할을 한다.
b. 재귀적 단계(Recursive Case)
문제의 크기를 줄이고 자기 자신을 호출하는 부분이다.
public class RecursiveTest {
static void recursive(int n){
if(n > 0){
recursive(n - 1);
System.out.println(n);
}
}
public static void main(String[] args) {
recursive(5);
}
}2. 팩토리얼 구하기
import java.util.Scanner;
public class FactorialCalculator {
static int factorial(int n) {
if (n > 0)
return n * factorial(n - 1);
else
return 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("n!, 정수 n을 입력하세요 : ");
int n = sc.nextInt();
System.out.println(n + "! = " + factorial(n));
}
}3. 유클리드 호제법
- 유클리드 호제법(Euclidean Algorithm)은 두 양의 정수의 최대공약수(Greatest Common Divisor, GCD)를 찾는 효율적인 방법이다.
- 기본 아이디어는 두 수의 차이가 그 수들의 최대 공약수에 영향을 미치지 않는다는 것이다.
- 두 수 a와 b (a > b)의 최대공약수는 a와 a-b의 최대공약수와 같다. 이 원리를 반복하면 최종적으로 최대공약수를 구할 수 있다.
- 뺄셈을 이용한 방법
가장 단순한 형태로, 두 수 중 큰 수에서 작은 수를 뺀다.
이 과정을 두 수가 같아질 때까지 반복하여, 최종적으로 남은 수가 두 수의 최대공약수가 된다.
→ 큰 수에 대해서는 계산이 비효율적일 수 있다. - 나눗셈을 이용한 방법(모듈로 연산)
두 수 a와 b (a > b)가 있을 때, a를 b로 나눈 나머지를 구한다.
그 다음, b와 이 나머지의 최대공약수를 구한다.
반복하여 나머지가 0이 되었을 때의 b가 두 수의 최대공약수이다.
→ 뺄셈을 사용하는 방법보다 훨씬 빠르고 효율적이다.
import java.util.Scanner;
public class GCDCalculator {
// 유클리드 호제법을 사용한 반복문
static int gcd(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
// 유클리드 호제법을 사용한 재귀 호출
static int calculateGCD(int x, int y) {
if (y == 0)
return x;
else
return calculateGCD(y, x % y);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("두 수의 최대공약수를 계산합니다.");
System.out.print("첫 번째 정수를 입력하세요: ");
int x = sc.nextInt();
System.out.print("두 번째 정수를 입력하세요: ");
int y = sc.nextInt();
System.out.println("두 수의 최대공약수는 " + gcd(x, y) + "입니다.");
System.out.println("두 수의 최대공약수는 " + calculateGCD(x, y) + "입니다.");
}
}꼬리 재귀
- 팩토리얼을 재귀함수와 for문으로 작성한 코드
import java.util.Scanner;
public class FactorialCalculator {
//재귀함수
static int factorial(int num) {
if (num > 0){
return factorial(num-1) * num;
} else{
return 1; //0!은 1이다.
}
}
//for문으로 구현한 함수
static int factorialForGrammar(int num) {
int result = 1;
if (num > 0){
for(int i = num; i < 0; i--){
result *= num;
}
}else {
result = 1;
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = 0;
do {
System.out.print("펙토리얼을 구하고자하는 양의 정수를 입력하세요: ");
num = sc.nextInt();
}while(num < 0);
System.out.println(factorial(num));
System.out.println(factorialForGrammar(num));
}
}꼬리재귀란
위의 팩토리얼 재귀함수 코드를 보면 return뒤에 아래와 같은 형태로 되어있는 것을 볼 수 있다.
factorial(num-1) * num;- 꼬리재귀는 재귀함수에 다른 연산을 하는 것이 아닌 모조건 return뒤에 재귀함수 본인만 오는 것을 말한다.
- 꼬리 재귀(Tail Recursion)는 함수의 마지막 동작이 자기 자신을 호출하는 형태의 재귀이다.
- 재귀 호출이 함수의 끝부분에서 발생하며, 현재 함수의 실행 상태를 유지할 필요가 없기 때문에, 컴파일러나 인터프리터가 최적화하기가 더 쉽다.
→ 즉, 새로운 스택 프레임을 추가하지 않고 현재의 스택 프레임을 재사용할 수 있어 메모리 사용량이 줄고, 실행 효율이 높아질 수 있다. - 예제 : 팩토리얼 계산
import java.util.Scanner;
public class TailRecursiveFactorial {
// 꼬리 재귀를 사용한 팩토리얼 계산 메서드
static int factorial(int n, int accumulator) {
if (n == 1) return accumulator;
return factorial(n - 1, n * accumulator); // 꼬리 재귀 호출
}
// 사용자가 입력한 숫자에 대해 팩토리얼을 계산
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("팩토리얼을 계산할 정수를 입력하세요: ");
int x = sc.nextInt();
// 초기 누적 변수 값으로 1을 사용
int result = factorial(x, 1);
System.out.println(x + "의 팩토리얼은 " + result + "입니다.");
}
}마지막에 수행하는 작업이 재귀 호출인 점이 중요한 특징이다.
호출 시 전달되는 모든 정보가 매개변수에 포함되어 있어서 현재 실행 컨텍스트를 유지할 필요가 없다는 것이다.
정렬
정렬(Sorting)은 데이터를 특정 기준에 따라 순서대로 배열하는 과정이다.
1. 버블 정렬(Bubble Sort)
- 방식
: 인접한 두 요소를 비교하고, 필요한 경우에 위치를 교환한다. 이 과정을 모든 요소가 정렬될 때까지 반복한다.
: 한 턴이 끝나면 마지막 요소는 정렬되어 있는 상태 - 특징 : 구현이 간단하지만, 효율성이 낮아 큰 데이터셋에는 부적합하다.
평균 및 최악의 경우 시간 복잡도는 O(n^2) 이다.
import java.util.Arrays;
public class BubbleSortExam {
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println((i + 1) + "번째 정렬 : " + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr = {64, 33, 67, 22, 6, 88, 5};
System.out.println("원래배열 : " + Arrays.toString(arr));
bubbleSort(arr);
System.out.println("정렬 후 배열 : " + Arrays.toString(arr));
}}
if 문 안의 내용이 보기 복잡하다면 swap 메소드로 구현하면 좀 더 깔끔해지기도 한다.
2. 선택 정렬(Selection Sort)
- 방식
: 전체 요소 중에서 가장 작은(혹은 큰) 요소를 찾아 첫 번째(혹은 마지막) 위치에 놓고, 나머지 요소에 대해 같은 과정을 반복한다.
: 한 턴이 끝나면 가장 앞의 요소는 정렬되어 있는 상태 - 특징 : 버블 정렬과 마찬가지로 구현이 쉽지만, 큰 데이터셋에는 비효율적이다.
시간 복잡도는 평균과 최악의 경우 모두 O(n^2) 이다.
import java.util.Arrays;
public class SelectionSortExam {
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
swap(arr, i, min);
System.out.println((i + 1) + "번째 정렬 : " + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr = {64, 33, 67, 22, 6, 88, 5};
System.out.println("원래배열 : " + Arrays.toString(arr));
selectionSort(arr);
System.out.println("정렬 후 배열 : " + Arrays.toString(arr));
}
}
안녕하세요, 박경서입니다.