코드저장소

이번 문제는 각각의 집을 RGB중 하나로 칠한다고 할때, 규칙을 만족하면서 비용의 최솟값을 구하는 문제이다. 핵심은i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다라는 조건을 어떻게 구현할 것인지 였는데 어느정도 동적계획법에 익숙해져서 인지 아니면 문제가 쉬웠던 건지 조금 생각해본 후에 간단하게 풀어 낼 수 있었다. 그럼 어떻게 풀었는지 되짚어 보자. 규칙은 무엇인가? 우선 입력값을 보면 딱 봐도 2차원 배열 형태로 저장해야 할 것 같은 느낌이 든다. 예제 입력 1을 기준으로 살펴보자. 나는 이번 동적계획법을 2차원 배열을 사용하여 구현했다. 우선 각각의 값을 기록하기 전 초기 상태는 다음과 같을 것이다. 0 1 2 26 40 83 당연히 0번 index에는 첫행이 ..

이번 문제는 특정 수열 A가 주어 졌을때, 가장 긴 증가하는 부분의 수열길이를 구하는 문제이다. 나는 Top-Down 방식으로 구현하였는데 어떤 부분에서 잘못 생각을 했고 어떻게 풀어 냈는지 살펴보자. 문제를 살펴보자! 문제 자체는 사실 비교적 간단해 보인다. 가장 작은 값과 가장 큰 값을 찾은 후 둘 사이의 값이 몇개인지만 찾아내면 되기 때문이다. 간단하게 표를 만들어 살펴보자. 0 1 2 3 4 5 10 20 10 30 20 50 1 2 1 3 2 4 각 값을 들어온 순서대로 배열에 담는다면 위와 같이 담기게 될 것이다. 그렇다면 10~50 사이에는 10, 20, 30, 50이라는 4개의 값이 들어오기 때문에 최종적으로 가장 긴 배열의 길이는 4이다. 중간에 같은 값이 껴있더라도 어차피 최소 숫자 ~..

이번 문제는 동적 프로그래밍을 이용하여 배낭에 넣을 수 있는 최대 가치 값을 찾아내는 문제이다. 골드 난이도 답게 난도가 좀 있었는데 혼자서 이리저리 짜보다가 생각처럼 잘 되지 않아 ChatGpt의 도움을 약간 받아 해결하였다. 그러면 어떻게 문제를 풀었고 어디가 문제였는지 살펴보자. 무엇이 반복되는가? 이전 글에서도 서술 했지만 동적 계획법의 핵심은 반복되는 요소를 기록하여 시간을 단축시키는 것이다. 그러면 무엇이 반복되는 것이고 그것을 어떤 방법으로 기록할 것인지가 핵심이 되겠다. 문제는 배낭의 넣을 수 있는 물건들의 최대 가치값만을 요구하고 있기 때문에 안에 몇개가 들어가는지, 몇종류가 들어가는지는 중요하지 않다. 즉, 배낭에 무게별로 들어가는 가치합이 반복되는 요소가 될 것이다. 그럼 남은 문제는..

이번 문제는 동적 프로그래밍을 이용하여 피보나치 수열을 풀어보는 문제이다. 기존에 재귀를 이용하여 피보나치 수열을 계산하는 것을 해보았지만, 이번에는 동적 프로그래밍을 이용하여 더 빠르고 효율적인 프로그래밍을 하는것이 목적이다. 그럼 우선 동적 계획법에 대해서 자세하게 살펴보자. 동적 계획법(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에서 삽입과 삭제의 연산이 같이 이루어지며, ..

이번 문제는 배열이 주어졌을 때, 두 배열의 차집합의 원소 갯수를 구하는 문제이다. 나는 처음에는 HashMap을 이용했는데 가만히 생각해보니 HashSet을 이용해야 했다는 것을 알았다. 우선 구현한 코드를 먼저 보고, 무엇이 잘못 되었고 왜 HashSet을 사용해야 하는지 살펴보자. import java.io.*; import java.util.*; class Main{ public static int n,m; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().sp..

이번 문제는 1차원 배열이 아닌 2차원의 배열을 오름차순으로 정렬하는 문제이다. 2차원 배열을 정렬하기 위해선 기존 sort()메서드를 바로 사용할 순 없고 약간 다르게 사용해야 했는데 그럼 2차원 배열을 정렬 하는 방법을 알아보자. Comparator 익명 클래스 구현 2차원 배열에서 Arrays.sort() 메서드를 사용하게 되면, java.lang.ClassCastException: I cannot be cast to java.lang.Comparable이란 오류가 발생하게 된다. 비교 기준이 정의 되어있지 않기 때문인데, 때문에 Comparator 인터페이스를 구현하여 정렬기준을 추가해 줘야한다. comparable, comparator 구현에 대해서 잘 정리된 글이 있어 참고하였다. https:..