[알고리즘] Dynamic Programming (동적 계획법)
Dynamic Programming (동적 계획법)이란? 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것입니다. DP는 왜 사용하는 걸까? 피보나치 수열을 예시로 들 수 있습니다. 피보나치 수열은 아래와 같습니다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... => fibo(n) = fibo(n-1) + fibo(n-2) 이런 알고리즘에서 f(n)을 호출한다고 하면 아래와 같이 중복되는 숫자들이 늘어나게 됩니다. 즉, 시간복잡도가 O(2^n)이 걸리게 됩니다. 하지만 이미 계산했던 값들을 저장한다면 O(n)까지 줄일 수 있습니다. 이것이 DP를 사용하는 이유입니다. DP의 접근방식 기본적..
2023. 2. 12.
[BOJ][Java] 백준 2011번: 암호코드
문제 설명 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아? 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, ..
2022. 7. 3.
백준 / BOJ / 11660 / 구간 합 구하기 5
문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 ..
2021. 11. 6.
