Now Loading ...
-
-
-
📦[DS,Algorithm] Circular Queue(원형 큐)의 중간 지점 찾기.
1️⃣ Circular Queue(원형 큐)의 중간 지점 찾기.
Java에서 배열을 사용하여 구현한 원형 큐에서 중간 지점을 찾는 방법은 큐의 시작 위치(‘front’)와 끝 위치(‘rear’)를 기준으로 계산할 수 있습니다.
중간 지점을 찾는 공식은 원형 큐의 특성을 고려하여 적절히 조정되어야 합니다.
2️⃣ 중간 지점을 찾기 위한 방법.
1️⃣ 중간 지점 계산 공식.
중간 지점을 찾는 방법은 큐의 시작점과 끝점을 이용하여 계산할 수 있습니다.
원형 큐의 크기, 시작 인덱스(front), 끝 인덱스(rear)를 사용하여 중간 인덱스를 계산할 수 있습니다.
이때 중간 지점을 계산하는 공식은 다음과 같습니다.
(front + size / 2) % capacity
여기서 ‘size’ 는 큐에 현재 저장된 요소의 수이고, ‘capacity’ 는 큐의 전체 크기입나다.
3️⃣ 예시
public class CircularQueue {
private int[] queue;
private int front, rear, size, capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
this.queue = new int[capacity];
this.front = 0;
this.rear = 0;
this.size = 0;
}
public boolean isFull() {
return size == capacity;
}
public boolean isEmpty() {
return size == 0;
}
public void enqueue(int data) {
if (isFull()) {
throw new RuntimeException("Queue is full");
}
queue[rear] = data;
rear = (rear + 1) % capacity;
size++;
}
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
int data = queue[front];
front = (front + 1) % capacity;
size--;
return data;
}
public int getMiddle() {
if (isEmpty()) {
throw new RuntimeException("Queue is empty");
}
int middleIndex = (front + size / 2) % capacity;
return queue[middleIndex];
}
public static void main(String[] args) {
CircularQueue cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.enqueue(40);
cq.enqueue(50);
System.out.println("Middle element: " + cq.getMiddle()); // Output: Middle element: 30
cq.dequeue();
cq.enqueue(60);
System.out.println("Middle element: " + cq.getMiddle()); // Output: Middle element: 40
}
}
이 코드에서는 ‘CircularQueue’ 클래스를 정의하고, ‘enqueue’, ‘dequeue’, ‘isFull’, ‘isEmpty’ 메서드를 포함합니다.
또한, 큐의 중간 요소를 반환하는 ‘getMiddle’ 메서드를 정의합니다.
이 메서드는 현재 큐의 크기와 시작 인덱스를 사용하여 중간 인덱스를 계산한 후 해당 인덱스의 요소를 반환합니다.
-
📦[DS,Algorithm] Deque에서의 front와 rear의 변화.
🧨 시발점.
Deque을 공부하던 중 동적으로 변하는 front와 rear가 근본적으로 어떻게 동작하는지 궁금해졌습니다.
이것을 알게되면 정확하게 Deque의 addFirst, addLast, removeFirst, removeLast 시 front와 rear가 어디에 위치하는지 알 수 있고 Deque의 원리를 이해 할 수 있을 것 같았습니다.
1️⃣ Deque의 front와 rear의 위치는 변할 수 있나요? 🤔
‘Deque‘ (Double Ended Queue)에서 ‘front‘ 와 ‘rear‘ 의 위치는 변할 수 있습니다.
‘Deque‘ 는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이기 때문에, ‘front‘ 와 ‘rear‘ 의 위치는 데이터가 삽입되거나 제거될 때마다 변합니다.
2️⃣ Deque에서의 front와 rear의 변화. 🤩
1️⃣ 삽입 연산 (‘addFirst‘ 와 ‘addLast‘)
‘addFirst’ : 요소를 덱의 앞쪽에 삽입합니다.
‘front‘ 위치가 바뀝니다.
‘addLast’ : 요소를 덱의 뒤쪽에 삽입합니다.
‘rear‘ 위치가 바뀝니다.
2️⃣ 삭제 연산 (‘removeFirst‘ 와 ‘removeLast‘)
‘removeFirst’ : 덱의 앞쪽에서 요소를 제거합니다.
‘front‘ 위치가 바뀝니다.
‘removeLast’ : 덱의 뒤쪽에서 요소를 제거합니다.
‘rear‘ 위치가 바뀝니다.
3️⃣ 예제 코드.
아래는 ‘Deque’ 의 ‘LinkedList’ 구현을 사용하여 ‘front’ 와 ‘rear’ 의 변화를 보여주는 예제 코드입니다.
import java.util.Deque;
import java.util.LinkedList;
public class DequeExample {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
// 요소를 덱의 앞과 뒤에 추가
deque.addFirst("A"); // front: A
deque.addLast("B"); // rear: B
deque.addFirst("C"); // front: C, rear: B
deque.addLast("D"); // rear: D
System.out.println("Initial Deque: " + deque); // 출력 : [C,A,B,D]
// 앞쪽에서 요소 제거
System.out.println("Removed from front: " + deque.removeFirst()); // 출력: C
// 뒤쪽에서 요소 제거
System.out.println("Removed from rear: " + deque.removeLast()); // 출력: D
System.out.println("Deque after removals: " + deque); // 출력: [A, B]
// 덱의 앞쪽과 뒤쪽에서 요소 확인
System.out.println("Front element: " + deque.getFirst()); // 출력: A
System.out.println("Rear element: " + deque.getLast()); // 출력: B
}
}
👉 설명.
1️⃣ 삽입 연산.
‘deque.addFirst(“A”)’ : “A”를 덱의 앞에 삽입합니다.
‘deque.addLast(“B”)’ : “B”를 덱의 뒤에 삽입합니다.
‘deque.addFirst(“C”)’ : “C”를 덱의 앞에 삽입합니다.
‘deque.addLast(“D”)’ : “D”를 덱의 뒤에 삽입합니다.
이 연산들은 ‘front’ 와 ‘rear’ 의 위치를 업데이트합니다.
2️⃣ 삭제 연산.
‘deque.removeFirst()’ : 덱의 앞쪽에서 “C”를 제거합니다.
‘deque.removeLast()’ : 덱의 뒤쪽에서 “D”를 제거합니다.
이 연산들은 ‘front’ 와 ‘rear’ 의 위치를 다시 업데이트합니다.
3️⃣ 요소 확인.
‘deque.getFirst()’ : 덱의 앞쪽 요소를 확인합니다.
‘deque.getLast()’ : 덱의 뒤쪽 요소를 확인합니다.
이 예시 코드는 ‘front’ 와 ‘rear’ 가 데이터의 삽입 및 삭제 연산에 따라 어떻게 변하는지 잘 보여줍니다.
‘Deque’ 는 이처럼 양쪽 끝에서의 삽입과 삭제 연산을 지원하므로, ‘front’ 와 ‘rear’ 의 위치는 동적입니다.
-
📦[DS,Algorithm] Circular Queue(원형 큐)란?
1️⃣ Circular Queue(원형 큐)란?
원형 큐는 큐의 일종으로, 배열을 사용하여 구현되며, 큐의 마지막 위치가 처음 위치와 연결되어 원형 구조를 가지는 큐입니다.
원형 큐는 고정된 크기의 배열을 사용하여 구현되므로, 큐의 마지막 인덱스가 배열의 끝에 도달하면 다음 인덱스가 배열의 시작 부분으로 이동합니다.
이를 통해 메모리를 효율적으로 사용할 수 있으며, 큐의 처음과 끝을 관리하는 데 도움이 됩니다.
2️⃣ 원형 큐의 원리.
고정된 크기 : 원형 큐는 고정된 크기의 배열을 사용하여 구현됩니다. 따라서 배열의 크기를 초과하여 요소를 추가할 수 없습니다.
연결된 인덱스 : 큐의 마지막 인덱스가 배열의 끝에 도달하면, 다음 인덱스는 배열의 처음 부분으로 이동합니다.
두 개의 포인터 : 원형 큐는 두 개의 포인터를 사용하여 구현됩니다.
‘front’ : 큐의 첫 번째 요소를 가리킵니다.
‘rear’ : 큐의 마지막 요소를 가리킵니다.
비어 있는 상태와 가득 찬 상태 : 큐가 비어 있는 상태와 가득 찬 상태를 구별해야 합니다. 이를 위해 추가적인 변수를 사용하거나 포인터의 위치를 비교하여 상태를 확인합니다.
3️⃣ 원형 큐의 주요 연산.
초기화 : 큐의 크기를 설정하고, ‘front’ 와 ‘rear’ 포인터를 초기화합니다.
isEmpty() : 큐가 비어 있는지 확인합니다.
isFull() : 큐가 가득 찼는지 확인합니다.
enqueue() : 큐에 요소를 추가합니다. ‘rear’ 포인터를 업데이트합니다.
dequeue() : 큐에서 요소를 제거하고 반환합니다. ‘front’ 포인터를 업데이트합니다.
peek() : 큐의 첫 번째 요소를 반환합니다.
4️⃣ 원형 큐의 예제 구현.
public class CircularQueue {
private int[] queue;
private int front;
private int rear;
private int size;
private int capacity;
// 생성자
public CircularQueue(int capacity) {
this.capacity = capacity;
queue = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
// 큐가 비어 있는지 확인
public boolean isEmpty() {
return size == 0;
}
// 큐가 가득 찼는지 확인
public boolean isFull() {
return size == capacity;
}
// 큐에 요소 추가
public void enqueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
return;
}
rear = (rear + 1) % capacity;
queue[rear] = element;
size++;
}
// 큐에서 요소 제거
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
int element = queue[front];
front = (front + 1) % capacity;
size--;
return element;
}
// 큐의 첫 번째 요소 확인
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
return queue[front];
}
// 큐의 크기 반환
public int getSize() {
return size;
}
// 큐의 모든 요소 출력
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
int i = front;
int count = 0;
while (count < size) {
System.out.print(queue[i] + " ");
i = (i + 1) % capacity;
count++;
}
System.out.println();
}
// 메인 메서드 (테스트용)
public static void main(String[] args) {
CircularQueue cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.enqueue(40);
cq.enqueue(50);
cq.display(); // 출력: 10 20 30 40 50
System.out.println("Dequeued: " + cq.dequeue()); // 출력: Dequeued: 10
System.out.println("Dequeued: " + cq.dequeue()); // 출력: Dequeued: 20
cq.display(); // 출력: 30 40 50
cq.enqueue(60);
cq.enqueue(70);
cq.display(); // 출력: 30 40 50 60 70
System.out.println("Front element: " + cq.peek()); // 출력: Front element: 30
}
}
🙋♂️ 설명.
큐 초기화:
‘capacity’ : 큐의 최대 크기입니다.
‘queue’ : 큐를 저장할 배열입니다.
‘front’ : 큐의 첫 번째 요소를 가리키는 인덱스입니다.
‘rear’ : 큐의 마지막 요소를 가리키는 인덱스입니다.
‘size’ : 큐에 있는 요소의 개수입니다.
메서드:
‘isEmpty()’ : 큐가 비어 있는지 확인합니다.
‘isFull()’ : 큐가 가득 찼는지 확인합니다.
‘enqueue(int element)’ : 큐에 요소를 추가합니다.
‘dequeue()’ : 큐에서 요소를 제거하고 반환합니다.
‘peek()’ : 큐의 첫 번째 요소를 반환합니다.
‘getSize()’ : 큐에 있는 요소의 개수를 반환합니다.
‘display()’ : 큐의 모든 요소를 출력합니다.
5️⃣ 결론.
원형 큐는 배열을 효율적으로 사용하여 큐의 크기를 고정하고, 처음과 끝이 연결된 형태로 큐를 관리하는 자료구조입니다.
이를 통해 큐의 공간을 최대한 활용하고, 큐가 비어 있는지 가득 찼는지를 쉽게 확인할 수 있습니다.
🤔 궁금했던 부분.
rear = (rear + 1) % capacity;
1️⃣ 이 코드에서 % capacity 를 하는 이유는 무엇일까?
원형 큐에서 ‘rear’ 포인터를 업데이트 할 때 % capacity 를 사용하는 이유는 큐가 마지막 인덱스에 도달한 후, 다시 처음 인덱스로 돌아가도록 하기 위해서입니다.
이를 통해 큐가 원형으로 동작할 수 있습니다.
구체적으로 말하면, 큐의 크기를 고정된 크기의 배열로 구현할 때, 배열의 끝에 도달했을 때 다시 처음으로 돌아가는 기능을 제공합니다.
2️⃣ % 연산자의 역할.
배열의 인덱스는 0부터 시작하여 배열의 크기보다 1 작은 값까지입니다.
예를 들어, 배열의 크기가 5라면 인덱스는 0부터 4까지입니다.
원형 큐에서 새로운 요소를 추가할 때마다 ‘rear’ 포인터를 증가시키는데, 이 포인터가 배열의 끝을 넘어가지 않도록 해야 합니다.
이를 위해 % capacity 연산을 사용합니다.
rear = (rear + 1) % capacity;
이 연산은 ‘rear’ 포인터를 1씩 증가시키다가, 배열의 끝에 도달하면 다시 0으로 돌아가게 합니다.
즉, 배열의 인덱스가 배열의 크기를 넘어가면, 다시 처음 인덱스(0)로 순환되게 합니다.
👉 예제.
배열의 크기가 5인 원형 큐를 생각해봅시다.
초기 상태: ‘rear = -1’
요소 추가 시, ‘rear’ 포인터의 변화를 관찰해보면
첫 번째 추가: ‘rear = (rear + 1) % 5 -> rear = 0’
두 번째 추가: ‘rear = (rear + 1) % 5 -> rear = 1’
세 번째 추가: ‘rear = (rear + 1) % 5 -> rear = 2’
네 번째 추가: ‘rear = (rear + 1) % 5 -> rear = 3’
다섯 번째 추가: ‘rear = (rear + 1) % 5 -> rear = 4’
여섯 번째 추가: ‘rear = (rear + 1) % 5 -> rear = 0’ (다시 처음으로 돌아감)
이렇게 ‘rear’ 포인터가 배열의 끝에 도달하면 다시 배열의 시작 부분으로 순환되므로, 배열을 효율적으로 사용할 수 있게 됩니다.
💻 코드 예제.
위 개념을 이용한 원형 큐의 ‘enqueue’ 메서드 구현
public void enqueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
return;
}
rear = (rear + 1) % capacity; // rear 포인터를 증가시키고, 배열의 처음으로 순환시킴.
queue[rear] = element;
size++;
}
6️⃣ 정리.
원형 큐에서 ’% capacity’ 연산은 ‘rear’ 포인터와 ‘front’ 포인터가 배열의 끝에 도달했을 때, 다시 배열의 시작 부분으로 돌아가기 위해 사용됩니다.
이를 통해 배열의 고정된 크기를 효율적으로 활용하며, 원형 큐의 특성을 유지할 수 있습니다.
-
📦[DS,Algorithm] LinkedList를 사용한 Deque.
1️⃣ LinkedList를 사용한 Deque.
‘LinkedList‘ 는 ‘Deque‘ 인터페이스를 구현한 클래스 중 하나로, 양쪽 끝에서 삽입과 삭제가 가능한 이중 연결 리스트 기반의 자료 구조입니다.
‘LinkedList‘ 는 ‘Deque‘ 뿐만 아니라 ‘List‘, ‘Queue‘ 인터페이스도 구현하여 다양한 형태로 사용할 수 있습니다.
2️⃣ 주요 특징.
이중 끝 큐 : 양쪽 끝에서 요소를 추가하고 제거할 수 있습니다.
이중 연결 리스트 : 각 노드는 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가집니다.
비동기적 : ‘LinkedList‘ 는 비동기적으로 동작하므로 동기화된 환경에서 안전하지 않습니다.
3️⃣ 주요 메서드.
삽입 연산.
‘addFirst(E e)’ : 지정된 요소를 덱의 앞쪽에 추가합니다.
‘addLast(E e)’ : 지정된 요소를 덱의 뒤쪽에 추가합니다.
‘offerFirst(E e)’ : 지정된 요소를 덱의 앞쪽에 추가합니다.
‘offerLast(E e)’ : 지정된 요소를 덱의 뒤쪽에 추가합니다.
삭제 연산.
‘removeFirst()’ : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
‘removeLast()’ : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
‘pollFirst()’ : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
‘pollLast()’ : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
조회 연산.
‘getFirst()’ : 덱의 앞쪽에 있는 요소를 반환합니다.
‘getLast()’ : 덱의 뒤쪽에 있는 요소를 반환합니다.
‘peekFirst()’ : 덱의 앞쪽에 있는 요소를 반환합니다.
‘peekLast()’ : 덱의 뒤쪽에 있는 요소를 반환합니다.
스택 연산.
‘push(E e)’ : 스택의 맨 위에 요소를 추가합니다.(FIFO, First In First Out)
‘pop()’ : 스택의 맨 위에 있는 요소를 제거하고 반환합니다.(LIFO, Last In First Out)
4️⃣ 시간 복잡도
삽입과 삭제 연산 : ‘addFirst‘, ‘addLast‘, ‘removeFirst‘, ‘removeLast‘, ‘offerFirst‘, ‘offerLast‘, ‘pollFirst‘, ‘pollLast‘ 등의 연산은 O(1)입니다.
이중 연결 리스트를 사용하기 때문에 양쪽 끝에서의 삽입과 삭제는 상수 시간 내에 수행됩니다.
조회 연산 : ‘getFirst‘, ‘getLast‘, ‘peekFirst‘, ‘peekLast‘ 등의 연산은 O(1)입니다.
임의 접근 연산( **‘get(int index)‘, ‘set(int index, E element)’ 등) :** 인덱스를 사용한 접근 연산은 리스트의 중간에 있는 요소를 찾기 위해 리스트를 순회해야 하므로 O(n) 시간이 걸립니다.
5️⃣ 코드 예시.
아래 코드는 ‘LinkedList‘ 를 ‘Deque‘ 로 사용하는 예제입니다.
import java.util.Deque;
import java.util.LinkedList;
public class LinkedListDequeExample {
public static void main(String[] args) {
// LinkedList로 Deque 생성
Deque<Integer> deque = new LinkedList<>();
// 요소 삽입
deque.addFirst(1);
deque.addLast(2);
deque.offerFirst(0);
deque.offerLast(3);
// 요소 조회
System.out.println("First element: " + deque.getFirst());
System.out.println("Last element: " + deque.getLast());
System.out.println("Peek first element: " + deque.peekFirst());
System.out.println("Peek last element: " + deque.peekLast());
// 요소 식제
System.out.println("Removed first element: " + deque.removeFirst());
System.out.println("Removed last element: " + deque.removeLast());
System.out.println("Poll first element: " + deque.pollFirst());
System.out.println("Poll last element: " + deque.pollLast());
// 덱의 크기와 비어 있는지 여부 확인
System.out.println("Deque size: " + deque.size());
System.out.println("Is deque empty? " + deque.isEmpty());
// 스택 연산.
deque.push(4);
System.out.println("Pushed element: " + deque.peekFirst());
System.out.println("Popped element: " + deque.pop());
}
}
/*
=== 출력 ===
First element: 0
Last element: 3
Peek first element: 0
Peek last element: 3
Removed first element: 0
Removed last element: 3
Poll first element: 1
Poll last element: 2
Deque size: 0
Is deque empty? true
Pushed element: 4
Popped element: 4
*/
🙋♂️ 설명.
베열 초기화 : ‘DEFAULT_CAPACITY‘ 크기의 배열을 초기화하고, ‘head‘, ‘tail‘, ‘size‘ 변수를 초기화 합니다.
삽입 연산( **‘addFirst‘, ‘addLast‘) :** 요소를 덱의 첫 번째 또는 마지막에 추가합니다.
삭제 연산( **‘removeFirst‘, ‘removeLast‘) :** 첫 번째 요소와 마지막 요소를 각각 제거합니다.
조회 연산( **‘getFirst‘, ‘getLast‘, ‘peekFirst‘, ‘peekLast‘) :** 첫 번째 요소와 마지막 요소를 반환합니다.
기타 메서드 : ‘size‘ 와 ‘isEmpty‘ 메서드는 덱의 크기와 비어 있는지 여부를 반환합니다.
스택 연산( **‘push‘, ‘pop‘) :** 스택의 맨 위에 요소를 추가하고, 스택의 맨 위에 있는 요소를 제거하고 반환합니다.
위 예시 코드에서는 ‘LinkedList‘ 를 ‘Deque‘ 로 사용하여 다양한 연산을 수행하는 방법을 보여줍니다.
‘LinkedList‘ 는 이중 연결 리스트를 사용하기 때문에 양쪽 끝에서의 삽입과 삭제가 빠르고 효율적입니다.
-
📦[DS,Algorithm] ArrayDeque
1️⃣ ArrayDeque.
Java에서 ‘ArrayDeque‘ 는 ‘java.util‘ 패키지에 속하는 클래스이며, 큐(Queue)와 덱(Deque)의 기능을 모두 지원하는 배열 기반의 자료 구조입니다.
‘ArrayDeque‘ 는 ‘Deque‘ 인터페이스를 구현하며, 그기가 가변적인 배열을 사용하여 요소를 저장합니다.
2️⃣ 주요 특징.
이중 끝 큐 : 양쪽 끝에서 요소를 추가하고 제거할 수 있습니다.
크기 조정 : 필요에 따라 내부 배열의 크기를 자동으로 조정합니다.
스택 및 큐로 사용 가능 : ‘ArrayDeque‘ 는 스택(LIFO, Last In First Out)과 큐(FIFO, First In First Out) 모두로 사용할 수 있습니다.
비동기적 : ‘ArrayDeque‘ 는 비동기적으로 동작하므로 동기화된 환경에서 안전하지 않습니다.
3️⃣ 주요 메서드.
삽입 연산.
‘addFirst(E e)’ : 지정된 요소를 덱의 앞쪽에 추가합니다.
‘addLast(E e)’ : 지정된 요소를 덱의 뒤쪽에 추가합니다.
‘offerFirst(E e)’ : 지정된 요소를 덱의 앞쪽에 추가합니다.
‘offerLast(E e)’ : 지정된 요소를 덱의 뒤쪽에 추가합니다.
삭제 연산.
‘removeFirst()’ : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
‘removeLast()’ : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
‘pollFirst()’ : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
‘pollLast()’ : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
조회 연산.
‘getFirst()’ : 덱의 앞쪽에 있는 요소를 반환합니다.
‘getLast()’ : 덱의 뒤쪽에 있는 요소를 반환합니다.
‘peekFirst()’ : 덱의 앞쪽에 있는 요소를 반환합니다.
‘peekLast()’ : 덱의 뒤쪽에 있는 요소를 반환합니다.
스택 연산.
‘push(E e)’ : 스택의 맨 위에 요소를 추가합니다.(LIFO, Last In First Out)
‘pop(E e)’ : 스택의 맨 위에 있는 요소를 제거하고 반환합니다.(LIFO, Last In First Out)
4️⃣ 시간 복잡도.
삽입과 삭제 연산 : ‘addFirst‘, ‘addLast‘, ‘removeFirst‘, ‘removeLast‘, ‘offerFirst‘, ‘offerLast‘, ‘pollFirst‘, ‘pollLast‘, 등의 연산은 평균적으로 O(1)입니다.
조회 연산 : ‘getFirst‘, ‘getLast‘, ‘peekFirst‘, ‘peekLast‘ 등의 연산은 O(1)입니다.
크기 조정 : 베열의 크기가 가득 찼을 때 크기를 두 배로 늘리거나 줄이는 작업은 O(n) 시간이 걸리지만, 이는 드물게 발생하므로 평균적으로는 O(1)로 간주합니다. (amortized O(1)).
5️⃣ 예제 코드
아래의 코드는 ‘ArrayDeque‘ 를 사용한 예제 코드입니다.
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeExample {
public static void main(String[] args) {
// ArrayDeque로 Deque 생성
Deque<Integer> deque = new ArrayDeque<>();
// 요소 삽입
System.out.println("=== 요소 삽입 ===");
deque.addFirst(1);
deque.addLast(2);
deque.offerFirst(0);
deque.offerLast(3);
System.out.println(deque);
System.out.println();
// 요소 조회
System.out.println("=== 요소 조회 ===");
System.out.println("First element: " + deque.getFirst());
System.out.println("Last element: " + deque.getLast());
System.out.println("Peek first element: " + deque.peekFirst());
System.out.println("Peek last element: " + deque.peekLast());
System.out.println();
// 요소 삭제
System.out.println("=== 요소 삭제 ===");
System.out.println("Removed first element: " + deque.removeFirst());
System.out.println("Removed last element: " + deque.removeLast());
System.out.println("Poll first element: " + deque.pollFirst());
System.out.println("Poll last element: " + deque.pollLast());
System.out.println();
// 덱의 크기와 비어 있는지 여부 확인
System.out.println("=== 덱의 크기와 비어 있는지 여부 확인 ===");
System.out.println("Deque size: " + deque.size());
System.out.println("Is deque empty? " + deque.isEmpty());
System.out.println();
// 스택 연산
System.out.println("=== 스택 연산 ===");
deque.push(4);
System.out.println("Pushed element: " + deque.peekFirst());
System.out.println("Popped element: " + deque.pop());
}
}
/*
=== 출력 ===
=== 요소 삽입 ===
[0, 1, 2, 3]
=== 요소 조회 ===
First element: 0
Last element: 3
Peek first element: 0
Peek last element: 3
=== 요소 삭제 ===
Removed first element: 0
Removed last element: 3
Poll first element: 1
Poll last element: 2
=== 덱의 크기와 비어 있는지 여부 확인 ===
Deque size: 0
Is deque empty? true
=== 스택 연산 ===
Pushed element: 4
Popped element: 4
*/
-
📦[DS,Algorithm] Deque(데크, 덱)
1️⃣ Deque(덱, Double Ended Queue)
Deque(덱, Double Ended Queue)는 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조입니다.
Java에서는 java.util 패키지에서 제공하는 Deque 인터페이스와 이를 구현한 클래스인 ArrayDeque 와 LinkedList 를 통해 사용할 수 있습니다.
Deque 는 큐(Queue)와 스택(Stack)의 기능을 모두 포함하고 있습니다.
1️⃣ 데크 기본 구조
데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조
일부 기능을 제한하여 용도에 맞게 변형 가능
add나 remove 계열은 예외를 발생시킵니다.
때문에 예외 처리가 가능합니다.
offer이나 poll 계열은 null이나 false를 반환합니다.
때문에 return값 (반환값)을 받아서 처리할 수 있습니다.
2️⃣ Deque의 주요 메서드.
1️⃣ 삽입 연산.
addFirst(E e) : 지정된 요소를 덱의 앞쪽에 추가합니다.
addLast(E e) : 지정된 요소를 덱의 뒤쪽에 추가합니다.
offerFirst(E e) : 지정된 요소를 덱의 앞쪽에 추가합니다.
offerLast(E e) : 지정된 요소를 덱의 뒤쪽에 추가합니다.
2️⃣ 삭제 연산.
removeFirst() : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
removeLast() : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
pollFirst() : 덱의 앞쪽에서 요소를 제거하고 반환합니다.
pollLast() : 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
3️⃣ 조회 연산.
getFirst() : 덱의 앞쪽에 있는 요소를 반환합니다.
getLast() : 덱의 뒤쪽에 있는 요소를 반환합니다.
peekFirst() : 덱의 앞쪽에 있는 요소를 반환합니다.
peekLast() : 덱의 뒤쪽에 있는 요소를 반환합니다.
4️⃣ 기타 연산.
size() : 덱에 있는 요소의 수를 반환합니다.
isEmpty() : 덱이 비어 있는지 여부를 확인합니다.
3️⃣ 시간 복잡도.
Deque 인터페이스의 시간 복잡도는 이를 구현한 클래스에 따라 달라집니다.
Java에서는 주로 ArrayDeque 와 LinkedList 를 사용하여 Deque 를 구현합니다.
1️⃣ ArrayDeque
삽입과 삭제 연산 (앞과 뒤 모두): 평균적으로 O(1)
조회 연산 (앞과 뒤 모두): O(1)
ArrayDeque 는 배열을 기반으로 구현되기 때문에, 배열이 꽉 차면 자동으로 크기를 늘리지만, 이 과정은 amortized O(1)로 간주됩니다.
2️⃣ LinkedList
삽입과 삭제 연산 (앞과 뒤 모두): O(1)
조회 연산 (앞과 뒤 모두): O(1)
LinkedList 는 이중 연결 리스트로 구현되어 있어 각 노드가 이전과 다음 노드에 대한 참조를 가지고 있습니다.
LinkedList는 각 노드가 이전 노드와 다음 노드의 참조를 가지고 있어 삽입과 삭제가 O(1)의 시간 복잡도를 가집니다.
하지만 탐색에는 O(n)의 시간이 소요됩니다.
ArrayDeque는 배열을 사용하여 내부적으로 구현되기 때문에 삽입과 삭제 시에도 평균적으로 O(1)의 시간 복잡도를 가지며,
특히 큐의 끝에서의 연산이 빠릅니다.
다만, 내부적으로 배열이 가득 차면 크기를 조정해야 하므로 최악의 경우 O(n)의 시간 복잡도가 발생할 수 있습니다.
Deque 는 다양한 상황에서 유연하게 사용될 수 있는 유용한 자료구조입니다.
특히 양쪽 끝에서의 빠른 삽입과 삭제가 필요한 경우 유용합니다.
3️⃣ 직접 Deque 인터페이스 구현.
간단한 배열을 사용하여 Deque 를 구현해보겠습니다.
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SimpleArrayDeque<E> {
private static final int DEFALT_CAPACITY = 10;
private E[] elements;
private int head;
private int tail;
private int size;
public SimpleArrayDeque() {
elements = (E[]) new Object[DEFALT_CAPACITY];
head = 0;
tail = 0;
size = 0;
}
public void addFirst(E e) {
if (size == elements.length) {
resize();
}
head = (head - 1 + elements.length) % elements.length;
elements[head] = e;
size++;
}
public void addLast(E e) {
if (size == elements.length) {
resize();
}
elements[tail] = e;
tail = (tail + 1) % elements.length;
size++;
}
public E removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
E element = elements[head];
elements[head] = null; // for garbege collection
head = (head + 1);
size--;
return element;
}
public E removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
tail = (tail - 1 + elements.length) % elements.length;
E element = elements[tail];
elements[tail] = null; // for garbage collection
size--;
return element;
}
public E getFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
return elements[head];
}
public E getLast() {
if (size == 0) {
throw new NoSuchElementException();
}
return elements[(tail - 1 + elements.length) % elements.length];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private void resize() {
int newCapacity = elements.length * 2;
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(head + i) % elements.length];
}
elements = newElements;
head = 0;
tail = size;
}
public ArrayList<E> toArrayList() {
return IntStream.range(0, size)
.mapToObj(i -> elements[(head + i) % elements.length])
.collect(Collectors.toCollection(ArrayList::new));
}
}
// Main
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
SimpleArrayDeque<Integer> deque = new SimpleArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(0);
deque.addLast(3);
ArrayList<Integer> dequeList = deque.toArrayList();
System.out.println("=== dequeList === ");
System.out.println(dequeList);
System.out.println("First element: " + deque.getFirst());
System.out.println("Last element: " + deque.getLast());
System.out.println("=== dequeList === ");
dequeList = deque.toArrayList();
System.out.println(dequeList);
System.out.println("Removed first element: " + deque.removeFirst());
System.out.println("Remove last element: " + deque.removeLast());
System.out.println("=== dequeList === ");
dequeList = deque.toArrayList();
System.out.println(dequeList);
System.out.println("Deque size: " + deque.size());
System.out.println("Is deque empty? " + deque.isEmpty());
System.out.println("=== dequeList === ");
dequeList = deque.toArrayList();
System.out.println(dequeList);
}
}
/*
=== 출력 ===
=== dequeList ===
[0, 1, 2, 3]
First element: 0
Last element: 3
=== dequeList ===
[0, 1, 2, 3]
Removed first element: 0
Remove last element: 3
=== dequeList ===
[1, 2]
Deque size: 2
Is deque empty? false
=== dequeList ===
[1, 2]
*/
4️⃣ 입력 제한 Deque(Input-Restricted Deque).
입력 제한 Deque(Input-Restricted Deque)은 덱의 한쪽 끝에서만 삽입이 가능하고, 양쪽 끝에서 삭제가 가능한 자료구조입니다.
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class InputRestrictedDeque<E> {
private static final int DEFAULT_CAPACITY = 10;
private E[] elements;
private int head;
private int tail;
private int size;
@SuppressWarnings("unchecked")
public InputRestrictedDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
head = 0;
tail = 0;
size = 0;
}
public void addLast(E e) {
if (size == elements.length) {
resize();
}
elements[tail] = e;
tail = (tail + 1) % elements.length;
size++;
}
public E removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
E element = elements[head];
elements[head] = null; // for garbage collection
head = (head + 1) % elements.length;
size--;
return element;
}
public E removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
tail = (tail - 1 + elements.length) % elements.length;
E element = elements[tail];
elements[tail] = null; // for gatbage collection
size--;
return element;
}
public E getFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
return elements[head];
}
public E getLast() {
if (size == 0) {
throw new NoSuchElementException();
}
return elements[(tail - 1 + elements.length) % elements.length];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private void resize() {
int newCapacity = elements.length * 2;
@SuppressWarnings("unchecked")
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(head + i) % elements.length];
}
elements = newElements;
head = 0;
tail = size;
}
public ArrayList<E> toArrayList() {
return IntStream.range(0, size)
.mapToObj(i -> elements[(head + i) % elements.length])
.collect(Collectors.toCollection(ArrayList::new));
}
}
// Main
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
InputRestrictedDeque<Integer> deque = new InputRestrictedDeque<>();
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
ArrayList<Integer> dequeList = deque.toArrayList();
System.out.println("=== dequeList ===");
System.out.println(dequeList);
System.out.println("First element: " + deque.getFirst());
System.out.println("Last element: " + deque.getLast());
System.out.println("=== dequeList ===");
dequeList = deque.toArrayList();
System.out.println(dequeList);
System.out.println("Remove first element: " + deque.removeFirst());
System.out.println("Remove last elment: " + deque.removeLast());
System.out.println("=== dequeList ===");
dequeList = deque.toArrayList();
System.out.println(dequeList);
System.out.println("Deque size: " + deque.size());
System.out.println("Is deque empty? " + deque.isEmpty());
}
}
/*
=== 출력 ===
=== dequeList ===
[1, 2, 3]
First element: 1
Last element: 3
=== dequeList ===
[1, 2, 3]
Remove first element: 1
Remove last elment: 3
=== dequeList ===
[2]
Deque size: 1
Is deque empty? false
*/
1️⃣ 코드 설명.
배열 초기화 : DEFAULT_CAPACITY 크기의 배열을 초기화하고, head, tail, size 변수를 초기화합니다.
삽입 연산(addLast) : 요소를 덱의 마지막 에 추가합니다. 배열이 가득 차면 크기를 두 배로 늘립니다.
삭제 연산(removeFirst, removeLaste) : 첫 번째 요소와 마지막 요소를 각각 제거합니다.
조회 연산(getFirst, getLast) : 첫 번째 요소와 마지막 요소를 반환합니다.
기타 메서드 : size 와 isEmpty 메서드는 덱의 크기와 덱이 비어 있는지 여부를 반환합니다.
배열 크기 조정 (resize) : 배열이 가득 찰 때 호출되며, 배열의 크기를 두 배로 늘리고 요소를 새 배열로 복사합니다.
이 예제에서는 요소를 덱의 끝에만 삽입할 수 있는 입력 제한 덱을 구현했습니다.
필요에 따라 이 구현을 확장하거나 수정하여 요구사항에 맞게 사용할 수 있습니다.
5️⃣ 출력 제한 Deque(Output-Restricted Deque).
출력 제한 Deque(Output-Restricted Deque)은 양쪽 끝에서 삽입이 가능하지만, 한쪽 끝에서만 삭제가 가능한 자료 구조입니다.
이 구조는 양쪽 끝에서 요소를 추가할 수 있지만, 삭제는 한쪽 끝에서만 할 수 있습니다.
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class OutputRestrictedDeque<E> {
private static final int DEFAULT_CAPACITY = 10;
private E[] elements;
private int head;
private int tail;
private int size;
@SuppressWarnings("unchecked")
public OutputRestrictedDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
head = 0;
tail = 0;
size = 0;
}
public void addFirst(E e) {
if (size == elements.length) {
resize();
}
head = (head - 1 + elements.length) % elements.length;
elements[head] = e;
size++;
}
public void addLast(E e) {
if (size == elements.length) {
resize();
}
elements[tail] = e;
tail = (tail + 1) % elements.length;
size++;
}
public E removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
E element = elements[head];;
elements[head] = null; // for garbage collection
head = (head + 1) % elements.length;
size--;
return element;
}
public E getFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
return elements[head];
}
public E getLast() {
if (size == 0) {
throw new NoSuchElementException();
}
return elements[(tail - 1 + elements.length) % elements.length];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private void resize() {
int newCapacity = elements.length * 2;
@SuppressWarnings("unchecked")
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(head + 1) % elements.length];
}
elements = newElements;
head = 0;
tail = size;
}
public ArrayList<E> toArrayList() {
return IntStream.range(0, size)
.mapToObj(i -> elements[(head + i) % elements.length])
.collect(Collectors.toCollection(ArrayList::new));
}
}
// Main
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
OutputRestrictedDeque<Integer> deque = new OutputRestrictedDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.addFirst(0);
deque.addLast(3);
ArrayList<Integer> dequeList = deque.toArrayList();
System.out.println("=== dequeList === ");
System.out.println(dequeList);
System.out.println("First element: " + deque.getFirst());
System.out.println("Last element: " + deque.getLast());
System.out.println("=== dequeList === ");
dequeList = deque.toArrayList();
System.out.println(dequeList);
System.out.println("Remove first element: " + deque.removeFirst());
System.out.println("=== dequeList === ");
dequeList = deque.toArrayList();
System.out.println(dequeList);
System.out.println("Deque size: " + deque.size());
System.out.println("Is deque empty? " + deque.isEmpty());
System.out.println("=== dequeList === ");
dequeList = deque.toArrayList();
System.out.println(dequeList);
}
}
/*
=== 출력 ===
=== dequeList ===
[0, 1, 2, 3]
First element: 0
Last element: 3
=== dequeList ===
[0, 1, 2, 3]
Remove first element: 0
=== dequeList ===
[1, 2, 3]
Deque size: 3
Is deque empty? false
=== dequeList ===
[1, 2, 3]
*/
1️⃣ 코드 설명.
배열 초기화 : DEFAULT_CAPACITY 크기의 배열을 초기화하고, head, tail, size 변수를 초기화 합니다.
삽입 연산(addFirst, addLast) : 요소를 덱의 첫 번째 또는 마지막에 추가합니다. 배열이 가득 차면 크기를 두 배로 늘립니다.
삭제 연산(removeFirst) : 첫 번째 요소를 제거합니다. 출력 제한 덱에서는 첫 번째 요소만 제거할 수 있습니다.
조회 연산(getFirst, getLast) : 첫 번째 요소와 마지막 요소를 반환합니다.
기타 메서드 : size 와 isEmpty 메서드는 덱의 크기와 덱이 비어 있는지 여부를 반환합니다.
배열 크기 조정(resize) : 배열이 가득 찰 때 호출되며, 배열의 크기를 두 배로 늘리고 요소를 새 배열로 복사합니다.
이 예제에서는 요소를 덱의 양쪽 끝에서 삽입할 수 있고, 첫 번째 요소만 제거할 수 있는 출력 제한 덱을 구현했습니다.
필요에 따라 이 구현을 확장하거나 수정하여 요구사항에 맞게 사용할 수 있습니다.
-
📦[DS,Algorithm] Java의 배열.
1️⃣ Java의 배열.
1️⃣ 배열이란 무엇인가?
배열(Array)은 동일한 타입의 여러 요소를 하나의 변수로 관리할 수 있게 해주는 자료구조입니다.
배열은 연속된 메모리 공간에 할당되며, 각 요소는 인덱스를 통해 접근할 수 있습니다.
2️⃣ 배열의 선언과 초기화.
Java에서 배열은 다음과 같이 선언하고 초기화할 수 있습니다.
int[] array = new int[5]; // 크기가 5인 정수형 배열 선언.
int[] array = {10, 20, 30, 40, 50}; // 초기화와 동시에 배열 선언
3️⃣ 배열의 요소와 접근.
배열의 각 요소는 인덱스를 통해 접근할 수 있으며, 인덱스는 0부터 시작합니다.
int firstElement = array[0]; // element = 10, 첫 번째 요소에 접근
array[1] = 25; // [10, 25, 30, 40, 50], 두 번째 요소에 값 25를 저장
4️⃣ 배열의 시간 복잡도.
배열의 시간 복잡도는 연산의 종류에 따라 다릅니다.
아래는 일반적인 배열 연산과 그 시간 복잡도를 설명한 것입니다.
1. 접근(Access)
특정 인덱스의 요소에 접근하는 시간 복잡도는 O(1)입니다.
이유 : 배열은 연속된 메모리 공간에 저장되므로 인덱스를 통해 바로 접근할 수 있기 때문입니다.
// 접근(Access)
int element = array[2];
// element = 30, time complexity = O(1)
// [10, 25, 30, 40, 50]
2. 탐색(Search)
배열에서 특정 값을 찾는 시간 복잡도는 O(n)입니다.
이유: 최악의 경우 배열의 모든 요소를 검사해야 할 수도 있기 때문입니다.
boolean found = false;
int target = 30;
for (int i = 0; i < array.length; i++) {
if (array[i] == target) { // i = 2, array[i] = 30
found = true;
break;
}
}
// [10, 25, 30, 40, 50]
3. 삽입(Insertion)
배열의 끝에 요소를 추가하는 시간 복잡도는 O(1)입니다.
배열의 특정 위치에 요소를 삽입하는 시간 복잡도는 O(n)입니다.
이유: 특정 위치에 삽입하기 위해서는 해당 위치 이후의 모든 요소를 한 칸씩 뒤로 밀어야 하기 때문입니다.
// 삽입(Insertion)
// 배열 삽입시 index가 array.length가 아니고 array.length - 1인 이유는
// array.length는 배열의 크기, 즉 5를 나타내기 때문입니다.
// index는 0부터 시작하기 때문에 배열의 크기가 5인 배열의 끝 index는 4입니다.
// 때문에 array.length - 1을 해줍니다.
array[array.length - 1] = 60; // 배열 끝에 삽입 (O(1)), [10, 25, 30, 40, 60]
// 배열 중간에 삽입하는 메서드
public static void insertion(int[] array, int index, int insertValue) {
// 배열 중간에 삽입(O(n))
for (int i = array.length - 1; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = insertValue;
System.out.println(Arrays.toString(array));
}
4. 삭제(Deletion)
배열의 끝에서 요소를 제거하는 시간 복잡도는 O(1)입니다.
배열의 특정 위치의 요소를 제거하는 시간 복잡도는 O(n)입니다.
이유: 특정 위치의 요소를 제거한 후에는 해당 위치 이후의 모든 요소를 한 칸씩 앞으로 당겨야 하기 때문입니다.
// 삭제(Deletion)
array[array.length - 1] = 0; // 배열의 끝에서 삭제 ((O(1)), [10, 25, 30, 77, 0]
System.out.println(Arrays.toString(array));
// 배열 중간에서 삭제하는 메서드
int deletionValue = deletion(array, 2);
System.out.println(deletionValue); // 30
// 배열 중간에 삭제하는 메서드
public static int deletion(int[] array, int index) {
// 배열 중간에 삭제(O(n))
int[] returnValue = new int[array.length];
for (int i = index, j = 0; i < array.length - 1 ; i++) {
returnValue[j] = array[i];
j++;
array[i] = array[i + 1];
}
array[array.length - 1] = 0; // 마지막 요소 초기화.
int deletionValue = returnValue[0]; // 배열을 메모리에서 지우기
returnValue = null;
return deletionValue;
}
5️⃣ 배열의 장점과 단점.
장점.
빠른 접근 속도 : 인덱스를 통해 O(1) 시간에 요소를 접근할 수 있습니다.
메모리 효율 : 연속된 메모리 공간을 사용하므로 메모리 사용이 효율적입니다.
단점.
고정된 크기 : 배열의 크기는 선언 시에 고정되므로, 실행 중에 크기를 변경할 수 없습니다.
삽입 및 삭제의 비효율성 : 배열 중간에 요소를 삽입하거나 삭제할 때 O(n)의 시간이 소요됩니다.
연속된 메모리 할당 필요 : 큰 배열을 사용할 떄는 연속된 메모리 공간이 필요하여 메모리 할당에 제한이 있을 수 있습니다.
배열은 이러한 특성들로 인해 빠른 접근이 필요한 상황에서는 매우 유용하지만, 삽입 및 삭제가 빈번히 일어나는 경우에는 비효율적일 수 있습니다.
따라서 상황에 맞게 적절한 자료구조를 선택하는 것이 중요합니다.
-
📦[DS,Algorithm] 배열에서 특정 인덱스의 요소를 삭제하기.
1️⃣ 배열에서 특정 인덱스의 요소를 삭제하기.
Java에서 배열의 특정 인덱스의 요소를 삭제하는 방법은 배열의 구조 특성상 직접적으로 제공되지 않습니다.
때문에 일반적으로 요소를 삭제하기 위해 다음의 방법을 사용합니다.
2️⃣ 배열에서 요소를 삭제하는 방법 2가지.
1️⃣ 새로운 배열을 생성하여 요소를 복사하는 방법 :)
● 특정 인덱스의 요소를 건너뛰고 나머지 요소를 새로운 배열에 복사합니다.
방법 1 : 새로운 배열 생성하여 복사.
// 배열의 특정 인덱스의 요소를 삭제하는 방법 - 1
// 방법1. 새로운 배열을 생성하여 요소를 복사하는 방법
// - 특정 인덱스의 요소를 건너뛰고 나머지 요소를 새로운 배열에 복사합니다.
public class Main {
public static void main(String[] args) {
int[] array = {10, 20, 30, 40, 50};
array = removeElement(array, 0);
for (int value : array) {
System.out.println(value + " ");
}
}
// 특정 배열을 지우는 메소드
public static int[] removeElement(int[] array, int index) {
if (index < 0 || index >= array.length) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
// 새로운 배열은 특정 요소를 지우기 때문에 기존 배열의 크기에서 -1 한 크기로 생성합니다.
int[] newArray = new int[array.length - 1];
for (int i = 0, j = 0; i < array.length; i++) {
if (i != index) {
newArray[j++] = array[i];
}
}
return newArray;
}
}
/*
=== 출력 ===
20
30
40
50
*/
“방법1의 장.단점”
새 배열 생성 : 메모리 사용량이 증가하지만, 원래 배열을 유지하고 싶은 경우 유용합니다.
2️⃣ 기존 배열을 이용하여 요소를 덮어쓰는 방법 :)
● 특정 인덱스 이후의 요소들을 앞으로 한 칸씩 이동시켜 덮어씁니다.
방법 2 : 기존 배열을 이용하여 요소 덮어쓰기.
// 배열의 특정 인덱스의 요소를 삭제하는 방법 - 2
// 방법2. 기존 배열을 이용하여 요소를 덮어쓰는 방법.
// - 특정 인덱스 이후의 요소들을 앞으로 한 칸씩 이동시켜 덮어 씁니다.
public class Main {
public static void main(String[] args) {
int[] array = {10, 20, 30, 40, 50};
array = removeElementInPlace(array, 0);
for (int value : array) {
System.out.println(value + " ");
}
}
public static int[] removeElementInPlace(int[] array, int index) {
if (index < 0 || index >= array.length) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
for (int i = index; i < array.length - 1; i++) {
array[i] = array[i + 1];
}
// 배열의 마지막 요소를 0 또는 다른 기본값으로 설정 (선택 사항)
array[array.length - 1] = 0;
return array;
}
}
/*
=== 출력 ===
20
30
40
50
0
*/
“방법2의 장.단점”
기존 배열 사용 : 메모리를 절약할 수 있지만, 배열의 마지막 요소는 기본값으로 설정해야 합니다.
-
-
📦[DS,Algorithm] 스택(Stack)
1️⃣ 스택(Stack).
스택(Stack)은 자료구조의 한 종류로, 데이터가 일렬로 쌓이는 구조를 가지고 있습니다.
1️⃣ 스택(Stack)의 특징.
“후입선출(LIFO, Last In First Out)”로, 가장 나중에 삽입된 데이터가 가장 먼저 꺼내진다는 점이 특징입니다.
2️⃣ 스택(Stack)의 기본 연산.
푸시(Push) : 스택의 맨 위에 데이터를 삽입하는 연산.
팝(Pop) : 스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산.
3️⃣ 스택(Stack)의 부가적인 연산.
피크(peek) 또는 탑(top) : 스택의 맨 위에 있는 데이터를 제거하지 않고 반환하는 연산.
isEmpty : 스택이 비어 있는지 여부를 확인하는 연산.
size : 스택에 있는 데이터의 개수를 반환하는 연산.
4️⃣ 스택(Stack)의 실제 응용 사례.
웹 브라우저의 방문 기록(뒤로 가기 기능)
함수 호출시의 호출 스택
역폴란드 표기법 계산 등
5️⃣ 스택(Stack)의 구현.
스택은 배열이나 연결 리스트를 이용하여 구현할 수 있습니다.
배열을 이용한 스택 구현은 고정된 크기를 가지며, 연결 리스트를 이용한 스택 구현은 동적으로 크기를 조절할 수 있습니다.
배열을 이용한 스택 : 고정된 크기의 배열을 사용하여 스택을 구현할 수 있습니다. 이 경우 스택의 크기가 초과되면 더 큰 배열로 복사하는 추가 작업이 필요할 수 있습니다.
연결 리스트를 이용한 스택 : 동적으로 크기를 조절할 수 있는 연결 리스트를 사용하여 스택을 구현할 수 있습니다. 연결 리스트의 노드 삽입 및 삭제는 O(1)의 시간 복잡도를 가지므로, 스택 연산을 효율적으로 수행할 수 있습니다.
6️⃣ 시간 복잡도
스택의 각 연산은 일반적으로 다음과 같은 시간 복잡도를 가집니다.
Push : O(1)
데이터를 스택의 맨 위에 추가하는 연산은 항상 일정한 시간 내에 완료됩니다.
Pop : O(1)
데이터를 스택의 맨 위에서 제거하는 연산도 항상 일정한 시간 내에 완료됩니다.
Peek 또는 Top : O(1)
스택의 맨 위에 있는 데이터를 확인하는 연산은 데이터 접근만 필요하기 때문에 일정한 시간 내에 완료됩니다.
isEmpty : O(1)
스택이 비어 있는지 확인하는 연산은 스택의 크기만 확인하면 되프로 일정한 시간 내에 완료됩니다.
Size : O(1)
스택에 있는 데이터의 개수를 반환하는 연산은 스택의 크기 정보를 유지하고 있으면 일정한 시간 내에 완료됩니다.
7️⃣ 스택 구현.
// Stack
public class Stack {
private int maxSize; // 스택의 최대 크기
private int top; // 스택의 맨 위를 가리키는 인덱스
private int[] stackArray; // 스택을 저장할 배열
// 생성자
public Stack(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1; // 스택이 비어있음을 나타냄
}
// 스택에 값을 푸시하는 메소드
public void push(int value) {
if (isFull()) {
System.out.println("스택이 가득 찼습니다.");
return;
}
stackArray[++top] = value;
}
// 스택에서 값을 팝하는 메소드
public int pop() {
if (isEmpty()) {
System.out.println("스택이 비어있습니다.");
return -1; // 에러를 나타내기 위해 -1 반환
}
return stackArray[top--];
}
// 스택의 맥 위 값을 반환하는 메소드
public int peek() {
if (isEmpty()) {
System.out.println("스택이 비어있습니다.");
return -1; // 에러를 나타내기 위해 -1 반환
}
return stackArray[top];
}
// 스택이 비어있는지 확인하는 메소드
public boolean isEmpty() {
return (top == -1);
}
// 스택이 가득 찼는지 확인하는 메소드
public boolean isFull() {
return (top == maxSize -1);
}
// 스택의 크기를 반환하는 메소드
public int size() {
return top + 1;
}
}
// Main
public class Main {
public static void main(String[] args) {
Stack stack = new Stack(5); // 크기가 5인 스택 생성
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println("스택의 맨 위 값 : " + stack.peek());
System.out.println("스택의 크기 : " + stack.size());
while (!stack.isEmpty()) {
System.out.println("팝 : " + stack.pop());
}
System.out.println("스택의 크기 : " + stack.size());
}
}
/*
===출력===
스택의 맨 위 값 : 5
스택의 크기 : 5
팝 : 5
팝 : 4
팝 : 3
팝 : 2
팝 : 1
스택의 크기 : 0
*/
주요 메서드 설명
push(int value) : 스택의 맨 위에 값을 추가합니다. 스택이 가득 찼을 경우, 에러 메시지를 출력합니다.
pop() : 스택의 맨 위 값을 제거하고 반환합니다. 스택이 비어 있을 경우, 에러 메시지를 출력하고 -1을 반환합니다.
peek() : 스택의 맨 위 값을 반환하지만, 스택에서 제거하지는 않습니다. 스택이 비어 있을 경우, 에러 메시지를 출력하고 -1을 반환합니다.
isEmpty() : 스택이 비어 있는지 여부를 확인합니다.
isFull() : 스택이 가득 찼는지 여부를 확인합니다.
size() : 스택에 현재 저장된 데이터의 개수를 반환합니다.
-
📦[DS,Algorithm] 트리(Tree)
1️⃣ 트리(Tree).
트리(Tree) 는 계층적 구조를 나타내는 자료구조로, 노드(Node)와 에지(Edge)로 구성됩니다.
트리는 사이클이 없는 연결 그래프(Connected Graph)이며, 계층적 데이터 표현에 매우 유용합니다.
트리는 부모-자식 관계를 가지며, 데이터의 조직화와 검색, 계층적 데이터 표현에 사용됩니다.
1️⃣ 트리의 구성 요소.
노드(Node) : 트리의 기본 단위로, 데이터를 저장합니다.
에지(Edge) : 노드와 노드를 연결하는 선으로, 부모-자식 관계를 나타냅니다.
루트(Root) : 트리의 최상위 노드로, 부모 노드가 없습니다.
부모(Parent) : 다른 노드를 가리키는 노드입니다.
자식(Child) : 부모 노드에 의해 가리켜지는 노드입니다.
잎(Leaf) : 자식 노드가 없는 노드입니다.
내부 노드(Internal Node) : 자식 노드가 있는 노드입니다.
레벨(Level) : 루트 노드에서 특정 노드까지의 에지 수를 나타냅니다.
높이(Height) : 트리의 최대 레벨을 의미합니다.
2️⃣ 트리의 특성.
계층적 구조 : 트리는 계층적 구조로 데이터를 조직화합니다.
사이클 없음 : 트리는 사이클이 없는 그래프입니다.
연결성 : 모든 노드는 하나의 연결된 구성 요소로 되어 있습니다.
한 개의 루트 노드 : 트리는 하나의 루트 노드를 가지며, 루트 노드는 트리의 시작점입니다.
3️⃣ 트리의 종류.
이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리입니다.
이진 탐색 트리(Binary Search Tree, BST) : 이진 트리의 일종으로, 왼쪽 자식 노드의 값이 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값이 부모 노드의 값보다 큰 특성을 가집니다.
균형 이진 트리(Balanced Binary Tree) : AVL 트리, 레드-블랙 트리 등과 같이 트리의 높이가 균형을 이루도록 유지하는 트리입니다.
B-트리(B-Tree) : 데이터베이스와 파일 시스템에서 사용되는 트리로, 자식 노드의 수가 정해진 다진 트리(Multiway Tree)입니다.
힙(Heap) : 완전 이진 트리의 일종으로, 부모 노드의 값이 자식 노드의 값보다 크거나 작은 특성을 가집니다.
트라이(Trie) : 문자열 검색을 위한 트리 자료구조로, 접두사 검색에 유용합니다.
4️⃣ 트리의 주요 연산.
삽입(Insertion) : 트리에 새로운 노드를 추가합니다.
삭제(Deletion) : 트리에서 노드를 제거합니다.
탐색(Search) : 트리에서 특정 값을 찾습니다.
순회(Traversal) : 트리의 모든 노드를 방문합니다. 전위(Preorder), 중위(Inorder), 후위(Postorder), 레벨 순회(Level Order) 방식이 있습니다.
-
-
📦[DS,Algorithm] 완전 이진 트리(Complete Binary Tree)
1️⃣ 완전 이진 트리(Complete Binary Tree).
완전 이진 트리(Complete Binary Tree)는 이진 트리의 한 종류입니다.
1️⃣ 완전 이진 트리(Complete Binary Tree)의 특성.
모든 레벨이 완전히 채워져 있다.
마지막 레벨을 제외한 모든 레벨의 노드가 최대 개수로 채워져 있습니다.
마지막 레벨의 노드들은 왼쪽부터 오른쪽으로 채워져 있습니다.
노드의 배치
트리의 높이가 ‘h’ 라면, 마지막 레벨을 제외한 모든 레벨에는 ‘2^k’ 개의 노드가 있습니다. 여기서 ‘k’ 는 해당 레벨의 깊이 입니다.
마지막 레벨에는 1개 이상 ‘2^h’ 개 이하의 노드가 있으며, 이 노드들은 왼쪽부터 채워집니다.
2️⃣ 완전 이친 트리의 예.
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
위의 트리는 완전 이진 트리의 예입니다.
모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 오른쪽으로 채워져있습니다.
3️⃣ 완전 이진 트리의 속성.
노드 수
높이가 ‘h’ 인 완전 이진 트리는 최대 ‘2^(h+1) - 1’ 개의 노드를 가질 수 있습니다.
마지막 레벨을 제외한 모든 노드는 ‘2^h - 1’ 개의 노드를 가집니다.
높이
노드 수가 ‘n’ 인 완전 이진 트리의 높이는 ‘O(log n)’ 입니다.
배열 표현
완전 이진 트리는 배열을 사용하여 쉽게 표현할 수 있습니다. 이는 힙 자료구조에서 많이 사용됩니다.
4️⃣ 배열을 통한 완전 이진 트리 표현
완전 이진 트리는 배열을 사용하여 효율적으로 표현할 수 있습니다.
노드의 인덱스를 기준으로 부모-자식 관계를 쉽게 파악할 수 있습니다.
노드의 인덱스 규칙
루트 노드 : 인덱스 0
인덱스 ‘i’의 오른쪽 자식 노드 : ‘2*i + 1’
인덱스 ‘i’의 부모 노드 : ‘(i - 1) / 2’
5️⃣ 예제 코드
아래는 완전 이진 트리를 배열로 표현하고, 이를 출력하는 간단한 예제 코드입니다.
public class CompleteBinaryTree {
public static void main(String[] args) {
int[] tree = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 트리 출력
printTree(tree);
}
// 배열로 표현된 완전 이진 트리 출력
public static void printTree(int[] tree) {
for (int i = 0; i < tree.length; i++) {
int leftChildIndex = 2 * i + 1;
int rightChildIndex = 2 * i + 2;
System.out.print("Node " + tree[i] + ": ");
if (leftChildIndex < tree.length) {
System.out.print("Left Child: " + tree[leftChildIndex] + ", ");
} else {
System.out.print("Left Child: null, ");
}
if (rightChildIndex < tree.length) {
System.out.print("Right Child: " + tree[rightChildIndex]);
} else {
System.out.print("Right Child: null");
}
System.out.println();
}
}
}
/* 출력
Node 1: Left Child: 2, Right Child: 3
Node 2: Left Child: 4, Right Child: 5
Node 3: Left Child: 6, Right Child: 7
Node 4: Left Child: 8, Right Child: 9
Node 5: Left Child: null, Right Child: null
Node 6: Left Child: null, Right Child: null
Node 7: Left Child: null, Right Child: null
Node 8: Left Child: null, Right Child: null
Node 9: Left Child: null, Right Child: null
*/
설명
트리 배열 초기화 : int[] tree = {1, 2, 3, 4, 5, 6, 7, 8, 9};
완전 이진 트리를 배열로 표현합니다.
트리 출력 : printTree(tree)
배열로 표현된 완전 이진 트리를 출력하는 함수입니다.
각 노드에 대해 왼쪽 자식과 오른쪽 자식을 출력합니다.
시간 복잡도
삽입(Insertion) : O(log n)
삭제(Deletion) : O(log n)
탐색(Search) : O(n) (일반적으로 완전 이진 트리는 탐색보다 삽입/삭제가 주된 연산입니다.)
완전 이진 트리는 데이터의 구조적 특성 때문에 힙과 같은 자료구조에서 많이 사용됩니다.
이는 효율적인 삽입 및 삭제 연산을 제공하며, 배열을 통한 표현이 간편하여 다양한 알고리즘에서 유용하게 사용됩니다.
-
📦[DS,Algorithm] 이진 트리(Binary Tree)
1️⃣ 이진 트리(Binary Tree).
이진 트리(Binary Tree) 는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다.
이 두 자식 노드는 일반적으로 왼쪽 자식(Left Child) 과 오른쪽 자식(Right Child) 이라고 불립니다.
이진 트리는 다양한 응용 프로그램에서 중요한 자료구조입니다.
1️⃣ 이진 트리의 구성 요소.
노드(Node) : 데이터를 저장하는 기본 단위입니다.
루트(Root) : 트리의 최상위 노드입니다.
자식(Child) : 특정 노드로부터 연결된 하위 노드입니다.
부모(Parent) : 특정 노드를 가리키는 상위 노드입니다.
잎(Leaf) : 자식 노드가 없는 노드입니다.
서브트리(Subtree) : 특정 노드와 그 노드의 모든 자식 노드로 구성된 트리입니다.
2️⃣ 이진 트리의 종류.
포화 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리입니다.
완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 채워져 있는 트리입니다.
높이 균형 이진 트리(Height-balanced binary Tree) : AVL 트리와 같이 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리입니다.
이진 탐색 트리(Binary Search Tree, BST) : 왼쪽 서브트리의 모든 노드가 루트 노드보다 작고, 오른쪽 서브 트리의 모든 노드가 루트 노드보다 큰 트리입니다.
3️⃣ 이진 트리의 주요 연산 및 시간 복잡도.
삽입(Insertion) : 새로운 노드를 트리에 추가합니다.
일반적인 경우 시간 복잡도 : O(log n)(이진 탐색 트리에서)
최악의 경우 시간 복잡도 : O(n)(편향된 트리에서)
삭제(Deletion) : 트리에서 특정 노드를 제거합니다.
일반적인 경우 시간 복잡도 : O(log n)(이진 탐색 트리에서)
최악의 경우 시간 복잡도: O(n)(편향된 트리에서)
탐색(Search) : 트리에서 특정 값을 찾습니다.
일반적인 경우 시간 복잡도: O(log n)(이진 탐색 트리에서)
최악의 경우 시간 복잡도 : O(n)(편향된 트리에서)
순회(Traversal) : 트리의 모든 노드를 방문합니다. 순회 방법에는 전위(Preorder), 중위(Inorder), 후위(Postorder) 순회가 있습니다.
시간 복잡도: O(n)(모든 노드를 방문하기 때문에)
4️⃣ 이진 트리의 예제
이진 탐색 트리(BST)의 구현
// TreeNode
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// BinarySearchTree
public class BinarySearchTree {
private TreeNode root;
public BinarySearchTree() {
this.root = null;
}
// 삽입 연산
public void insert(int data) {
root = insertRec(root, data);
}
private TreeNode insertRec(TreeNode root, int data) {
if (root == null) {
root = new TreeNode(data);
return root;
}
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
// 탐색 연산
public boolean search(int data) {
return searchRec(root, data);
}
private boolean searchRec(TreeNode root, int data) {
if (root == null) {
return false;
}
if (root.data == data) {
return true;
}
if (data < root.data) {
return searchRec(root.left, data);
} else {
return searchRec(root.right, data);
}
}
// 중위 순회(Inorder Traversal)
public void inorder() {
inorderRec(root);
}
private void inorderRec(TreeNode root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
}
// Main
public class Main {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
System.out.println("Inorder traversal of the BST:");
bst.inorder(); // 출력: 20 30 40 50 60 70 80
System.out.println("\nSearch for 40: " + bst.search(40)); // 출력: true
System.out.println("Search for 90: " + bst.search(90)); // 출력: false
}
}
-
📦[DS,Algorithm] 해시 테이블(Hash Table)
1️⃣ 해시 테이블(Hash Table).
해시 테이블(Hash Table)은 데이터를 키-값 쌍(key-value pairs)으로 저장하는 자료구조입니다.
해시 테이블은 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이 해시 값을 인덱스로 사용하여 배열에서 값을 저장하거나 검색합니다.
이를 통해 데이터에 빠르게 접근할 수 있습니다.
1️⃣ 해시 테이블의 구성 요소.
키(key) : 각 데이터를 식별하기 위한 고유한 식별자입니다.
값(Value) : 키와 연관된 데이터입니다.
해시 함수(Hash Function) : 키를 입력으로 받아 해시 값을 출력하는 함수입니다. 이 해시 값은 보통 정수이며, 배열의 인덱스로 사용됩니다.
버킷(Bucket) : 해시 값에 의해 인덱싱되는 배열의 각 위치입니다. 각 버킷은 하나의 키-값 쌍 또는 충돌 처리를 위한 데이터 구조(예: 연결 리스트)를 저장할 수 있습니다.
2️⃣ 해시 함수의 역할.
해시 함수는 키를 고정된 크기의 해시 값으로 매핑합니다.
이상적인 해시 함수는 키를 균등하게 분포시키고, 충돌을 최소화합니다.
3️⃣ 충동(Collision)과 충돌 해결 방법.
두 개 이상의 키가 동일한 해시 값을 가질 때 충돌이 발생합니다.
해시 테이블은 이러한 충돌을 처리하기 위한 여러가지 방법을 제공합니다.
체이닝(Chaining) : 각 버킷에 연결 리스트를 사용하여 동일한 해시 값을 갖는 모든 요소를 저장합니다. 충돌이 발생하면 해당 버킷의 리스트에 요소를 추가합니다.
개방 주소법(Open Addressing) : 충돌이 발생하면 다른 빈 버킷을 찾아 데이터를 저장합니다. 이를 위해 다양한 탐사 방법(예: 선형 탐사, 제곱 탐사, 이중 해싱)을 사용합니다.
4️⃣ 해시 테이블의 시간 복잡도.
검색(Search) : O(1)(평균), O(n)(최악)
삽입(Insertion) : O(1)(평균), O(n)(최악)
삭제(Deletion) : O(1)(평균), O(n)(최악)
최악의 경우 시간 복잡도는 해시 충돌로 인해 모든 요소가 하나의 버킷에 저장될 때 발생합니다.
그러나, 좋은 해시 함수와 충돌 해결 방법을 사용하면 평균적으로 O(1)의 성능을 유지할 수 있습니다.
5️⃣ 해시 테이블의 장점과 단점.
장점
빠른 검색, 삽입, 삭제 성능(평균적으로 O(1))
키를 사용하여 데이터에 빠르게 접근 가능
단점
해시 함수의 성능에 의존
충돌 처이 필요
메모리 사용량이 증가할 수 있슴(특히 체이닝을 사용하는 경우)
💻 해시 테이블의 구현 예제.
아래는 Java에서 간단한 해시 테이블을 구현한 예제입니다.
// HashTable
import java.util.LinkedList;
class HashTable {
private class HashNode {
String key;
String value;
HashNode next;
public HashNode(String key, String value) {
this.key = key;
this.value = value;
}
}
private LinkedList<HashNode>[] buckets;
private int numBuckets;
private int size;
public HashTable() {
numBuckets = 10; // 버킷의 초기 크기
buckets = new LinkedList[numBuckets];
size = 0;
for (int i = 0; i < numBuckets; i++) {
buckets[i] = new LinkedList<>();
}
}
private int getBucketIndex(String key) {
int hashCode = key.hashCode();
int index = hashCode % numBuckets;
return index < 0 ? index * -1 : index;
}
public void put(String key, String value) {
int bucketIndex = getBucketIndex(key);
LinkedList<HashNode> bucket = buckets[bucketIndex];
for (HashNode node : bucket) {
if (node.key.equals(key)) {
node.value = value;
return;
}
}
bucket.add(new HashNode(key, value));
size++;
}
public String get(String key) {
int bucketIndex = getBucketIndex(key);
LinkedList<HashNode> bucket = buckets[bucketIndex];
for (HashNode node : bucket) {
if (node.key.equals(key)) {
return node.value;
}
}
return null;
}
public String remove(String key) {
int bucketIndex = getBucketIndex(key);
LinkedList<HashNode> bucket = buckets[bucketIndex];
HashNode prev = null;
for (HashNode node : bucket) {
if (node.key.equals(key)) {
if (prev != null) {
prev.next = node.next;
} else {
bucket.remove(node);
}
size--;
return node.value;
}
prev = node;
}
return null;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
// Main
public class Main {
public static void main(String[] args) {
HashTable hashTable = new HashTable();
hashTable.put("one", "1");
hashTable.put("two", "2");
hashTable.put("three", "3");
System.out.println("Value for key 'one': " + hashTable.get("one"));
System.out.println("Value for key 'two': " + hashTable.get("two"));
System.out.println("Removing key 'one': " + hashTable.remove("one"));
System.out.println("Contains key 'one': " + (hashTable.get("one") != null));
}
}
/*
출력
Value for key 'one': 1
Value for key 'two': 2
Removing key 'one': 1
Contains key 'one': false
*/
-
📦[DS,Algorithm] 해시(Hash)
1️⃣ 해시(Hash).
해시(Hash)란 컴퓨터 과학에서 주어진 입력 데이터를 고정된 크기의 고유한 값(일반적으로 숫자)으로 변환하는 과정 또는 그 결과 값을 말합니다.
해시는 주로 데이터 검색, 데이터 무결성 검증, 암호화 등에 사용됩니다.
1️⃣ 해시의 개념.
해시 함수(Hash Function)
임의의 길이를 가진 데이터를 고정된 길이의 해시 값으로 변환하는 함수입니다.
해시 함수는 동일한 입력에 대해 항상 동일한 해시 값을 생성해야 하며, 서로 다른 입력에 대해서는 가능한 한 다른 해시 값을 생성해야 합니다.
해시 값(Hash Value)
해시 함수를 통해 생성된 고정된 크기의 출력 값입니다.
이를 해시 코드(Hash Code) 또는 다이제스트(Digest)라고도 합니다.
2️⃣ 해시 함수의 특징.
결정성(Deterministic) : 동일한 입력에 대해 항상 동일한 해시 값을 반환합니다.
효율성(Efficiency) : 해시 함수는 입력 데이터를 빠르게 처리하여 해시 값을 생성해야 합니다.
충돌 저항성(Collision Resistance) : 서로 다른 두 입력이 동일한 해시 값을 갖지 않도록 해야 합니다. 현실적으로 완벽한 충돌 저항성은 불가능하므로, 가능한 충돌을 최소화하는 것이 중요합니다.
역상 저항성(Pre-image Resistance) : 해시 값을 통해 원해의 입력 데이터를 유추하는 것이 어렵거나 불가능해야 합니다.
두 번째 역상 저항성(Second Pre-image Resitance) : 특정 입력과 동일한 해시 값을 갖는 또 다른 입력을 찾는 또 다른 입력을 찾는 것이 어려워야 합니다.
3️⃣ 해시 함수의 용도.
데이터 검색 : 해시 테이블(Hash Table)과 같은 자료구조에서 빠른 데이터 검색을 위해 사용됩니다.
데이터 무결성 검증 : 데이터가 변경되지 않았음을 확인하기 위해 해시 값을 사용합니다. 예를 들어, 파일의 해시 값을 비교하여 파일이 손상되지 않았음을 확인할 수 있습니다.
암호화 및 보안 : 패스워드 저장, 디지털 서명, 메시지 인증 코드(MAC) 등에서 데이터의 무결성과 기밀성을 보장하기 위해서 사용됩니다.
4️⃣ 해시 함수의 예
SHA-256(Secure Hash Algorithm 256-bit) : 256비트의 해시 값을 생성하는 암호화 해시 함수입니다.
MD5(Message Digest Algorithm 5) : 128비트의 해시 값을 생성하는 해시 함수로, 현재는 충돌 저항성의 취약성 때문에 보안 용도로는 권장되지 않습니다.
CRC32(Cyclic Redundancy Check 32-bit) : 데이터 전송 오류 검출을 위해 사용되는 32비트 해시 함수입니다.
🙋♂️ 주요 포인트 요약
해시(Hash) 는 데이터를 고정된 크기의 고유한 값으로 변환하는 과정입니다.
해시 함수는 빠르고 효율적으로 해시 값을 생성하며, 충돌을 최소화하고 역상을 예측할 수 없도록 설계되어야 합니다.
해시 함수는 데이터 검색, 무결성 검증, 암호화 등 다양한 용도로 사용됩니다.
💻 해시 함수의 예제 코드
아래는 Java에서 SHA-256 해시 함수를 사용하여 문자열의 해시 값을 생성하는 예제입니다.
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class Main {
public static void main(String[] args) {
String input = "Hello World!";
try {
// SHA-256 해시 함수 인스턴스 생성
MessageDigest digest = MessageDigest.getInstance("SHA-256");
// 입력 문자열의 해시 값 계산
byte[] hash = digest.digest(input.getBytes());
// 해시 값을 16진수 문자열로 변환하여 출력
System.out.println("Hash value: " + bytesToHex(hash));
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
}
// 바이트 배열을 16진수 문자열로 변환하는 함수
private static String bytesToHex(byte[] bytes) {
StringBuilder hexString = new StringBuilder();
for (byte b : bytes) {
String hex = Integer.toHexString(0xff & b);
if (hex.length() == 1) hexString.append('0');
hexString.append(hex);
}
return hexString.toString();
}
}
-
-
-
📦[DS,Algorithm] 선형 자료구조 - 배열
1️⃣ 선형 자료구조 - 배열.
자료구조 관점에서 배열을 이해하고 여러 방법으로 구현 가능
1️⃣ 배열(Array).
자료구조 관점에서 배열(Array)은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 선형 자료구조입니다.
배열은 조정된 크기를 가지며, 인덱스를 사용하여 각 요소에 빠르게 접근할 수 있는 특징이 있습니다.
배열은 가장 기본적이고 널리 사용되는 자료구조 중 하나입니다.
특징.
고정된 크기(Fixed Size)
배열은 선언 시 크기가 결정되며, 배열의 크기는 변경할 수 없습니다. 이 크기는 배열을 사용하는 동안 고정되어 있습니다.
예: ‘int[] numbers = new int[10];‘(크기가 10인 정수형 배열)
연속된 메모리 공간(Contiguous Memory Allocation)
배열의 요소들은 메모리상에 연속적으로 배치됩니다. 이는 인덱스를 통한 빠른 접근을 가능하게 합니다.
첫 번째 요소의 메모리 주소를 기준으로 인덱스를 사용하여 다른 요소의 주소를 계산할 수 있습니다.
인덱스를 통한 접근(Indexing)
배열의 각 요소는 인덱스를 통해 접근할 수 있습니다. 인덱스는 0부터 시작하여 배열의 크기 -1까지의 값을 가집니다.
예: ‘numbers[0]’,’numbers[1]‘,…,’numbers[9]‘
동일한 데이터 타입(Homogeneous Data Type)
배열은 동일한 데이터 타입의 요소들로 구성됩니다. 즉, 배열 내 모든 요소는 같은 데이터 타입이어야 합니다.
예: 정수형 배열, 문자열 배열 등.
장점.
빠른 접근 속도(Fast Access) :
인덱스를 사용하여 O(1) 시간 복잡도로 배열의 임의의 요소에 접근할 수 있습니다. 이는 배열의 주요 장점 중 하나입니다.
간단한 구현(Simple Implementation) :
배열은 데이터 구조가 간단하여 구현이 용이합니다. 기본적인 자료구조로, 다른 복잡한 자료구조의 기초가 됩니다.
단점.
고정된 크기(Fixed Size) :
배열의 크기는 선언 시 결정되며, 크기를 변경할 수 없습니다. 이는 크기를 사전에 정확히 예측하기 어려운 경우 비효율적일 수 있습니다.
삽입 및 삭제의 비효율성(Inefficient Insertions and Deletions) :
배열의 중간에 요소를 삽입하거나 삭제할 경우, 요소들을 이동시켜야 하기 때문에 O(n) 시간이 소요됩니다. 이는 큰 배열의 경우 성능 저하를 초래할 수 있습니다.
메모리 낭비(Memory Waste) :
배열의 크기를 너무 크게 설정하면 사용되지 않는 메모리가 낭비될 수 있고, 너무 작게 설정하면 충분한 데이터를 저장할 수 없습니다.
배열의 사용 예시.
정수형 배열 선언 및 초기화
int[] numbers = new int[5];
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
numbers[3] = 40;
numbers[4] = 50;
배열의 요소 접근
int firstElement = numbers[0]; // 10
int lastElement = numbers[4]; // 50
배열의 순회
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
마무리.
배열은 다양한 상황에서 기본적인 데이터 저장과 접근 방법을 제공하며, 특정 요구사항에 맞춰 다른 자료구조와 함께 사용되기도 합니다.
배열의 빠른 접근 속도와 간단한 구조 덕분에, 많은 알고리즘과 프로그램에서 핵심적인 역할을 합니다.
2️⃣ 배열 직접 구현.
// CustomArray 클래스
public class CustomArray {
private int[] data;
private int size;
// 특정 용량으로 배열을 초기화하는 생성자
public CustomArray(int capacity) {
data = new int[capacity];
size = 0;
}
// 배열의 크기를 가져오는 메서드
public int size() {
return size;
}
// 배열이 비어 있는지 확인하는 메서드
public boolean isEmpty() {
return size == 0;
}
// 특정 인덱스의 요소를 가져오는 메서드
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
return data[index];
}
// 특정 인덱스에 요소를 설정하는 메서드
public void set(int index, int value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
data[index] = value;
}
// 배열에 요소를 추가하는 메서드
public void add(int value) {
if (size == data.length) {
throw new IllegalStateException("Array is full");
}
data[size] = value;
size++;
}
// 특정 인덱스의 요소를 삭제하는 메서드
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
}
// 모든 요소를 출력하는 메서드
public void print() {
for (int i = 0; i < size; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
설명.
필드:
‘data’ : 실제 데이터를 저장하는 배열.
‘size’ : 현재 배열에 저장된 요소의 개수.
생성자:
‘CustomArray(int capacity)’ : 초기 용량을 설정하여 배열을 초기화 합니다.
메서드:
‘size()’ : 현재 배열에 저장된 요소의 개수를 반환합니다.
‘isEmpty()’ : 배열이 비어있는지 확인합니다.
‘get(int index)’ : 특정 인덱스의 요소를 반환합니다.
‘set(int index, int value)’ : 특정 인덱스의 요소를 설정합니다.
‘add(int value)’ : 배열의 마지막에 요소를 추가합니다.
‘remove(int index)’ : 특정 인덱스의 요소를 제거하고, 이후의 요소들을 앞으로 이동시킵니다.
‘print()’ : 배열의 모든 요소를 출력합니다.
-
📦[DS,Algorithm] 자료구조 소개
1️⃣ 자료구조(Data Structure)
자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하며, 이를 통해 데이터를 효율적으로 접근하고 수정할 수 있도록 하는 체계적인 방법입니다.
자료구조는 알고리즘의 성능을 최적화하고 프로그램의 효율성을 향상시키는 데 중요한 역할을 합니다.
기본 개념.
자료구조는 데이터를 저장하는 방식과 데이터를 조작하는 방법을 정의합니다.
이는 데이터를 어떻게 배열하고, 접근하고, 수정하고, 삭제할지를 규정하는 규칙과 방법의 집합입니다.
주요 목적.
효율적인 데이터 저장 및 접근.
데이터를 효율적으로 저장하여 빠르게 접근하고 검색할 수 있도록 합니다.
데이터 수정 및 삭제 용이.
데이터를 쉽게 수정하고 삭제할 수 있도록 합니다.
알고리즘 최적화.
알고리즘의 성능을 최적화하고 실행 시간을 단축시킵니다.
주요 종류.
배열(Array)
고정된 크기의 연속된 메모리 공간에 데이터를 저장합니다.
인덱스를 사용하여 데이터에 빠르게 접근할 수 있습니다.
연결 리스트(Linked List)
각 요소가 데이터와 다음 요소를 가리키는 포인터를 포함합니다.
동적 크기 조절이 가능하며 삽입과 삭제가 용이합니다.
스택(Stack)
후입선출(LIFO, Last In First Out) 방식으로 동작합니다.
데이터를 삽입하는 push와 삭제하는 pop 연산을 가집니다.
큐(Queue)
선입선출(FIFO, First In First Out) 방식으로 동작합니다.
데이터를 삽입하는 enqueue와 삭제하는 dequeue 연산을 가집니다.
트리(Tree)
계층적 구조를 가지며, 노드와 에지로 구성됩니다.
이진 트리, 이진 탐색 트리, AVL 트리 등 다양한 형태가 있습니다.
그래프(Graph)
노드(정점)와 에지(간선)로 구성된 자료구조로, 다양한 관계를 표현할 수 있습니다.
방향 그래프, 무방향 그래프 등이 있습니다.
해시 테이블(Hash Table)
키-값 쌍을 저장하며, 해시 함수를 사용하여 데이터에 빠르게 접근할 수 있습니다.
충돌 해결 방법으로 체이닝과 개방 주소법이 있습니다.
응용 사례.
자료구조는 데이터베이스, 운영체제, 네트워크, 인공지능, 게임 개발 등 다양한 분야에서 중요한 역할을 합니다.
적절한 자료구조의 선택은 프로그램의 성능과 효율성을 크게 향상시킬 수 있습니다.
2️⃣ 자료구조의 분류
1️⃣ 선형 자료구조(Linear Data Structure)
선형 자료구조(Linear Data Structure)는 데이터 요소들이 순차적으로 배열된 구조를 의미합니다.
이 자료구조에서는 데이터 요소들이 직선 형태로 연결되어 있으며, 각 요소는 한 다음 요소나 이전 요소와 연결되어 있습니다.
선형 자료구조의 주요 특징인 데이터 요소들이 한 줄로 배열되어 있다는 점 입니다.
주요 선형 자료구조르는 배열, 연결 리스트, 스택, 큐 등이 있습니다.
주요 선형 자료구조.
배열(Array)
정의 : 동일한 타입의 데이터 요소들이 연속된 메모리 공간에 저장되는 자료구조입니다.
특징 : 고정된 크기를 가지며 인덱스를 통해 데이터에 빠르게 접근할 수 있습니다.
예시 : 정수형 배열, 문자열 배열 등.
연결 리스트(Linked List)
정의 : 각 데이터 요소가 노드로 구성되고, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함하는 자료구조입니다.
특징 : 동적 크기 조절이 가능하며 삽입과 삭제가 용이하지만, 인덱스를 통한 접근은 배열보다 느립니다.
종류 : 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등.
스택(Stack)
정의 : 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다.
특징 : 데이터 삽입(push)과 삭제(pop)이 한쪽 끝에서만 이루어집니다.
사용 사례 : 함수 호출 스택, 역순 문자열 처리 등.
큐(Queue)
정의 : 선입선출(FIFO, First In First Out) 방식으로 동작하는 자료구조입니다.
특징 : 데이터의 삽입(enqueue)은 한쪽 끝(후단)에서, 삭제(dequeue)는 반대쪽 끝(전단)에서 이루어집니다.
종류 : 원형 큐, 우선순위 큐, 덱(Deque) 등.
사용 사례 : 운영 체제의 작업 스케줄링, 프린터 대기열 등.
선형 자료구조의 특징 및 장단점.
특징.
순차적 접근이 가능하며, 데이터를 차례대로 처리할 때 유리합니다.
메모리에서 연속적으로 배치되므로 인덱스를 통해 직접 접근할 수 있습니다.(배열의 경우)
장점.
간단하고 구현이 용이합니다.
데이터의 삽입과 삭제가 특정 조건 하에 효율적일 수 있습니다(예: 스택, 큐)
단점
데이터 크기에 따라 메모리 낭비가 발생할 수 있습니다(배열의 경우).
특정 요소 접근이나 삽입/삭제 시 성능이 저하될 수 있습니다(연결 리스트의 경우)
마무리.
선형 자료구조는 데이터가 순차적으로 연결되어 있어 순차적 처리에 적합하며, 프로그램의 다양한 부분에서 사용되는 기초적인 자료구조입니다.
2️⃣ 비선형 자료구조(Non-linear Data Structure)
비선형 자료구조(Non-linear Data Structure)는 데이터 요소들이 계층적 또는 그물 형태로 배열된 구조를 의미합니다.
이 자료구조에서는 데이터 요소들이 순차적으로 배열되지 않고, 하나의 요소가 여러 요소들과 연결될 수 있습니다.
주요 비선형 자료구조로는 트리(Tree)와 그래프(Graph)가 있습니다.
주요 비선형 자료구조.
트리(Tree)
정의 : 노드와 그 노드들을 연결하는 간선으로 구성된 계층적 자료구조입니다. 트리는 루트 노드에서 시작하여 자식 노드로 분기하며, 사이클이 없습니다.
특징 : 트리는 계층적 관계를 나타내며, 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
종류 :
이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
이진 탐색 트리(Binary Search Tree) : 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리입니다.
균형 이진 트리(Balanced Binary Tree) : AVL 트리, 레드-블랙 트리 등과 같이 높이가 균형을 이루도록 유지되는 트리입니다.
힙(Heap) : 완전 이진 트리의 일종으로, 최대 힙과 최소 힙이 있습니다.
트라이(Trie) : 문자열을 저장하고 빠르게 검색하기 위해 사용되는 트리입니다.
그래프(Graph)
정의 : 정점(Vertex)들과 이 정점들을 연결하는 간선(Edge)들로 구성된 자료구조입니다.
특징 : 그래프는 방향 그래프(Directed Graph)와 무방향 그래프(Undirceted Graph)로 나눌 수 있으며, 사이클이 존재할 수 있습니다.
종류 :
방향 그래프(Directed Graph) : 간선에 방향성이 있는 그래프입니다.
무방향 그래프(Undirected Graph) : 간선에 방향성이 없는 그래프입니다.
가중치 그래프(Weighted Graph) : 간선에 가중치가 부여된 그래프입니다.
비가중치 그래프(Unweighted Graph) : 간선에 가중치가 없는 그래프입니다.
비선형 자료구조의 특징 및 장단점.
특징 :
계층적 또는 네트워크 구조를 나태내는 데 적합합니다.
복잡한 관계를 표현할 수 있으며, 데이터 요소 간의 다대다 관계를 처리할 수 있습니다.
장점 :
데이터의 계층적 구조를 쉽게 표현할 수 있습니다(트리).
복잡한 연결 관계를 효과적으로 모델링할 수 있습니다(그래프).
특정 유형의 탐색, 정렬, 데이터 압축, 네트워크 라우팅 등에 유용합니다.
단점 :
구현과 관리가 선형 자료구조보다 복잡할 수 있습니다.
특정 작업(예: 트리의 균형 유지, 그래프 탐색 등)에서 추가적인 알고리즘이 필요합니다.
마무리.
비선형 자료구조는 데이터가 단순히 순차적으로 배열되지 않고, 복잡한 관계를 나타내는 경우에 사용됩니다.
예를 들어, 파일 시스템의 디렉터리 구조, 데이터베이스 인덱스, 소셜 네트워크의 사용자 관계 등이 비선형 자료구조를 활용하는 사례입니다.
2️⃣ 자료구조의 구현.
1️⃣ 추상 자료형(Abstract Data Type, ADT)
자바 프로그래밍에서의 추상 자료형(Abstract Data Type, ADT)은 데이터의 논리적 구조와 이를 조작하는 연산들을 명확하게 정의한 개념입니다.
ADT는 구현 세부 사항을 숨기고, 데이터와 연산의 인터페이스를 통해 사용자에게 추상적인 수준에서 데이터 조작을 제공합니다.
즉, ADT는 데이터가 어떻게 저장되고 구현되는지에 대한 정보는 감추고, 데이터와 상호작용하는 방법만을 정의합니다.
주요 개념
추상화(Abstraction)
ADT는 데이터를 추상화하여 데이터의 실제 구현과 독립적으로 사용될 수 있도록 합니다.
사용자는 데이터의 저장 방식이나 연산의 구현 방법을 알 필요 없이, ADT가 제공하는 인터페이스를 통해 데이터를 조작할 수 있습니다.
인터페이스(Interface)
ADT는 데이터 타입과 이를 다루는 연산들을 인터페이스를 통해 정의합니다.
자바에서는 인터페이스(Interface) 키워드를 사용하여 ADT의 연산을 정의할 수 있습니다.
캡슐화(Encapsulation)
ADT는 데이터와 연산을 하나의 단위로 묶어 캡슐화합니다.
데이터를 직접 접근하지 않고, 정의된 연산을 통해서만 접근할 수 있도록 하여 데이터 무결성을 보장합니다.
자바에서의 ADT 예시
다음은 자바에서 스택(Stack) ADT를 정의하고 구현하는 예시입니다.
스택 인터페이스 정의
public interface Stack<T> {
void push(T item); // 스택에 아이템을 추가
T pop(); // 스택에서 아이템을 제거하고 반환
T peek(); // 스택의 맨 위 아이템을 반환(제거하지 않음)
boolean isEmpty(); // 스택이 비어 있는지 확인
int size(); // 스택의 크기 반환
}
스택 구현
import java.util.ArrayList;
import java.util.List;
public class ArrayListStack<T> implements Stack<T> {
private List<T> list = new ArrayList<>();
@Override
public void push(T item) {
list.add(item);
}
@Override
public T pop() {
if (isEmpty()) {
throw new RuntimException("Stack is empty");
}
return list.remove(list.size() - 1);
}
@Override
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return list.get(list.size() - 1);
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public int size() {
return list.size();
}
}
설명
‘Stack<T>‘ 인터페이스는 스택 ADT의 연산을 정의합니다. 이 인터페이스는 ‘push’, ‘pop’, ‘peek’, ‘isEmpty’, ‘size’ 메서드를 포함합니다.
‘ArrayListStack<T>‘ 클래스는 ‘Stack<T>‘ 인터페이스를 구현합니다. 이 클래스는 ‘ArrayList’ 를 내부 데이터 구조로 사용하여 스택 연산을 구현합니다.
‘push’ 메서드는 스택에 아이템을 추가합니다.
‘pop’ 메서드는 스택에서 맨 위의 아이템을 제거하고 반환합니다.
‘peek’ 메서드는 스택의 맨 위 아이템을 제거하지 않고 반환합니다.
‘isEmpty’ 메서드는 스택이 비어 있는지 확인합니다.
‘size’ 메서드는 스택의 크기를 반환합니다.
이 예시에서 ‘Stack<T>‘ 인터페이스는 스택 ADT를 정의하고, ‘ArrayListStack<T>‘ 클래스는 이 ADT를 구현한 것입니다.
사용자는 ‘ArrayListStack’ 의 내부 구현을 알 필요 없이 ‘Stack’ 인터페이스를 통해 스택 연산을 사용할 수 있습니다.
이는 ADT의 주요 장점 중 하나인 구현의 독립성을 잘 보여줍니다.
-
[AnD] 두 수의 합.
문제 설명 🤓
0 이상의 두 정수가 문자열 a, b로 주어질 때, a + b의 값을 문자열로 return 하는 solution 함수를 작성해 주세요.
솔루션 📝
import java.math.BigInteger;
class Solution {
public String solution(String a, String b) {
String answer = "";
BigInteger bigNumberA = new BigInteger(a);
BigInteger bigNumberB = new BigInteger(b);
answer = bigNumberA.add(bigNumberB).toString();
return answer;
}
}
트러블슈팅 🏀
1. NumberFormatException 에러(1).
입출력의 예시 중 가장 긴 입력 예시인 a : “18446744073709551615”, b : “305793246910280479981” 에서 에러가 발생 했습니다.
1️⃣ 콘솔에 나타난 에러 메시지
콘솔에 나타난 에러 메시지는 아래와 같았습니다.
Exception in thread "main" java.lang.NumberFormatException: For input string: "18446744073709551615"
at java.base/java.lang.NumberFormatException.forInputString(NumberFormatException.java:67)
at java.base/java.lang.Integer.parseInt(Integer.java:662)
at java.base/java.lang.Integer.valueOf(Integer.java:989)
at programmers.test1.Solution.solution(Solution.java:8)
at programmers.test1.SolutionMain.main(SolutionMain.java:7)
Process finished with exit code 1
2️⃣ 본격적인 트러블슈팅
이 메시지를 하나씩 해석하고 트러블슈팅을 이어갔습니다.
먼저 이 오류 메시지는 NumberFormatException 이 발생했다는 것을 나타냅니다.
특히 “For input string: “18446744073709551615”는 Java에서 정수로 변환하려는 문자열이 정부 범위를 벗어났음을 의미합니다.
Java의 Integer.parseInt() 메소드는 문자열을 정수(Int)로 변환할 때 사용됩니다.
그러나 Int 자료형은 -2,147,483,648,648 부터 2,147,483,648,647까지의 값을 저정할 수 있습니다.
제공된 문자열 “18446744073709551615”는 이 범위를 훨씬 초과합니다.
3️⃣ 해결 방법
이 문제를 해결하려면 다음과 같은 방법을 고려할 수 있습니다.
1. 타입 변경
int 대신 long 타입을 사용하거나, 이보다 더 큰 범위가 필요하다면, BigInteger 클래스를 사용할 수 있습니다.
long 의 범위는 -9,223,372,036,854,775,808부터 9,223,372,036,854,775,807 까지입니다.
2. 입력 검증
입력 값이 정수 타입으로 변환 가능한지, 그리고 해당 타입의 범위 내에 있는지 검증하는 로직을 추가합니다.
코드를 수정할 때는 적절한 데이터 타입을 사용하도록 주의해야 합니다.
예를 들어, long 으로 변경하려면 Long.parseLong() 을 사용할 수 있습니다.
2. NumberFormatException 에러(2)
이번에는 위의 트러블슈팅을 활용하여 코드를 만든 결과 NumberFormatException 에러를 다시 발생 시킨 케이스 입니다.
이번에는 Long.parseLong() 메소드를 사용하면서 발생했습니다.
문자열 “18446744073709551615”는 이번에도 범위를 벗어난 값으로 처리되었습니다.
long 자료형의 최대값은 9,223,372,036,854,775,807dlqslek.
제공된 값 “18446744073709551615”는 이 최대값을 초과합니다.
따라서, long 으로도 처리할 수 없으며, Java에서 이러한 큰 숫자를 다루려면 BigInteger 클래스를 사용해야 합니다.
BigInteger 는 사실상 제한 없는 정밀도의 정수를 다룰 수 있어 이와 같은 큰 숫자를 취급할 때 유용합니다.
BigInteger를 사용하는 예시 코드.
import java.math.BigInteger;
public class Solution {
public void solution(String input) {
BigInteger bigNumber = new BigInteger(input);
// bigNumber를 사용한 다른 로직
}
}
public class SolutionMain {
public static void main(String[] args) {
new Solution().solution("18446744073709551615");
}
}
이 코드는 BigInteger 를 사용하여 입력된 숫자를 처리하고, 필요한 로직을 수행할 수 있도록 구성되어 있습니다.
3. BigInteger 클래스를 사용하여 두 큰 정수를 더하는 방법.
두 문자열을 받아 큰 범위의 문자열을 BigInteger 클래스를 사용하여 받아오고 변환하는 데 까지는 성공하였으나 입력된 두 개의 큰 범위 값의 BigInteger 를 어떻게 합쳐야 할지를 몰라 검색해 봤습니다.
1️⃣ Java에서 BigInteger 클래스를 사용하여 두 큰 정수를 더하는 방법
BigInteger 클래스는 불변(immutable) 객체 이므로 두 BigInteger 인스턴스를 더할 때, 새로운 BigInteger 객체가 반환됩니다.
2️⃣ BigInteger 객체를 더하는 방법 예시 코드
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
// 두 큰 수를 BigInteger로 생성
BigInteger number1 = new BigInteger("12345678901234567890");
BigInteger number2 = new BigInteger("98765432109876543210");
// 두 수를 더함
BigInteger sum = number1.add(number2);
// 결과 출력
System.out.println("Sum: " + sum.toSting())
}
}
이 코드는 다음과 같은 단계를 거칩니다.
1. 두 개의 BigInteger 인스턴스 number1 과 number2 를 생성합니다.
이들은 문자열로부터 생성되며, 매우 큰 수를 나타낼 수 있습니다.
2. add 메소드를 사용하여 number1 과 number2 를 더합니다.
이 메소드는 두 수의 합을 나타내는 새로운 BigInteger 객체를 반환합니다.
3. 덧셈 결과를 출력합니다.
BigInteger 를 사용하면 정수의 범위에 제한 없이 수학적 연산을 수행할 수 있어, 매우 큰 수를 처리해야 할 때 유용합니다.
Touch background to close
devkobe24.com
