코드저장소

이번 문제는 동적 프로그래밍을 이용하여 피보나치 수열을 풀어보는 문제이다. 기존에 재귀를 이용하여 피보나치 수열을 계산하는 것을 해보았지만, 이번에는 동적 프로그래밍을 이용하여 더 빠르고 효율적인 프로그래밍을 하는것이 목적이다. 그럼 우선 동적 계획법에 대해서 자세하게 살펴보자. 동적 계획법(Dynamic Programming) 이란... 동적 계획법(줄여서 DP라고 부르기도 한다.) 을 간단하게 설명하면 답을 재활용하는 것이다. 좀 더 본질적인 의미를 살리자면 기억하며 풀기라고 생각해도 되겠다. 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거의 구한 해를 활용하는 것이 동적 계획법의 핵심이다. 문제를 작은 문제로 쪼개어 생각한다는 점에서 분할 정복 알고리즘과 비슷하게 보이기..

이번 문제는 주어진 테스트 케이스의 각각의 경우의 수를 출력하는 문제이다. 위 문제를 풀기 위해서는 이항 계수를 이해할 필요가 있는데 수학을 조금 아는 사람이라면 로직 자체는 어렵지 않기 때문에 금방 풀 수 있을 것이다. 하지만 나는 수학에 손을 놓은지 꽤 된 터라... 문제를 이해하는데 꽤나 애를 먹었다. 그러면 이항계수가 무엇이고 이를 이용하여 어떻게 문제를 풀어야 하는지 알아보자. 이항 계수(Binomial Coefficient)란? en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient - Wikipedia en.wikipedia.org 이항 계수에 대한 정확한 개념은 위 글에 잘 정리가 되어있다. 이항계수란 주어진 크기의 집합에서 원하는..

이번 문제는 덱을 이용하여 스택과 큐가 혼합된 자료구조에 배열이 입력되었을때 출력 값을 구하는 문제이다. 문제를 이해하는데 꽤 애를 먹었는데 각각의 자료구조에 한 개의 원소가 들어있다라는 문구를 제대로 이해하지 못해서 처음에는 입력받은 자료구조의 배열을 통과하면서 스택과 큐로 변형되는 문제인줄 알았다가 예시를 한참 보고서야 제대로 이해할 수 있었다. 문제부터 이해하자! 예시를 잘 살펴보면서 문제를 이해해보자. 첫번째 예시에서 자료구조는 [큐,스택,스택,큐]의 구조로 이루어진다. 그리고 통과할 배열은 [1,2,3,4]로 이루어져있다. 나는 처음에 초기 상태를 보고 첫번째에는 2라는 입력값이 큐로 한번 통과하여 [2,3,4,2]로 나오고 그다음 출력된 1을 스택으로 통과시켜 [2,3,4,2]로 나오게 하여 ..

덱(Deque)이란? 덱(Deque)이란 양끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 큐와 스택의 성질을 모두 가지고 있는 자료구조이다. 양쪽에서 모두 삽입과 삭제가 가능하기 때문에 First,Last로 앞에서 처리할지 뒤에서 처리할지를 결정 할 수 있으며 보다 자유롭게 사용이 가능한 큐라고 이해해도 무방하겠다. 중복 원소를 허용하며 크기 제한이 없는 것도 특징이다. 덱의 특징 덱은 기본적으로 큐이기 때문에, 큐처럼 구현체를 만들어 사용하여야 한다. java.util.Deque 인터페이스를 구현한 클래스를 사용하면 되며 일반적으로는 ArrayDeque와 LinkedList를 사용한다. 덱의 주요 메서드는 다음과 같다. addFirst(E e) / offerFirst(E e): 덱의 맨 앞에 원소..

스택(Stack)이란? 스택(stack)이란 책을 쌓는 것처럼 쌓아 올려진 형태의 자료구조를 말한다. 가령, A,B,C라는 책을 상자에 넣고 뺀다고 생각해보자. 넣을 때는 A,B,C 순으로 들어가겠지만, 뺄때는 C,B,A순으로 빼내어야 한다. 이런 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 한다. 스택의 특징 앞서 설명했듯, 스택은 먼저 들어간 것이 가장 나중에 나오는 형태이다. 따라서 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근 할 수 있다는 특징이 있으며 이러한 특징 때문에 역순 문자열 만들기, 실행 취소, 웹 브라우저 방문 기록(뒤로가기) 등의 분야에서 활용된다. 스택은 top에서 삽입과 삭제의 연산이 같이 이루어지며, ..