자료구조 큐, 스택, 덱 (Queue, Stack, Deque)
Queue, Stack, Deque(=Double-ended Queue) 큐, 스택, 덱은 배열, 리스트와 함께 선형 자료구조에 속하는 자료구조들이다. 사실 큐, 스택, 덱의 모든 기능은 리스트(이하 '리스트'라는 단어는 모두 Linked List를 뜻함)만 사용해서도 시간복잡도 마저 동일하게 동작할 수 있다. 즉, 어찌보면 스택, 큐, 덱은 리스트에 포함되는 자료구조라고 볼 수 있다. 그럼에도 큐, 스택, 덱은 분명 리스트와는 별개의 자료구조로 정의되어 사용되고 있다. 이건 일종의 컨셉, 규칙에 해당한다고 생각한다. 술먹고 있는데 상대방이 갑자기 병따개를 준다. 병따달라는 의도를 바로 파악할 수 있다. 술먹다가 이번엔 상대방이 멀티툴을 갑자기 준다. 물론 멀티툴엔 병따개가 있다. 하지만 난 멀티툴을 받..
2021. 10. 11.
백준 15779 자바 - ZigZag (BOJ 15779 JAVA)
https://www.acmicpc.net/problem/15779 i번째 데이터에 대해, i-2, i-1, i 번째 데이터를 살펴보며 단조증가 수열이거나 단조감소 수열일 경우 arr[i] = 0을 기입했고, 지그재그 수열일 경우 1을 기입함.(13line) 그럼 예를들어서 문제에 제시된 2번째 예시 (1,3,4,2,5)의 경우 제가 짠 로직으로는 arr = [0, 0, 0, 1, 1] 와 같이 기입됨. 근데 이 때 1이 연속된 갯수가 결국 지그재그 수열의 길이이므로, 13line처럼 이전값+1을 해주면 연속된 길이도 한꺼번에 구할 수 있음. 최종적으로 arr 배열에 있는 가장 큰 수가 가장 긴 지그재그 수열의 길이이므로 max값을 찾아주고 (19line) 거기에 2를 더해준게 답임. (+2를 해준 것은..
2021. 10. 8.
백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA)
https://www.acmicpc.net/problem/15993 f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면, f(n) = f(n-1) + f(n-2) + f(n-3) 이다. 왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 + f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다. 위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다. 그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자. a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀..
2021. 10. 7.