📦[DS,Algorithm] Circular Queue(원형 큐)를 배열로 구현시 rear를 -1으로 설정하지 않는 이유.

Backend · 2024-06-13

📦[DS,Algorithm] 알고리즘(Algorithm)

1️⃣ 알고리즘(Algorithm). 알고리즘(Algorithm)은 주어진 문제를 해결하기 위해 일련의 명확한 단계로 구성된 절차나 방법을 의미합니다. 쉽게 말해, 알고리즘은 문제 해결을 위한 일련의 규칙 또는 지침입니다. 1️⃣ 알고리즘(Algorithm)의 정의. 알고리즘은 다음과 같은 요소를 갖춘 절차를 말합니다. 입력(Input) : 알고리즘이 처리할 하나 이상의 값이 주어집니다. 출력(Output) : 알고리즘의 수행 결과로 하나 이상의 값이 생성됩니다. 명확성(Definiteness) : 각 단계는 명확하게 정의되어 있어야 합니다. 모호한 부분 없이 명확한 지침이어야 합니다. 유한성(Finiteness) : 알고리즘은 유한한 단계 내에서 종료되어야 합니다. 즉, 알고리즘은 무한히 실행되지 않고, 한정된 단계 내에서 끝나야 합니다. 유효성(Effectiveness) : 알고리즘의 모든 단계는 실제로 수행 가능해야 하며, 사람이 직접 수행할 수 있을 정도로 기본적인 연산으로 구성되어 있어야 합니다. 2️⃣ 알고리즘의 특성 알고리즘은 다음과 같은 특성을 가질 수 있습니다. 정확성(Correctness) : 알고리즘은 올바른 결과를 생성해야 합니다. 시간 복잡도(Time Complexity) : 알고리즘이 문제를 해결하는 데 걸리는 시간입니다. 일반적으로 크기에 대한 함수로 표현됩니다. 공간 복잡도(Space Complexity) : 알고리즘이 문제를 해결하는 데 사용하는 메모리 양입니다. 이 또한 입력 크기에 대한 함수로 표현됩니다. 효율성(Efficiency) : 알고리즘이 주어진 자원을 얼마나 효율적으로 사용하는지 나타냅니다. 여기에서는 시간 복잡도와 공간 복잡도가 포함됩니다. 확장성(Scalability) : 알고리즘이 입력 크기에 따라 얼마나 잘 동작하는지 나타냅니다. 확장성 있는 알고리즘은 큰 입력 크기에서도 효율적으로 작동합니다. 3️⃣ 알고리즘의 중요성. 알고리즘(Algorithm)은 컴퓨터 과학 및 프로그래밍에서 핵심적인 역할을 합니다. 효율적인 알고리즘을 사용하면 컴퓨터 프로그램이 더 빠르고 적은 자원을 사용하여 문제를 해결할 수 있습니다. 또한 알고리즘은 문제 해결의 논리적이고 체계적인 접근 방식을 제공하여 복잡한 문제를 단순화하고 해결하는 데 도움을 줍니다. 알고리즘을 잘 이해하고 사용하는 것은 프로그래머와 컴퓨터 과학자에게 필수적인 기술입니다. 이를 통해 다양한 문제를 효율적으로 해결하고, 더 나은 소프트웨어와 시스템을 설계할 수 있습니다.

Backend · 2024-06-13

📦[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’ 메서드를 정의합니다. 이 메서드는 현재 큐의 크기와 시작 인덱스를 사용하여 중간 인덱스를 계산한 후 해당 인덱스의 요소를 반환합니다.

Backend · 2024-06-12

📦[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’ 의 위치는 동적입니다.

Backend · 2024-06-10

📦[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’ 포인터가 배열의 끝에 도달했을 때, 다시 배열의 시작 부분으로 돌아가기 위해 사용됩니다. 이를 통해 배열의 고정된 크기를 효율적으로 활용하며, 원형 큐의 특성을 유지할 수 있습니다.

Backend · 2024-06-09

📦[DS,Algorithm] LinkedList를 사용한 Deque.

Backend · 2024-06-07

📦[DS,Algorithm] ArrayDeque

Backend · 2024-06-06

📦[DS,Algorithm] Deque(데크, 덱)

Backend · 2024-06-05

📦[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)의 시간이 소요됩니다. 연속된 메모리 할당 필요 : 큰 배열을 사용할 떄는 연속된 메모리 공간이 필요하여 메모리 할당에 제한이 있을 수 있습니다. 배열은 이러한 특성들로 인해 빠른 접근이 필요한 상황에서는 매우 유용하지만, 삽입 및 삭제가 빈번히 일어나는 경우에는 비효율적일 수 있습니다. 따라서 상황에 맞게 적절한 자료구조를 선택하는 것이 중요합니다.

Backend · 2024-06-02

📦[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의 장.단점” 기존 배열 사용 : 메모리를 절약할 수 있지만, 배열의 마지막 요소는 기본값으로 설정해야 합니다.

Backend · 2024-06-01

📦[DS,Algorithm] 큐(Queue)

Backend · 2024-05-30

📦[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() : 스택에 현재 저장된 데이터의 개수를 반환합니다.

Backend · 2024-05-28

📦[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) 방식이 있습니다.

Backend · 2024-05-27

📦[DS,Algorithm] 노드(Node)

1️⃣ Node(노드). Node(노드) 는 연결 리스트, 트리, 그래프 등의 자료구조에서 기본적인 단위 요소를 의미합니다. 노드는 데이터를 저장하며, 다른 노드와의 연결을 나타내는 포인터(참조)를 포함합니다. 1️⃣ Node의 구성 요소. 데이터(Data) : 노드가 저장하는 실제 값입니다. 이는 숫자, 문자, 객체 등 모든 데이터 타입이 될 수 있습니다. 포인터(참조, Pointer) : 다음 노드(또는 다른 관련된 노드)를 가리지는 참조입니다. 포인터의 수와 종류는 자료구조에 따라 다릅니다. Singly Linked List : 하나의 다음 노드를 가리키는 포인터를 가집니다. Doubly Linked List : 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가집니다. 트리(Tree) : 부모 노드, 자식 노드 등 여러 방향의 포인터를 가질 수 있습니다. 그래프(Graph) : 여러 개의 인접 노드를 가리키는 포인터를 가질 수 있습니다. Singly Linked List의 Node Singly Linked List에서의 노드는 다음과 같은 구조를 가집니다. public class Node { int data; // 노드가 저장하는 데이터 Node next; // 다음 노드를 가리키는 포인터 public Node(int data) { this.data = data; this.next = null; } } Doubly Linked List의 Node Doubly Linked List에서의 노드는 다음과 같은 구조를 가집니다. public class DoublyNode { int data; // 노드가 저장하는 데이터 DoublyNode next; // 다음 노드를 가리키는 포인터 DoublyNode prev; // 이전 노드를 가리키는 포인터 public DoublyNode(int data) { this.data = data; this.next = null; this.prev = null; } } 2️⃣ Node를 사용하는 예제. Singly Linked List Singly Linked List는 각 노드가 다음 노드를 가리키는 구조로 연결된 리스트 입니다. 아래는 Singly Linked List를 구현한 예제입니다. //SinglyLinkedList public class SinglyLinkedList { private Node head; public SinglyLinkedList() { this.head = null; } // 리스트의 맨 앞에 노드 추가 public void addFirst(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } // 리스트의 맨 끝에 노드 추가 public void addLast(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; } // 리스트의 특정 값 삭제 public void delete(int data) { if (head == null) { return; } if (head.data == data) { head = head.next; return; } Node current = head; while (current.next != null && current.next.data != data) { current = current.next; } if (current.next != null) { current.next = current.next.next; } } // 리스트 출력 public void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } } // Main public class Main { public static void main(String[] args) { // Singly Linked List 생성 SinglyLinkedList singlyLinkedList = new SinglyLinkedList(); singlyLinkedList.addFirst(1); singlyLinkedList.addLast(2); singlyLinkedList.addLast(3); singlyLinkedList.printList(); // 1 2 3 singlyLinkedList.delete(2); singlyLinkedList.printList(); // 1 3 } }

Backend · 2024-05-27

📦[DS,Algorithm] 완전 이진 트리(Complete Binary Tree)

Backend · 2024-05-27

📦[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 } }

Backend · 2024-05-27

📦[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 */

Backend · 2024-05-25

📦[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(); } }

Backend · 2024-05-24

📦[DS,Algorithm] 원형 큐(Circular Queue)

1️⃣ 원형 큐(Circular Queue). 원형 큐(Circular Queue)란, “고정된 크기의 배열” 을 사용하여 구현된 큐로서, 배열의 끝에 도달하면 다시 배열의 시작 부분으로 돌아가는 구조를 가진 큐입니다. 이를 통해 큐가 꽉 차 있는지, 비어 있는지를 효율적으로 관리할 수 있으며, 공간을 효율적으로 사용할 수 있습니다. 1️⃣ 원형 큐의 특징. 선입선출(FIFO, First In First Out) : 일반적인 큐와 마찬가지로 먼저 들어간 데이터가 먼저 나오는 구조입니다. 순환 구조 : 배열의 끝에 도달하면 다시 처음으로 돌아갑니다. 이를 통해 고정된 크기의 배열을 이용하여 메모리를 효율적으로 사용합니다. 3 고정 크기 : 큐의 최대 크기는 배열의 크기로 제한 됩니다. 2️⃣ 원형 큐의 주요 연산. Enqueue : 큐의 뒤쪽(rear)에 새로운 요소를 추가합니다. Dequeue : 큐의 앞쪽(front)에서 요소를 제거하고 반환합니다. Peek : 큐의 앞쪽(front) 요소를 제거하지 않고 반환합니다. IsEmpty : 큐가 비어 있는지 여부를 확인합니다. IsFull : 큐가 가득 찼는지 여부를 확인합니다. 3️⃣ 원형 큐의 장점. 메모리 효율성 : 고정된 크기의 배열을 사용하여 메모리를 효율적으로 사용합니다. 연속된 메모리 사용 : 배열을 사용하여 메모리를 연속적으로 사용하므로 캐시 효율성이 높습니다. 4️⃣ 원형 큐의 단점. 고정 크기 제한 : 크기가 고정되어 있으므로, 큐가 가득 찬 경우 더 이상 요소를 추가할 수 없습니다. 이 문제를 해결하려면 동적으로 크기를 조절할 수 있는 방법을 추가로 구현해야 합니다. 5️⃣ 원형 큐의 구현 예제 // CircularQueue 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 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 boolean isEmpty() { return size == 0; } // 큐가 가득 찼는지 확인 public boolean isFull() { return size == capacity; } // 큐의 크기 반환 public int getSize() { return size; } } // Main public class Main { public static void main(String[] args) { CircularQueue circularQueue = new CircularQueue(5); circularQueue.enqueue(1); circularQueue.enqueue(2); circularQueue.enqueue(3); circularQueue.enqueue(4); circularQueue.enqueue(5); System.out.println("Dequeue: " + circularQueue.dequeue()); System.out.println("Dequeue: " + circularQueue.dequeue()); circularQueue.enqueue(6); circularQueue.enqueue(7); System.out.println("Peek: " + circularQueue.peek()); while (!circularQueue.isEmpty()) { System.out.println("Dequeue: " + circularQueue.dequeue()); } } } // 출력 /* Dequeue: 1 Dequeue: 2 Peek: 3 Dequeue: 3 Dequeue: 4 Dequeue: 5 Dequeue: 6 Dequeue: 7 */ 코드 설명. CircularQueue 클래스: ‘queue’ : 큐를 저장하는 배열. ‘front’ : 큐의 앞쪽 인덱스. ‘rear’ : 큐의 뒤쪽 인덱스. ‘size’ : 현재 큐에 저장된 요소의 개수. ‘capacity’ : 큐의 최대 크기. 메서드: ‘enqueue(int element)’ : 큐가 가득 차지 않았으면 요소를 큐에 추가합니다. ‘dequeue()’ : 큐가 비어 있지 않으면 큐의 앞쪽 요소를 제거하고 반환합니다. ‘peek()’ : 큐의 앞쪽 요소를 제거하지 않고 반환합니다. ‘isEmpty()’ : 큐가 비어 있는지 확인합니다. ‘isFull()’ : 큐가 가득 찼는지 확인합니다. ‘getSize()’ : 큐의 현재 크기를 반환합니다. main 메서드: 원형 큐를 생성하고 여러 연산을 수행하여 큐의 동작을 테스트합니다.

Backend · 2024-05-23

📦[DS,Algorithm] 큐(Queue)

Backend · 2024-05-23

📦[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()’ : 배열의 모든 요소를 출력합니다.

Backend · 2024-05-21

📦[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의 주요 장점 중 하나인 구현의 독립성을 잘 보여줍니다.

Backend · 2024-05-21

[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 를 사용하면 정수의 범위에 제한 없이 수학적 연산을 수행할 수 있어, 매우 큰 수를 처리해야 할 때 유용합니다.

Backend · 2024-05-01

devkobe24.com

Contact

AnD