본문 바로가기

알고리즘8

백준)11052.카드구매하기 - 풀이(JAVA) 처음에는 n보다 작은 자연수들을 더해서 n을 만드는 경우를 구해야 한다고 생각했다. 그런 방향으로 풀다가 시간초과가 나버렸고 구글링 끝에 간단한 방법이 있어 정리해본다. 카드 n개를 구매하는 방법은. n개가 들어있는 팩을 구매하거나, 또는 카드 1개가 들어있는 팩을 구매하고 n-1개가 들어있는 팩을 구매한다. 카드 2개가 들어있는 팩을 구매하고 n-2개가 들어있는 팩을 구매한다. . . . 이런식의 방법이 있다. 가장 큰 비용으로 n개를 구매하는 방법까지 도달하기 전에 n보다 작은 카드들을 가장 큰 비용으로 구매하는 법들을 기억(memomemoization)해놓고, 이전에 구했던 값들을 이용해 n개를 가장 큰 비용으로 구매하는 법을 구하는 방식으로 접근해야 하는 문제다. (Dynamic Programmi.. 2020. 10. 26.
백준)1018.체스판 다시 칠하기 - 풀이 및 반례(JAVA) 작년 8월 같은 문제를 풀고 포스팅 한 적이 있다. 마음 같아선 작년의 모든 포스팅을 삭제하고 싶지만, 내 블로그의 취지인 '성장의 기록'을 위배하는 듯 하여 남겨둔다ㅎㅎ 작년 같은 문제 포스팅(별로 도움 안됩니다) dreamingdreamer.tistory.com/73?category=797039 백준)Q.1018_체스판 다시 칠하기(완전탐색(Brute-fore Search)) https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가. dreamingdreamer.tistory.com 작년의 코드와 크게 다른 점은,.. 2020. 10. 16.
백준)Q.1018_체스판 다시 칠하기(완전탐색(Brute-fore Search)) https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은.. 2019. 8. 25.
백준)Q.2503_숫자야구(완전탐색(Brute-fore Search)) https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다. www.acmicpc.net 문제 정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다. 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구.. 2019. 8. 24.
[Java] 컬렉션 프레임웍(Collections Framework) 연습문제 * 이 포스팅의 연습문제는 남궁성 선생님의 자바의 정석에 수록된 문제이며 정답 및 해설은 본인의 의견입니다. * 연습문제 PDF파일은 아래 남궁성 선생님의 GitHub에서 다운 받으실 수 있습니다. https://github.com/castello/javajungsuk3 castello/javajungsuk3 soure codes and ppt files of javajungsuk 3rd edition - castello/javajungsuk3 github.com [11-1] 다음은 정수집합 1,2,3,4와 3,4,5,6의 교집합, 차집합, 합집합을 구하는 코드이다. 코드를 완성하여 실행결과와 같은 결과를 출력하시오. [Hint] ArrayList클래스의 addAll(), removeAll(), reta.. 2019. 8. 23.
백준)Q.1924_2007년 문제 오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 빈 칸을 사이에 두고 x(1≤x≤12)와 y(1≤y≤31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. 출력 첫째 줄에 x월 y일이 무슨 요일인지에 따라 SUN, MON, TUE, WED, THU, FRI, SAT중 하나를 출력한다. 예제 입력 1 1 1 예제 출력 1 MON 예제 입력 2 3 14 예제 출력 2 WED import java.util.*; public class Main { public static void main(S.. 2019. 4. 15.

티스토리툴바