본문 바로가기

Development/알고리즘5

다이나믹프로그래밍 - 백준 1932 풀이 다이나믹프로그래밍 백준 1932 문제 풀입니다. ▶ 문제 우선 dp[i][j] 의 형태로 점화식이 만들어 질 것 같네요. 그렇게 생각을 한 이유는 아래층에 있는 수(1) 는, 현재 층에서 선택된 수의 왼쪽대각선 또는 오른쪽 대각선 (N) 에 있는 것 중에서만 선택을 할 수 있다고 하였으니까요. 1개의 숫자가 선택을 할 수 있는 경우의 수는 2가지이네요. 그렇기 때문에 dp[i][j]의 형태의 점화식이 만들어 질 것입니다. 자, 문제 해결의 키포인트 입니다. 각 숫자의 맨 왼쪽과 오른쪽은 항상 일정한 위치의 값만 받아올 수 있습니다. 위의 그림을 예로 들면 3이 선택할 수 있는 숫자는 오른쪽에 있는 7과 왼쪽에 있는 어떠한 값이겠네요. 그런데 왼쪽에는 값이 없죠. 그렇기 때문에 맨 왼쪽에 있는 숫자는 항상.. 2018. 3. 23.
[DP]백준 11052 - 붕어빵 판매하기 붕어빵 판매하기 - 링크 다이나믹 프로그래밍을 이용해서 풀어낼 수 있는 문제. dp[n] = n개의 붕어빵을 팔았을 때 얻을 수 있는 최대 이익. X명의 사람에게 붕어빵 [ N ]개를 팔아야 한다. 맨 처음 사람에게 [ i ]개의 붕어빵을 팔았다고 하면 X-1명의 사람들에게는 [ N-i ]개의 붕어빵을 팔아야 한다. (사람의 수 X는 중요하지 않다. 어차피 다 팔린다고 가정을 하고 풀기 때문. 이해하기 쉽도록 X명이 있다고 표현) 점화식으로 풀어보자. dp[N] = max( p[i] + dp[N-i] , dp[N] ) N개를 한번에 다 파는 경우가 가장 비쌀 수도 있기 때문에, max를 이용해서 최대값을 뽑아낸다. < 코드작성 > 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17.. 2018. 1. 19.
[알고리즘] 미로찾기 알고리즘 - 재귀함수 미로찾기알고리즘 - 재귀함수 [미로 표현] - 아래와 같은 미로가 있다.- 녹색은 숲으로 막혀있고 오직 흰색 길을 통해서만 나갈 수 있다.- 숲으로 들어가면 야생 동물들에게 잡하먹히기에 갈 수가 없다. 위와 같은 규칙이 있다고 할 때 미로는 아래 사진과 같이 생겼을 것이고 이를 2차원 배열로 바꿔서 풀어보면[9][10]의 배열이기 때문에 다음과 같이 나타낼 수 있습니다. - 1은 갈 수 없는 길, 0은 갈 수 있는 길- 시작은 [1][0], 출구는 [8][4] 1234567891011121314151617181920212223 int[][] arr = { {1,1,1,1,1,1,1,1,1,1}, {0,0,0,0,0,0,1,1,1,1}, {1,1,1,1,1,0,0,0,0,1}, {1,1,1,1,1,0,1,.. 2017. 12. 17.
[C++ / JAVA] Factorial 재귀함수로 구현하기 안녕하세요.C++을 새롭게 공부를 하게 되면서 기존에 했던 알고리즘을 다시 작성하고 있습니다. 이를 포스팅 하려고 합니다. 필요상 말을 편하게 쓰도록 하겠습니다. 재귀함수를 이용해서 팩토리얼 연산을 하는 방법을 알아보도록 하자.재귀는 자기 자신을 계속적으로 호출하는 방법이다. 팩토리얼 연산은 다음과 같다.3! (3 팩토리얼) = 3 * 2 * 1 = 6 이러한 식으로 연산을 하는 것을 팩토리얼이라고한다. 연산을 보면 N이 1씩 줄어드는 것을 알 수 있다.이를 이용해서 재귀함수를 구현한다. 12345678910111213141516171819202122#include using namespace std; int Factorial(int n){ if (n == 1){ return 1; } return n *.. 2017. 1. 3.