코딩 레시피

Algorithms/DP 검색 결과

해당 글 24건

[BOJ 1904] 01타일(C++)

01타일 (Silver 3) 문제 전체 문제 보기 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 접근법 이번 문제에서 구해야 하는 값은 1 타일과 00 타일을 활용해서 자릿수 N이 주어졌을 때 지원이가 만들 수 있는 모든 이진수 가짓수이다. 여기서 N의 값은 1,000,000 이하의 자연수로 꽤 크다. 그래서 자릿수 N이 주어졌을 때 지원이가 만들 수 있는 이진수의 최댓값은 \(2^1,000,000\)으로 모든 경우의 수를 따져보는 것은 불가능하다. 때문에 우리는 임의의 N에서 만들 수 있는 이진수의 가짓수 규칙..

Algorithms/DP 2021. 8. 16. 23:16

[BOJ 9184] 신나는 함수 실행(C++)

신나는 함수 실행 (Silver 2) 문제 전체 문제 보기 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 접근법 해당 문제에서 주어진 재귀 함수는 매우 복잡하고 함수의 호출 순서를 이해한다는 것은 거의 불가능에 가깝다. 시간 복잡도 또한 못 해도 \(O(4^n)\)은 훨씬 넘어 보인다. 그래서 한번 계산한 결과를 저장하여 활용하는 동적 프로그래밍으로 중복계산을 줄여서 문제를 풀어야 한다. 구현 a, b, c가 음수이거나 20 보다 큰 경우는 재귀함수의 예외처리에서 걸러진다. 때문에 배열은 0~20까지의 인덱스만..

Algorithms/DP 2021. 8. 13. 12:01

[BOJ 1003] 피보나치 함수 (C++)

피보나치 함수 (Silver 3) 문제 전체 문제 보기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 접근법 이 문제는 피보나치 함수를 조금 변형한 형태로 f(n)을 호출했을 때 f(0)과 f(1)이 각각 몇 번 호출되는지 구하는 문제이다. 피보나치는 무식하게 계산할 경우 \(O(2^n)\)이기 때문에 계산 결과를 저장하는 동적 계획법으로 접근해야한다. 동적계획법으로 풀 경우 \(O(n)\)로 풀이가 가능하다. 점화식을 살펴보면 다음과 같이 피보나치수열 와 동일하다. \[f(n) = f(n-1) + f(n-2)\] 구현 이 점화식을 0과 1에 같이 적용하여 다음과 같은 코드를 작성할 수 있다. #incl..

Algorithms/DP 2021. 8. 13. 11:40

[BOJ 2156] (동적계획법) 포도주 시식 (C++)

포도주 시식(Silver 1) 문제 전체 문제 보기 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 접근법 이 문제에서 구해야 하는 값은 주어진 규칙에 따라 포도주를 시식할 때 마실 수 있는 포도주의 최댓값이다. 주어진 규칙은 다음과 같다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 이를 일반화 해서 생각해 보자. n개의 포도주잔이 있을 때 n번째 잔을 마시는 것이 좋을지 마시지 않는 것이 좋..

Algorithms/DP 2021. 8. 11. 10:05