DP

메모이제이션 메모이제이션이란 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 실행 속도를 빠르게 하는 기술입니다. 이는 동적 계획법(Dynamic Programming)에서 핵심이 되는 기술입니다. 캐싱이라고 표현되기도 합니다. 예를 들어 재귀 함수를 사용한 피보나치 수열 함수가 있다고 해봅시다. func fibonacci(_ n: Int) -> Int { if n Int { var fiboArray: [Int] = [0, 1] guard n > 1 else { return n } for num in 2...n { fiboArray.append(fiboArray[num - 2] + fiboArray[num - 1]) } return fiboArray..

[Silver III] 피보나치 - 9711 문제 링크 성능 요약 메모리: 79720 KB, 시간: 988 ms 분류 다이나믹 프로그래밍, 수학 문제 설명 피보나치 수열은 아래와 같이 표현된다. 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다. P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라. 입력 첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 P와 Q가 주어진다. 출력 각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다. x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다. 풀이 i) 첫 시도에서는 P의 최대..

[Gold V] 비밀번호 만들기 - 17218 문제 링크 성능 요약 메모리: 69100 KB, 시간: 8 ms 분류 다이나믹 프로그래밍, 문자열 문제 설명 최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자. 입력 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는..

[Silver II] 가장 긴 증가하는 부분 수열 - 11053 문제 링크 성능 요약 메모리: 79516 KB, 시간: 20 ms 분류 다이나믹 프로그래밍 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 i) 해당 문제는 DP문제로, d..

[Gold IV] 최대 정사각형 - 4095 문제 링크 성능 요약 메모리: 77036 KB, 시간: 2476 ms 분류 다이나믹 프로그래밍 문제 설명 1과 0으로 이루어진 NxM크기의 행렬이 주어졌을 때, 1로만 이루어진 가장 큰 정사각형 부분 행렬 찾는 프로그램을 작성하시오. 입력 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 개가 주어진다. 출력 각 테스트 케이스에 대해서 가장 큰 정사각형의 너비 또는 높이를 출력한다. 만약 그런 정사각형이 없을 때는 0을 출력한다. 풀이 i) DP문제로, 현재 인덱스 값이 1이라면 현재 인덱스를 기준으..