일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 취득후기
- 자바PS
- 재귀함수
- 시뮬레이션
- deque
- 구현
- BFS
- 우선순위큐
- COSPRO
- 알고리즘
- 01BFS
- YBMCOS
- PS
- DFS
- 세그먼트트리
- 다이나믹프로그래밍
- 다익스트라
- spring
- 이젠 골드구현도 어렵네..
- 백준
- QUICKSTARTGUIDE
- 완전탐색
- java
- 엘라스틱서치
- COSPROJAVA1급
- 네트워크플로우
- 백준코딩테스트
- GatherTown
- dp
- 게더타운시작
- Today
- Total
목록알고리즘/Dynamic Programming (30)
공부공간
주어진 수를 제곱수로 나타낼 수 있는 최소의 항을 출력하는 문제이다. 주어진 수는, 주어진 수보다 작은 최대 제곱수의 경우 + 1의 규칙을 가지고 있다. 따라서, 해당 규칙을 만족하는 경우의 수가 현재 인덱스에 저장되어 있는 수보다 작다면, 갱신된다.
주어진 인덱스는 카드의 장수이고, 인덱스로 표기되는 팩에 따라 카드의 코스트를 입력 받는다. 원하는 카드의 개수 N 을 입력 받아 해당 카드의 개수를 구매할 때 금액의 최댓값을 출력하는 문제이다. 문제 해결에 대한 접근으로 2중 for 문을 사용하여, 원하는 카드를 구하기 까지 최대값을 갱신하도록 알고리즘을 작성한다. 카드의 구매 가능한 수에 따라, 해당 카드 팩을 구매했을 때와 그렇지 않을 때를 비교하여 최댓값을 갱신하여 준다. 카드 팩을 구매하였을 때는, 해당 카드팩의 카드 수를 빼준 최대값과 카드팩의 금액을 더한다.
https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 두가지 경우로 나누어 생각할 수있다. 격자상의 경로에서 중간점이 1)있는경우, 2)없는경우 없는 경우는 갈수있는 격자의 모든 경우의 수는 11111 12345 1361015 이런식으로 고등학교 수학에 나오는 방식으로 구할 수 있다. dp[..
종이를 반씩 접으면서 튀어나온 부분은 1 들어간 부분은 0 으로한 배열을 리턴하는 문제이다. 어떻게 이런 문제를 낼 생각을 했을까.. 직접 접어봐도 되고, 여러 방법으로 규칙을 찾으면 n번째 배열은 n-1 + 0 + n-1(변형) 의 규칙이 있는 것을 알수있다. 뒤쪽 n-1에서 배열길이의 /2에 해당되는 위치의 값이 1로 바뀌는것을 알수있다. 파이썬으로 풀어달라는 x예찬님의 요청으로 파이썬으로 풀었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 answer = [ [] for i in range(21)] visit = [False for i in range(21)] answer[1] = [0] answer[2] = [0,0,1] visit[1] = True ..
피보나치 함수에서 0과 1이 몇번 출력되었는지 출력하는 문제이다. 피보나치 수열을 살펴보면 n>=2 에 대하여 fibo(n) = fibo(n-1)+fibo(n-2) 의 점화식을 구할수 있다. 여기서 0과 1이 나온 횟수를 적어보았다. n= 0일때 -> 1 , 0 n= 1일때 -> 0 , 1 n= 2일때 -> 1 , 1 n= 3일때 -> 1 , 2 n= 4일때 -> 2 , 3 피보나치 수열과 마찬가지로 0과 1의 횟수또한 피보나치 수열점화식을 따른다.
보호되어 있는 글입니다.
보호되어 있는 글입니다.