분류 전체보기
-
[자료구조] Deque란? from Java자료구조 2024. 4. 27. 15:37
Deque란?- Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 넣고 뺄 수 있는 형태의 자료구조를 의미한다- 다시 말해 기존의 Queue는 한쪽에서 데이터를 넣고 다른 한쪽에서 데이터를 빼는 형태인데 Deque는 둘다 데이터를 넣고 뺄 수 있다는 것이다- Queue와 Stack 을 합쳐 놓은 자료구조라고 생각 하면 된다 - Deque를 이해하려면 일단 Queue를 알아야 한다 - 아래는 Queue를 정리한 포스팅이다 https://hyeonni.tistory.com/24 Queue란? from javaQueue 란? Queue란? 사전적 의미로는 대기줄이다이러한 사전 적 의미 처럼 queue는 차례대로 처리된다큐는 후입선출(LIFO)인 스택과 다르게 선입선출(FIFO)의 형태를..
-
[백준] 1158 요세푸스 문제 - Java알고리즘 문제 풀이 2024. 4. 27. 02:48
문제 - 요세푸스 문제https://www.acmicpc.net/problem/1158 문제 설명 입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력예제와 같이 요세푸스 순열을 출력한다. 예제 입력7 3 예제 출력 접근 방법 - 문제를 보면 숫자를 차례대로 탐색하고 K 번째 숫자를 제거하고 그런식으로 처리를 한다 - 여기에서 생각 해볼 자료구조가 링크드리스트나 큐를 생각했다- 큐를 생각한 이유는 차례대로 탐색을 하면서 K번째 이전의 값들은 다시 빼고 다시 넣는 형태가 맞는 것 같아서 생각을 했다 그리고 숫자를 차례대로 탐색하는 형식이라 선입선출 형식과 맞는 것 같다 코드 작성import java.io.BufferedReader;import ja..
-
[자료구조] Queue란? from java자료구조 2024. 4. 27. 00:40
Queue 란? Queue란? 사전적 의미로는 대기줄이다이러한 사전 적 의미 처럼 queue는 차례대로 처리된다큐는 후입선출(LIFO)인 스택과 다르게 선입선출(FIFO)의 형태를 가진다선입선출 말 그대로 먼저 들어오면 먼저 나가는 구조이다 특징- FIFO (First In First Out) 구조 - 큐의 한 쪽 끝은 front (앞)로 정하여 삭제 연산만 수행- 다른 한 쪽 끝은 rear 로 정하여 삽입 연산만 수행- 예를 들어 빨대 형태이다 한쪽으로 들어오고 다른 한쪽으로 나간다 사용법, 예제import java.util.Queue;import java.util.LinkedList;Queue queue = new LinkedList(); // T 타입 queue 선언- 일단 java.util.Q..
-
[백준] 10845 큐 -Java알고리즘 문제 풀이 2024. 4. 25. 15:39
문제 - 큐https://www.acmicpc.net/problem/10845 10845번: 큐첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지www.acmicpc.net 문제 설명 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다. 예제 입력15push 1push 2fron..
-
[백준] 1966 프린터 큐 - Java알고리즘 문제 풀이 2024. 4. 25. 01:16
문제 - 프린터 큐https://www.acmicpc.net/problem/1966 1966번: 프린터 큐여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에www.acmicpc.net 문제 설명 입력첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M 출력각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다. 예제 입력31 054 21 2 3 46..
-
[백준] 2161 카드1 - Java알고리즘 문제 풀이 2024. 4. 24. 01:25
문제 - 카드1 https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 설명 입력 첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다. 출력 첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다. 예제 입력 7 예제 출력 1 3 5 7 4 2 6 접근 방법 - 문제를 보면 1번 부터 N 까지의 카드를 차례대로 한장을 버리고 그 다음 한장을 다시 아래에 넣는다 이런식으로 반복을 하는데 괜찮은 자료구조..
-
[알고리즘] 이분 탐색 / 이진 탐색 Java알고리즘 2024. 4. 22. 19:22
이분 탐색 / 이진 탐색 - 데이터가 정렬돼 있는 상태에서 값을 찾아내는 알고리즘 이다- 데이터의 중앙값과 찾고 하는 값을 비교해서 데이터의 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다- 데이터가 정렬되어 있어야만 사용할 수 있다 기능특징 시간 복잡도타깃 데이터 탐색중앙값 비교를 통한 대상 탐색 축소 방식O(logN) 탐색 과정1) 현재 데이터셋의 중앙값을 선택한다 2) 중앙값 > 타깃 데이터 일때 중앙값 기준으로 왼쪽 데이터셋을 선택한다3) 중앙값 4) 과정 1~3 을 반복하여 중앙값 == 타깃 데이터일때 탐색을 종료한다 Java로 하는 이분 탐색 구현 1. 반복문 구현public boolean searchBinary (int[] array, int n) { int left = 0; in..
-
[백준] 2470 두 용액 - Java알고리즘 문제 풀이 2024. 4. 22. 16:53
문제 - 두 용액 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 설명 입력 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력..