코드저장소

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

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

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

N개의 수가 주어졌을 때, 오름차순으로 정렬하는 간단한 프로그램 구현 문제이다. 중요한 것은 제한사항인데, 입력에는 중복된 값이 있을 수 있고, 최대 값은 10000이다. 나는 이전 수 정렬 문제들을 sort() 메서드를 이용하여 풀었는데 (이미 해당 메서드를 알고 있었다.) 이번 문제에서 카운팅 정렬과 sort()메서드의 속도를 비교해 보기로 하였다. 우선, 2751번 - 수 정렬하기 2 (실버 5) 에서 사용하였던 오름차순 정렬 코드를 살펴 보자. 2751번 - 수 정렬하기 2 (실버 5) https://www.acmicpc.net/problem/2751 위 문제 역시 오름차순으로 입력받은 값을 정렬하기만 하면 되는데, 두 문제의 차이는, 최대 값과 중복값의 여부이다. 다만, 위의 문제는 효율성을 검..

조건문 단계 역시 단순한 If문의 연속인 만큼 크게 어려운 문제는 없었다. 몇가지 기초적인 실수를 했던 것을 다시 한번 복습해본다. 9498번 - 시험 성적 (브론즈 5) class Main{ public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); int point = sc.nextInt(); switch(point) case point >= 90 : System.out.println('A'); break; case point = 80 : System.out.println('B'); break; case point = 70 : Syst..

코딩 테스트를 준비하며 백준의 기본 문제를 단계별로 풀어보기로 하였다. 원래는 프로그래머스에서 코딩 테스트를 준비하고 있었는데, 프로그래머스에는 입출력 단계가 빠져있어 실제 코테와 환경이 조금 달랐다. 평소 IDE 환경에 익숙해 있었던 터라 아예 깡코딩으로 하는 백준이 더 도움이 될것 같아 백준으로 다시 문제를 풀어기로 하였다. 첫날에는 가볍게 입출력과 사칙연산 모든 문제를 풀어보는 것으로 시작하였다. 크게 어려운 것은 없었고 좀 생각해 봐야할 것은 BufferedReader 쪽이였는데, 기존에 항상 Scanner만 사용하던 방식과 달라 새로웠다. ChatGPT에게 BufferedReader에 대하여 물어보니 다음과 같은 답변을 받았다. BufferedReader 클래스는 Java의 입출력 스트림을 이용..