알고리즘/백준 알고리즘

[백준 11052] 붕어빵 판매하기

글에 개요 백준 알고리즘 11052번 "붕어빵 판매하기" 문제입니다.이 문제는 DP(동적 계획법)을 활용하는 문제로 '1,2,3의 조합으로 나타내는 방법의 수' 뒤로 연습해보면 좋은 문제입니다.역시 손으로 어느 정도의 규칙이 발견된 후에 점화식을 세우는 것이 좋은 방법인 것 같습니다. 아마 동적 계획법에 사용되는 점화식의 활용에 익숙해지고, 이후 재귀함수로 구현할 때 Top-down, Bottom-up 방식해 질 때까지 최대한 꾸준히 풀어볼 생각입니다. [백준 11052] 붕어빵 판매하기: https://www.acmicpc.net/problem/11052 참고할 글[백준 9095] 1, 2, 3 더하기 : http://brenden.tistory.com/29[백준 10942] 팰린드롬? : http:/..

2018. 4. 20. 11:39

알고리즘/백준 알고리즘

[백준 9095] 1, 2, 3 더하기

글에 개요 백준 알고리즘 9095번 "1, 2, 3 더하기" 문제입니다.이 문제는 DP(동적 계획법)을 활용하는 문제로 팰린드롬에 이어 2번째 등장이네요.아마 동적 계획법에 사용되는 점화식의 활용에 익숙해지고, 이후 재귀함수로 구현할 때 Top-down, Bottom-up 방식해 질 때까지 최대한 꾸준히 풀어볼 생각입니다. [백준 9095] 1, 2, 3 더하기: https://www.acmicpc.net/problem/9095 참고할 글[백준 10942] 팰린드롬? : http://brenden.tistory.com/27핵심 내용정수 n을 1,2,3의 조합으로 나타내는 방법의 수를 구하는 문제입니다.D[i] = i를 1,2,3의 조합으로 나타내는 방법의 수D[i] = D[i-1] + D[i-2] + D..

2018. 4. 20. 11:12

알고리즘/백준 알고리즘

[백준 11048] 이동하기 (DP, 최댓값,최솟값 구하는 문제로 확장)

글에 개요 백준 알고리즘 11048번 "이동하기" 문제입니다. DP를 활용하는 기본적인 문제입니다.해당 문제는 이동하면서 주울 수 있는 캔디의 최댓값을 구하는 문제이지만 캔디의 최솟값을 구하는 문제로도 확장해서 해결해 보겠습니다.두 가지 방법으로 해결하겠습니다. 하지만, 핵심은 같습니다!!!최댓값 구하는 방법은 [해결방법1번]으로 구하는게 좋습니다!!최솟값 구하는 방법은 [최솟값 해결방법2번]으로 구하는게 깔끔합니다!! [백준 11048] 이동하기 : https://www.acmicpc.net/problem/11048 핵심 내용시간 초과 이슈를 줄이기 위해 DP를 활용하자!!(1,0), (0,1), (1,1) 방향으로 이동할 수 있지만 점화식을 세울 때 생각해보면, 캔디 숫자는 음수가 될 수 없으므로 (..

2018. 4. 17. 16:39