분류 전체보기133 [코딩테스트/백준 알고리즘] 11726번 : 2×n 타일링 (자바, Java 풀이) 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 설명 문제 풀이 2 X n 사각형의 제일 왼 쪽에 타일을 놓을 수 있는 방법은 두 가지가 있다. 이 두 경우를 고려해서 가로 폭을 2칸 줄인 2 X (n - 2)의 경우와, 가로 폭을 1칸 줄인 2 X (n - 1)의 경우로 나눠서 해결할 수 있다. 따라서 memo[n] = memo[n - 1] + memo[n - 2]로 구할 수 있다. 예제) 코드 import java.util.*; class Main{ .. 2022. 8. 29. [코딩테스트/백준 알고리즘] 1463번 : 1로 만들기 (Java, 자바 풀이) 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 문제 풀이 정수 n이 입력으로 들어왔을 때 n에 사용할 수 있는 연산은 아래와 같다. 1. n이 3으로 나누어 떨어질 때 memo[n / 3] + 1 2. n이 2로 나누어 떨어질 때 memo[n / 2] + 1 3. n에서 1을 뺄 때 memo[n - 1] + 1 세 값 중 최소값이 memo[n]에 들어가게 된다 n이 10일 때, 호출되는 함수 n이 10일 때, memo[] 배열 n 1 2 3 4 5 6 7 8 9 10 memo[n] 0 1 1 2 3 2 3 3 2 3 코드 import jav.. 2022. 8. 29. [코딩테스트/알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. 1940년 Richard Bellman이 처음으로 Dynamic Programming이란 단어를 사용했는데 멋있어 보여서 이름 붙였다고 한다. (궁금해서 찾아보니까 벨만-포드 알고리즘의 그 벨만이 맞았다.) 다이나믹 프로그래밍으로 문제를 풀기 위한 조건 1. Overlapping Subproblem 문제를 작은 문제로 쪼갤 수 있다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. 2. Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 각 문제들은 Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정.. 2022. 8. 29. [코딩테스트/백준 알고리즘] 1966번 : 프린터 큐 (Java, 자바 풀이) 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 설명 문제 이해 큐를 사용하면 쉽게 해결할 수 있는 문제다. 맨 마지막 테스트 케이스인 6 0 1 1 9 1 1 1 에 대해 분석해보자. 테스트 케이스를 입력받은 큐의 상태는 위와 같다. 우선 순위가 가장 높은 2번 문서가 큐의 맨 앞에 올때까지 그 외 문서는 큐의 맨 뒤로 옮긴다. 우선 순위가 가장 높은 2번 문서가 큐의 맨 앞에 왔다면 문서를 인쇄한다. 이후 문서들의 우선순위는 모두 같.. 2022. 8. 11. 이전 1 ··· 13 14 15 16 17 18 19 ··· 34 다음
