전체 글376 [자료구조] 덱 (Deque) 목차 덱(Deque)의 개념 덱 (Deque)은 Double-ended queue를 줄인 것으로, 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산을 모두 지원한다. 즉, 앞쪽 front와 뒤쪽 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 따라서 스택과 큐의 특성을 모두 갖는 자료구조이다. 덱이 수용할 수 있는 데이터의 크기를 넘어가는 삽입 연산을 수행할 때는 오버플로우가 (Overflow) 발생한다. 그리고 비어 있는 덱에서 삭제 연산을 수행하면 언더플로우 (Underflow)가 발생한다. 덱의 핵심 기능은 앞으로 데이터 삽입, 앞으로 데이터 제거, 뒤로 데이터 삽입, 뒤로 데이터 제거이다. 밑에서 덱의 메서드들과 사용법을 알아보겠다. 덱 (Deque) 기능 & 사용법 덱 (Deque.. 2022. 3. 17. [자료구조] 큐(Queue) 목차 큐(Queue)의 개념 큐는 FIFO 선입선출(First In First Out)의 구조를 가진다. 즉, 큐에서는 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. 한 예는 은행에 번호표가 있다. 은행에서 번호표를 먼저 뽑은 사람이 서비스를 먼저 받는다. 이러한 은행의 번호표의 체계가 큐(Queue)이다. 큐는 추가로 그래프의 넓이 우선 탐색(BFS)에서 사용된다. Enqueue : 큐 맨 뒤에 데이터 추가 Dequeue : 큐 맨 앞쪽의 데이터 삭제 위의 그림에 나온 것처럼 큐는 앞뒤가 다른 역할을 수행한다. 큐의 앞부분은 front는 삭제 연산만 수행하고 큐의 뒷부분은 rear는 삽입 연산만 수행한다. 보통 컴퓨터 버퍼에서 주로 사용되고, 여러 개가 한꺼번에 입력이 들어올 때 대기열을 만들어 순.. 2022. 3. 15. [자료구조] 스택(Stack) 목차 스택(Stack)의 개념 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out), 즉 후입 선출 형식의 자료 구조이다. 따라서 스택에서는 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조를 가지고 있다. 스택은 완전히 꽉 찼을 때 Overflow 상태라고 하며 완전히 비어 있으면 Underflow 상태라고 한다. 스택(Stack)의 연산 스택은 LIFO(Last In First Out)를 따른다. 즉, 가장 최근에 스택에 추가한 데이터가 가장 먼저 제거된다. pop(): 스택에서 가장 위에 있는 항목을 제거한다. push(data): data 하나를 스택의 가장 윗부분에 추가한다. peek(): 스택의 가장 위에 있는 항목을 반환한다. isEmpty(): 스택.. 2022. 2. 28. [백준] 9084번 : 동전 – JAVA [자바] https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 문제 풀이 백준 9084번은 골드 5 난이도의 DP (다이나믹 프로그래밍) 문제다. 특히 이 문제는 전에 올렸던 백준 2293번 동전 1과 거의 똑같으니 밑에 링크를 참고해도 좋겠다. https://propercoding.tistory.com/entry/백준-2293번-영역-구하기-–-JAVA-자바 [백준] 2293번 : 동전 1 – JAVA [자바] https://www.a.. 2022. 2. 17. [백준] 1697번 : 숨바꼭질 – JAVA [자바] https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 문제 풀이 백준 1697번 숨바꼭질은 그래프, 그중에서도 BFS를 써서 푸는 난이도 실버 1의 문제이다. 왜 BFS를 쓰냐면 BFS는 Queue를 이용해서 count를 구하기 쉽지만 DFS는 재귀 함수로 구현되기 때문에 카운트를 구하기가 쉽지가 않다. 이 문제에서는 수빈이의 위치 n, 그리고 동생의 위치 k가 주어진다. 그리고 수빈이의 위치가 X이면 1초 후에 X-.. 2022. 2. 11. [백준] 9465번 : 스티커 – JAVA [자바] https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 문제 풀이 백준 9465 스티커는 2차원 배열을 이용한 DP (다이나믹 프로그래밍) 문제이다. 난이도는 실버 1로 측정되어 있다. DP 이론이 아직 부족한 사람은 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming [알고리즘] 다이나믹 프로그래밍 (Dynamic P.. 2022. 2. 11. [백준] 2293번 : 동전 1 – JAVA [자바] https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 문제 풀이 백준 2293번은 골드 5 난이도의 DP (다이내믹 프로그래밍) 문제다. 만약에 DP 이론을 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/알고리즘-다이내믹-프로그래밍-Dynamic-Programming [알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 목차 다이나믹 프로그래밍이란? 다이.. 2022. 2. 5. [백준] 2583번 : 영역 구하기 – JAVA [자바] https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 풀이 방법 이 문제는 전형적인 영역의 개수를 구하는 그래프 문제이다. 이런 문제 유형이 많으므로 조금만 풀면 이 유형의 그래프 문제는 쉽게 풀 수 있을 것이다. 조금 더 많은 그래프의 정보를 원한다면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/entry/자료구조-그래프 Graph [자료구조] 그래프(Graph) 목차 그래.. 2022. 2. 4. 이전 1 ··· 43 44 45 46 47 다음 반응형
