ㅅㅇ

동적계획법 DP 란? 다이나믹 프로그래밍 이라고도 불리며, 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나눠서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정. 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계 기법. 동적계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있음. 전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해 전체 문제를 해결하는 방식이라고 볼 수 있음. == > 규칙을 찾는 게 관건. ! 동적 계획법 접근 방법 1) Bottom Up 방법 작은 문제에서 큰 문제로 반복문 호출 2) Top Down 방법 큰 문제에서 작은 문제로 재귀 호출 - 메모이제이션 : 중복된 계산을 방지하기 위해 앞 계산을..

1. 재귀함수란 메소드 혹은 함수의 내부에서 자신의 메소드 혹은 함수를 다시 호출하여 작업을 수행하는 방식의 함수를 의미. 다른 말로는 재귀호출, 되부름이라고 부르기도 한다. 2. 재귀함수의 원리 재귀 함수를 작성할 때는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다. = = > 조건문을 활용하여 재귀함수 종료 조건을 삽입해야 함. 3. 재귀함수 사용 이유 코드의 간결화 및 변수 사용 최소화 4. 예시 문제 - 재귀함수를 활용한 완전탐색 data = [3, 5, 8] 에서 성분들의 합을 표현할 수 있는 경우의 가지수는? data = [3,5,8] def recur(index, value): if index =..

문제 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다. 출력 첫째 줄에 B진법 수 N을 10진법으로 출력한다. 예제 입력 1 ZZZZZ 36 예제 출력 1 60466175 문제풀이 소스 코드 1 - int (N, B) 함수 : B 진수인 N을 10진수로 변환해줌. - 첫 번째 인자는 무조건 문자열이여야 한다. N,B = input().split() ..

문제 상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. 팩토리얼 진법은 각 자리에 올 수 있는 숫자는 0부터 9까지로 10진법과 거의 비슷하다. 하지만, 읽는 법은 조금 다르다. 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다. 팩토리얼 진법으로 작성한 숫자가 주어졌을 때, 10진법으로 읽은 값을 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 ..

문제 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에..