전체 글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. [코딩테스트/백준 알고리즘] 10773번 : 제로 (Java, 자바 풀이) 문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 설명 문제 풀이 "이 문제를 풀 때 스택을 쓰지 않으면 너는 바보야" 라고 온몸으로 외치고 있는 문제다. 스택에 수를 입력하다 0이 나오면 top에 위치한 수를 제거한다. 수의 입력이 끝나면 스택에 남은 수의 합을 구한다. 코드 import java.util.*; class Main { public static void main(String[] args.. 2022. 8. 11. [코딩테스트/백준 알고리즘] 1024번 : 수열의 합 (Java, 자바 풀이) 문제 https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 문제 풀이 어떤 수 x가 있을 때, k개의 연속적인 합을 구하는 식을 만들면 아래의 표와 같다. k k개의 연속인 합 식 1 x x 2 x + (x + 1) 2x + 1 3 x + (x + 1) + (x + 2) 3x + 3 4 x + (x + 1) + (x + 2) + (x + 3) 4x + 6 5 x + (x + 1) + (x + 2) + (x + 3) + (x + 4) 5x + 10 ... ... ... k x + .. 2022. 8. 10. 이전 1 ··· 8 9 10 11 12 13 14 ··· 23 다음
