알고리즘9 [Java]백준 11726번 2Xn 타일링(Dynamic Programming) www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 2 x n 직사각형을 2x1 과 1x2 사이즈의 타일로 채우는 방법의 경우의 수를 찾는 문제이다 1. n = 1일 경우 2x1 타일 한개 배치 2. n = 2일 경우 2x1 타일 2개 or 1x2 타일 2개 배치 3. n = 3일경우 n =1 일 경우와 n = 2 일 경우의 타일 배치 이용하여 새로운 모양 등장 x => n이 3일 경우 -> n이 1일 경우 + n이 2일 경우 ∴ dp[i] = dp[i-1] + dp[i-2] .. 2020. 5. 8. [Java] 백준 2293번 동전 1 (Dynamic Programming) www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 1원 = 1 2원 = 1 + 1 = 2 3원 = 1 + 1 + 1 = 2 + 1 4원 = 1 + 1 + 1 + 1 = 2 + 2 5원 = 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 6원 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 2 .... 만약 5원을 구한다고 하면 - 4원에서 +1 -> 1가지 - 3원에서 +2 -> 2가지 - 0원에서 +5 -> 1가지 => 총 4가지 N번째.. 2020. 5. 8. [Java] 백준 9461번 (Dynamic Programming) www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 풀이 변의 길이가 1인 정삼각형에서 시작하여 변을 이어가며 정삼각형을 그리는 문제로 P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2 ... P(11) = 12까지 예시가 주어져있다. 위 규칙을 통해 P(N) = P(N-1) + P(N-5) 를 알 수 있다 P(1) ~ P(5)일 경우는 예외로 두고 N = 6일때부터 풀었다 cf) N이 100까지로 한정되어 있기때문에 이 범위.. 2020. 5. 8. 큐(Queue)란? 큐의 개념 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식 삭제의 위치와 방법이 제한되어 있는 유한 순서 리스트 스택(LIFO)과 반대되는 개념 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황(프린터의 출력 처리, 윈도 시스템의 메시지 처리기 등)에서 이용 큐의 연산 enQueue : 큐 안에 데이터를 넣는 연산 deQueue : 큐 안의 데이터를 빼내는 연산 peek : 큐의 front 데이터를 반환하는 연산 isEmpty : 큐가 빈 경우 true를 그렇지 않은 경우 false를 반환 큐의 종류 선형 큐(Linear Queue) 기본적인 큐의 형태 막대 모양으로 된 큐 크기가 제한, 빈 공간 사용 시 모든 자료를 꺼내거나 옮겨야 하는 .. 2020. 4. 21. 이전 1 2 3 다음
