본문 바로가기

Deque9

[세미나] queue, stack, deque (기초 자료구조 및 알고리즘 4회차) 세미나 진행한 pdf 입니다. 큐, 스택, 덱(데크)에 대해다룹니다. 이후에 영상이나 음성이 필요하다고 생각되는 회차가 있으면 그것도 공유할 예정입니다. ppt의 우측 상단 '새 탭에서 보기' 를 누르시면 크게보거나 pdf를 다운받아 보실 수 있습니다. 2024. 1. 8.
[자바] 백준 11003 - 최솟값 찾기 (java) 목차 문제 : boj11003 필요 알고리즘 그리디 그리디 개념으로 풀 수 있는 문제이다. 덱, 우선순위 큐 생각한 그리디 로직을 구현하기 위해 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 우선순위 큐를 사용한 풀이부터 얘기해보자 (코드2) 코드만 봐도 어떤 느낌인지 알 것 같다. 순서대로 입력값을 넣을 때, 입력값과 위치도 같이 넣는다. 그리고 우선순위 큐에서 최솟값을 꺼낼껀데, 이게 위치가 현재 보고 있.. 2023. 3. 9.
[자바] 백준 3190 - 뱀 (java) 문제 : boj3190 필요 알고리즘 개념 시뮬레이션 문제에서 제시된대로 실제 뱀을 움직여보면서 언제 끝나는지 시뮬레이션을 돌려보면 된다. 덱 (deque) 등의 자료구조 뱀의 머리부분이 움직이고, 꼬리부분이 사라지는 부분을 시뮬레이션으로 구현하기 위해 내가 생각한 가장 적합한 자료구조는 덱을 사용하는 것인데, 구현만 가능하다면 어떤 자료구조를 써도 당연히 상관없다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이하 풀이는.. 2023. 2. 1.
[자바] 프로그래머스 - 행렬과 연산 (Lv4, Java) 문제 : Programmers-행렬과 연산 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 Linked List, Deque 이 문제에서는 양방향에서의 삽입, 값 획득이 O(1)로 이루어질 수 있는 자료구조를 사용해야 한다. 따라서 Linked List 혹은 Deque에 대한 개념을 알고 있어야 풀 수 있다. 내 코드에서는 둘 다 사용하지만, 둘 중 하나로만 진행해도 동일한 결과를 얻을 수 있다. rc가 r*c 크기의 배열이라고 할 경우, 이 문제의 경우 그냥 배열 자체만 보고 진행을 하게 되면 shiftRow는 배열의 모든 원소를 건드려야 하므로 O(r*c)가 필요하고, rotate는 맨 위와 맨 아래 행, 그.. 2022. 8. 20.
[자바] 백준 1835 - 카드 (boj java) 문제 : boj1835 이걸 어찌 구해야할지 상당히 난감해보일 수 있다. 그럼 반대로 이미 출력의 답을 알고 있다고 할 때, 이 문제에서 제시된 방법대로 진행할 경우 정말 1,2,3,... 이 순서대로 뜰지 확인해볼 수 있을까? 물론 문제에서 제시된대로 코드를 구현만 하면 확인해볼 수 있다. 그렇다면, 이미 답을 알고있다고 가정하고 시뮬레이션을 돌려보자. 그리고 뽑히는 순서대로 1,2,3... 을 넣어준 후, 답의 출력순서대로 다시 짜맞춰주면 된다. 무슨 말이냐면, 아래 그림을 봐보자. 그리고 자바에서 클래스는 주소값을 기준으로 저 링크를 연결해두기 좋다. 그러니 ?로 된 카드들을 배열에 넣어두고, 해당 값들을 덱에다가 미리 넣어둔다(위 그림의 '1'에서 위쪽 파란거 3개가 배열, 아래쪽이 덱에 들어간걸.. 2022. 6. 30.
[자바] 프로그래머스 - 프린터 (programmers java) 문제 : programmers-프린터 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 문제에서 제시된 대로 시뮬레이션을 돌려주면 된다. 이 때 서브 문제로 문제를 나눠서 생각해보자. 1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다. 2. 현재 꺼내지 않은 대기목록에서 중요도가 가장 높은 값을 알 수 있어야 한다. 3. location으로 지정된 문서의 위치를 항상 알 수 있어야 한다. 위의 3가지를 모두 할 수 있다면 이 문제를 풀 수 있다. 그럼 각각 어떻게 해야할지 생각해보자. 1. 대기목록의 앞에서 꺼내고, 뒤에 다시 넣을 수 있는 자료구조를 선택해야 한다. 사실 이걸 만족하는 자료구조는 엄청.. 2022. 5. 4.
백준 1187 자바, C++ - 숫자 놀이 (boj 1187 java c++) 문제 : boj1187 감을 제대로 못잡고 있었는데, '수학귀신' 책을 추천해줬던 수학 잘하는 선배같은 동생의 도움으로 풀 수 있었다. 1. 귀납법(귀납 추론)으로 풀 수 있는 문제이다. 1.1 k=1 k를 1부터 증가시켜 나가면서 생각해보자. 우선 k=1일 때, N은 2가 된다. 이 때 2*2-1 = 3개 중 합이 2로 나누어 떨어지는 2개를 뽑는 문제가 된다. 그럼 2*2-1개의 수가 어떻게 나와야 2로 나눌 수 있는 2개를 뽑을 수 있을까? 이 때 모든 경우를 나타내보면 다음과 같다. A. 3개의 수가 모두 짝수일 경우 -> 아무거나 2개 뽑으면 된다. B. 3개의 수가 모두 홀수일 경우 -> 아무거나 2개 뽑으면 된다. C. 3개의 수가 짝수2개, 홀수1개인 경우 -> 짝수 2개를 뽑으면 된다. .. 2022. 4. 1.
백준 1806 자바 - 부분합 (BOJ 1806 JAVA) 문제 : boj1806 1. 틀린 방법 ※ 제가 틀린 방법에 대해 써둔 것으로, 해설만 보고 싶다면 2번부터 보시면 됩니다. 덱에 모든 값들을 담으면서 그 합을 따로 계산한다. 그럼 일단 그 합은 최대치로 나올 수 있는 합이 될 것이다. 그 합이 S보다 작다면 0을 출력하고, 그렇지 않다면 합이 S보다 작아질 때 까지 덱의 시작부분과 끝부분을 각각 peek 해봐서 둘 중 작은 값을 덱에서 빼버린다. 이렇게 하면 그리디하게 답을 구할수 있을줄 알았다. 예를들어 S가 5일 때 다음과 같이 수행한다. 이렇게 짠 코드는 다음과 같다. ※ 틀린 코드임 ... int n = nextInt(); int s = nextInt(); int sum = 0; Deque dq = new ArrayDeque(); for (in.. 2022. 1. 23.
자료구조 큐, 스택, 덱 (Queue, Stack, Deque) Queue, Stack, Deque(=Double-ended Queue) 큐, 스택, 덱은 배열, 리스트와 함께 선형 자료구조에 속하는 자료구조들이다. 사실 큐, 스택, 덱의 모든 기능은 리스트(이하 '리스트'라는 단어는 모두 Linked List를 뜻함)만 사용해서도 시간복잡도 마저 동일하게 동작할 수 있다. 즉, 어찌보면 스택, 큐, 덱은 리스트에 포함되는 자료구조라고 볼 수 있다. 그럼에도 큐, 스택, 덱은 분명 리스트와는 별개의 자료구조로 정의되어 사용되고 있다. 이건 일종의 컨셉, 규칙에 해당한다고 생각한다. 술먹고 있는데 상대방이 갑자기 병따개를 준다. 병따달라는 의도를 바로 파악할 수 있다. 술먹다가 이번엔 상대방이 멀티툴을 갑자기 준다. 물론 멀티툴엔 병따개가 있다. 하지만 난 멀티툴을 받.. 2021. 10. 11.

티스토리툴바